제출 #342813

#제출 시각아이디문제언어결과실행 시간메모리
342813TosicHedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++14
0 / 100
327 ms262148 KiB
#include <bits/stdc++.h> #define maxn 800010 using namespace std; int n, m, a[maxn], ans; struct node { int maxS, minS, res; vector<int> sorted; 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]; segTree[idx].sorted.push_back(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); int n1 =segTree[idx*2+1].sorted.size(), m1 = segTree[idx*2+2].sorted.size(); for(int i = 0, j = 0; i < n1 and j <n1; i = min(i, n1-1), j =min(j, m1-1)){ int a = segTree[idx*2+1].sorted[i], b = segTree[idx*2+2].sorted[j]; if(a < b){ segTree[idx].sorted.push_back(a); ++i; } else { segTree[idx].sorted.push_back(b); ++j; } } int tmp = lower_bound(segTree[idx*2+2].sorted.begin(), segTree[idx*2+2].sorted.end(), segTree[idx*2+1].maxS) - segTree[idx*2+2].sorted.begin(); --tmp; if(tmp >= 0){ segTree[idx].res = max(segTree[idx].res, tmp + segTree[idx*2+1].maxS); } } vector<int> allIx; int query(int idx, int l, int r, int ql, int qr){ if(l >= ql and r <= qr){ allIx.push_back(idx); return segTree[idx].res; } if(l > qr or r<ql){ return 0; } int mid = (l+r)/2; return max(query(idx*2+1, l, mid, ql, qr),query(idx*2+2, mid+1, r, ql, qr)); } 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; } allIx.clear(); if(n <= 5000){ int tmp = 0,res = 0; for(int i=l; i <= r; ++i){ if(tmp > a[i]){ res = max(res, tmp+a[i]); } tmp = max(tmp, a[i]); } cout << (res<=k) << '\n'; continue; } int tmp = query(0,0, n-1,l,r), pr = 0; for(auto j:allIx){ int tmpIdx=lower_bound(segTree[j].sorted.begin(), segTree[j].sorted.end(),pr)-segTree[j].sorted.begin(); --tmpIdx; if(tmpIdx >= 0){ tmp = max(segTree[j].sorted[tmpIdx] + pr, tmp); } pr = segTree[j].sorted.back(); } cout << (tmp<=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...