結果
問題 | No.961 Vibrant Fillumination |
ユーザー | kmjp |
提出日時 | 2019-12-24 01:11:31 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 3,688 bytes |
コンパイル時間 | 2,441 ms |
コンパイル使用メモリ | 185,452 KB |
実行使用メモリ | 55,552 KB |
最終ジャッジ日時 | 2024-09-19 05:38:11 |
合計ジャッジ時間 | 19,496 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 31 ms
45,568 KB |
testcase_01 | AC | 31 ms
45,440 KB |
testcase_02 | AC | 304 ms
55,296 KB |
testcase_03 | AC | 298 ms
55,552 KB |
testcase_04 | AC | 289 ms
55,424 KB |
testcase_05 | AC | 296 ms
55,552 KB |
testcase_06 | AC | 287 ms
55,424 KB |
testcase_07 | AC | 295 ms
55,424 KB |
testcase_08 | AC | 298 ms
55,424 KB |
testcase_09 | AC | 297 ms
55,424 KB |
testcase_10 | AC | 371 ms
55,424 KB |
testcase_11 | AC | 376 ms
55,552 KB |
testcase_12 | AC | 376 ms
55,552 KB |
testcase_13 | AC | 385 ms
55,552 KB |
testcase_14 | AC | 374 ms
55,424 KB |
testcase_15 | AC | 391 ms
55,552 KB |
testcase_16 | AC | 371 ms
55,424 KB |
testcase_17 | AC | 376 ms
55,552 KB |
testcase_18 | AC | 363 ms
55,424 KB |
testcase_19 | AC | 375 ms
55,552 KB |
testcase_20 | AC | 372 ms
55,552 KB |
testcase_21 | AC | 375 ms
55,424 KB |
testcase_22 | AC | 373 ms
55,552 KB |
testcase_23 | AC | 372 ms
55,552 KB |
testcase_24 | AC | 371 ms
55,552 KB |
testcase_25 | AC | 366 ms
55,552 KB |
testcase_26 | TLE | - |
testcase_27 | -- | - |
testcase_28 | -- | - |
testcase_29 | -- | - |
testcase_30 | -- | - |
testcase_31 | -- | - |
testcase_32 | -- | - |
testcase_33 | -- | - |
testcase_34 | -- | - |
testcase_35 | -- | - |
testcase_36 | -- | - |
testcase_37 | -- | - |
testcase_38 | -- | - |
testcase_39 | -- | - |
testcase_40 | -- | - |
testcase_41 | -- | - |
testcase_42 | -- | - |
testcase_43 | -- | - |
testcase_44 | -- | - |
testcase_45 | -- | - |
testcase_46 | -- | - |
testcase_47 | -- | - |
testcase_48 | -- | - |
testcase_49 | -- | - |
ソースコード
#include <bits/stdc++.h>using namespace std;typedef signed long long ll;#undef _P#define _P(...) (void)printf(__VA_ARGS__)#define FOR(x,to) for(x=0;x<(to);x++)#define FORR(x,arr) for(auto& x:arr)#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)#define ALL(a) (a.begin()),(a.end())#define ZERO(a) memset(a,0,sizeof(a))#define MINUS(a) memset(a,0xff,sizeof(a))//-------------------------------------------------------int N;ll H[505050];int X1[505050],Y1[505050];int X2[505050],Y2[505050];vector<ll> Ys[101010];int C[505050];int Q;int QX[101010],QY[101010];ll ret[101010];vector<int> add[101010],del[101010],query[101010];template<class V,int NV> class STma {public:vector<V> val, ma;STma(){val.resize(NV*2,0); ma.resize(NV*2,0);};V getval(int x,int y,int l=0,int r=NV,int k=1) {if(r<=x || y<=l) return 0;if(x<=l && r<=y) return ma[k];return val[k]+max(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));}void update(int x,int y, V v,int l=0,int r=NV,int k=1) {if(l>=r) return;if(x<=l && r<=y) {val[k]+=v;ma[k]+=v;}else if(l < y && x < r) {update(x,y,v,l,(l+r)/2,k*2);update(x,y,v,(l+r)/2,r,k*2+1);ma[k]=val[k]+max(ma[k*2],ma[k*2+1]);}}};template<class V,int NV> class STmi {public:vector<V> val, ma;STmi(){int i;val.resize(NV*2,0); ma.resize(NV*2,0);};V getval(int x,int y,int l=0,int r=NV,int k=1) {if(r<=x || y<=l) return 1<<20;if(x<=l && r<=y) return ma[k];return val[k]+min(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));}void update(int x,int y, V v,int l=0,int r=NV,int k=1) {if(l>=r) return;if(x<=l && r<=y) {val[k]+=v;ma[k]+=v;}else if(l < y && x < r) {update(x,y,v,l,(l+r)/2,k*2);update(x,y,v,(l+r)/2,r,k*2+1);ma[k]=val[k]+min(ma[k*2],ma[k*2+1]);}}};STma<int,1<<20> st1;STmi<int,1<<20> st2;template<class V, int ME> class BIT {public:V bit[1<<ME];V operator()(int e) {if(e<0) return 0;V s=0;e++;while(e) s^=bit[e-1],e-=e&-e; return s;}void add(int e,V v) { e++; while(e<=1<<ME) bit[e-1]^=v,e+=e&-e;}};BIT<ll,20> bt;int id[101010];void go(int c,int y1,int y2,int add) {int st=id[c];int sy=y1;if(add==-1) {st1.update(st+y1,st+y2,-1);st2.update(st+y1,st+y2,-1);}while(sy<y2 && st2.getval(st+sy,st+y2)==0) {int i;int la=y2;for(i=20;i>=0;i--) if(la-(1<<i)>sy && st2.getval(st+sy,st+la-(1<<i))==0) la-=1<<i;sy=la-1;for(i=20;i>=0;i--) if(sy+(1<<i)<=y2 && st1.getval(st+sy,st+sy+(1<<i))==0) {bt.add(Ys[c][sy],H[c]);sy+=(1<<i);bt.add(Ys[c][sy],H[c]);}}if(add==1) {st1.update(st+y1,st+y2,1);st2.update(st+y1,st+y2,1);}}void solve() {int i,j,k,l,r,x,y; string s;cin>>N;FOR(i,N) cin>>H[i];FOR(i,N) {cin>>X1[i]>>Y1[i]>>X2[i]>>Y2[i]>>C[i];C[i]--;Ys[C[i]].push_back(Y1[i]);Ys[C[i]].push_back(Y2[i]);add[X1[i]].push_back(i);del[X2[i]].push_back(i);}FOR(i,N) {Ys[i].push_back(2*N+1);sort(ALL(Ys[i]));Ys[i].erase(unique(ALL(Ys[i])),Ys[i].end());id[i+1]=id[i]+Ys[i].size();}FOR(i,N) {Y1[i]=lower_bound(ALL(Ys[C[i]]),Y1[i])-Ys[C[i]].begin();Y2[i]=lower_bound(ALL(Ys[C[i]]),Y2[i])-Ys[C[i]].begin();}cin>>Q;FOR(i,Q) {cin>>QX[i]>>QY[i];query[QX[i]].push_back(i);}FOR(x,101000) {FORR(a,add[x]) go(C[a],Y1[a],Y2[a],1);FORR(a,del[x]) go(C[a],Y1[a],Y2[a],-1);FORR(q,query[x]) ret[q]=bt(QY[q]);}FOR(i,Q) cout<<ret[i]<<endl;}int main(int argc,char** argv){string s;int i;if(argc==1) ios::sync_with_stdio(false), cin.tie(0);FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);cout.tie(0); solve(); return 0;}