제출 #342797

#제출 시각아이디문제언어결과실행 시간메모리
342797TosicHedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++14
13 / 100
1768 ms59092 KiB
#include <bits/stdc++.h> #define maxn 4000010 using namespace std; int n, m, a[maxn], ans; struct node { int maxS, minS, res; node(){ maxS = 0; minS = 1e9+10; res = 0; } }; node segTree[maxn]; void init(int idx, int l, int r){ if(l == r){ segTree[idx].maxS = segTree[idx].minS = a[l]; return; } int mid = (r+l)/2; init(idx*2+1, l, mid); init(idx*2+2, mid+1, r); segTree[idx].maxS = max(segTree[idx*2+1].maxS, segTree[idx*2+2].maxS); segTree[idx].minS = min(segTree[idx*2+1].minS, segTree[idx*2+2].minS); segTree[idx].res = max(segTree[idx*2+1].res, segTree[idx*2+2].res); if(segTree[idx*2+1].maxS > segTree[idx*2+2].minS){ segTree[idx].res = max(segTree[idx*2+1].maxS+segTree[idx*2+2].minS, segTree[idx].res); } } node query(int idx, int l, int r, int ql, int qr){ if(l >= ql and r <= qr){ return segTree[idx]; } if(l > qr or r<ql){ node tmp; return tmp; } int mid = (l+r)/2; node a = query(idx*2+1, l, mid, ql, qr); node b = query(idx*2+2, mid+1 ,r, ql, qr); node c; c.maxS = max(a.maxS, b.maxS); c.minS = min(a.minS, b.minS); c.res = max(a.res, b.res); if(a.maxS > b.minS){ c.res = max(c.res, a.maxS+b.minS);} return c; } int main(){ ios_base::sync_with_stdio(0); cout.tie(0); cin.tie(0); cin >> n >> m; for(int i = 0; i < n; ++i){ cin >> a[i]; } init(0, 0, n-1); for(int i = 0; i < m; ++i){ int l,r,k; cin>>l>>r>>k; --l, --r; if(l == r){ cout << "1\n"; continue; } //cerr << query(0,0,n-1,l,r).res << '\n'; cout << (query(0, 0, n-1, l, r).res <= k) << '\n'; } }
#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...