結果
問題 | No.1074 増殖 |
ユーザー |
![]() |
提出日時 | 2020-06-05 21:56:28 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 69 ms / 2,000 ms |
コード長 | 1,460 bytes |
コンパイル時間 | 2,334 ms |
コンパイル使用メモリ | 200,332 KB |
最終ジャッジ日時 | 2025-01-10 22:31:28 |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 |
ソースコード
#include <bits/stdc++.h> using namespace std; template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;} template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;} using Int = long long; const char newl = '\n'; //INSERT ABOVE HERE signed main(){ cin.tie(0); ios::sync_with_stdio(0); Int n; cin>>n; using P = pair<Int, Int>; set<P> sp1,sp2,sp3,sp4; const Int INF = 30000; sp1.emplace(0,INF); sp2.emplace(0,INF); sp3.emplace(0,INF); sp4.emplace(0,INF); sp1.emplace(INF,0); sp2.emplace(INF,0); sp3.emplace(INF,0); sp4.emplace(INF,0); auto calc=[&](auto &sp,P p)->Int{ auto area=[&](P q)->Int{ auto it=sp.lower_bound(q); auto pr=it;pr--; auto nx=it;nx++; return (it->first-pr->first)*(it->second-nx->second); }; Int res=0; Int x=p.first,y=p.second; auto it=sp.lower_bound(P(x,-1)); if(it->second>=y) return 0; while(!sp.empty()){ auto er=sp.lower_bound(P(x,y)); if(er==sp.begin()) break; er--; if(er->second<=y){ res-=area(*er); sp.erase(er); continue; } break; } sp.emplace(p); res+=area(p); return res; }; for(Int i=0;i<n;i++){ Int xa,ya,xb,yb; cin>>xa>>ya>>xb>>yb; Int dif=0; dif+=calc(sp1,P(+xb,+yb)); dif+=calc(sp2,P(-xa,+yb)); dif+=calc(sp3,P(-xa,-ya)); dif+=calc(sp4,P(+xb,-ya)); cout<<dif<<newl; } return 0; }