2008年 日本情報オリンピック春合宿OJ Origami

問題

https://www.ioi-jp.org/camp/2008/2008-sp-tasks/2008-sp_tr-day3_22.pdf

検討

２次元イモスみたいな方法でやるのかなと思いましたがうまくありません。

100万＊100万と非常に広い範囲ですが，個々の折り紙は高々20*20、またその枚数も5000枚以下なので、折り紙の総面積としては400*5000=2000000(200万）以下です。
mapですべてカウントしてやる方針で解けそうです。

ACしたコード

#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> P;

int main(){
  int n,a,b;
  cin>>n>>a>>b;
  map<P,int>mp;
  int p,q,r,s;
  for(int i=0;i<n;i++){
    cin>>p>>q>>r>>s;
    p--;q--;r--;s--;
    for(int j=p;j<=r;j++){
      for(int k=q;k<=s;k++){
        mp[{j,k}]++;
      }
    }
  }
  int ans=0;
  for(auto itr=mp.begin();itr !=mp.end();itr++){
    ans=max(itr->second,ans);
  }
  cout<<ans<<endl;
  int cnt=0;
  for(auto itr=mp.begin();itr !=mp.end();itr++){
    if(itr->second==ans){
      cnt++;
    }
  }
  cout<<cnt<<endl;
    
  return 0;
}