제출 #643437

#제출 시각아이디문제언어결과실행 시간메모리
643437czhang2718Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++17
0 / 100
2099 ms158672 KiB
#include "bits/stdc++.h" using namespace std; typedef long long ll; int n, q; const int N=1e6; int mx[4*N], lazy[4*N]; int a[N]; void push(int x, int lx, int rx){ if(rx-lx==1 || !lazy[x]) return; for(int y:{2*x+1, 2*x+2}){ mx[y]+=lazy[x]; lazy[y]+=lazy[x]; } lazy[x]=0; } void add(int l, int r, int v, int x, int lx, int rx){ push(x,lx,rx); if(lx>=r || rx<=l) return; if(lx>=l && rx<=r){ lazy[x]+=v; mx[x]+=v; return; } int m=(lx+rx)/2; add(l,r,v,2*x+1,lx,m); add(l,r,v,2*x+2,m,rx); } void add(int l, int r, int v){ if(r<=l) return; add(l, r, v, 0, 0, n); } int get_mx(int l, int r, int x, int lx, int rx){ push(x,lx,rx); if(lx>=r || rx<=l) return -1; if(lx>=l && rx<=r){ return mx[x]; } int m=(lx+rx)/2; return max(get_mx(l,r,2*x+1,lx,m), get_mx(l,r,2*x+2,m,rx)); } int get_mx(int l, int r){ return get_mx(l,r,0,0,n); } void build(int x, int lx, int rx){ if(rx-lx==1){ mx[x]=a[lx]; return; } int m=(lx+rx)/2; build(2*x+1, lx, m); build(2*x+2, m, rx); mx[x]=max(mx[2*x+1], mx[2*x+2]); } signed main(){ cin.tie(0)->sync_with_stdio(0); cin >> n >> q; for(int i=0; i<n; i++){ cin >> a[i]; } build(0, 0, n); vector<vector<int>> qu(n), lr(q, vector<int>(2)); vector<int> ans(q), k(q); for(int i=0; i<q; i++){ cin >> lr[i][0] >> lr[i][1] >> k[i]; lr[i][0]--, lr[i][1]--; qu[lr[i][0]].push_back(i); } stack<int> s; s.push(n); int inf=2e9; for(int i=n-1; i>=0; i--){ int lst=i; while(s.size()>1 && a[i]>a[s.top()]){ int j=s.top(); s.pop(); int j2=s.top(); add(j+1, j2, -a[j]); add(j,j+1,-inf+a[j]); } add(i,i+1,-a[i]+inf); add(i+1,s.top(),a[i]); s.push(i); for(int p:qu[i]){ ans[p]=get_mx(i,lr[p][1]+1); } } for(int i=0; i<q; i++){ cout << (k[i]>=ans[i]) << "\n"; } } // range add // range max // tuck a knife with my heart up my sleeve

컴파일 시 표준 에러 (stderr) 메시지

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:83:13: warning: unused variable 'lst' [-Wunused-variable]
   83 |         int lst=i;
      |             ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...