제출 #342814

#제출 시각아이디문제언어결과실행 시간메모리
342814TosicHedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++14
17 / 100
638 ms64108 KiB
#include <bits/stdc++.h> #define maxn 800010 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]; vector<int> sorted[maxn]; void init(int idx, int l, int r){ //cerr<< idx<< '\n'; if(l == r){ segTree[idx].maxS = segTree[idx].minS = a[l]; //cerr<< 'a'; sorted[idx].clear(); sorted[idx]={a[l]}; //cerr<<'b'; return; } int mid = (r+l)/2; init(idx*2+1, l, mid); init(idx*2+2, mid+1, r); //cerr<< sorted[idx*2+1].size( ) << '\n'; 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 =sorted[idx*2+1].size(), m1 = sorted[idx*2+2].size(); //cerr<< sorted[idx*2+1].size() << '\n'; sorted[idx].clear(); sorted[idx].resize(sorted[idx*2+1].size()+sorted[idx*2+2].size()); merge(sorted[idx*2+1].begin(), sorted[idx*2+1].end(), sorted[idx*2+2].begin(), sorted[idx*2+2].end(), sorted[idx].begin()); // for(int i = 0, j = 0; i < n1 and j < m1; i = min(i, n1-1), j =min(j, m1-1)){ // int a = sorted[idx*2+1][i], b = sorted[idx*2+2][j]; // if(a < b){ // sorted[idx].push_back(a); // ++i; // } else { // sorted[idx].push_back(b); // ++j; // } // } //cerr<< 'a' << '\n'; int tmp = lower_bound(sorted[idx*2+2].begin(), sorted[idx*2+2].end(), segTree[idx*2+1].maxS) - sorted[idx*2+2].begin(); --tmp; if(tmp >= 0){ segTree[idx].res = max(segTree[idx].res, sorted[idx*2+2][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(sorted[j].begin(), sorted[j].end(),pr)-sorted[j].begin(); --tmpIdx; if(tmpIdx >= 0){ tmp = max(sorted[j][tmpIdx] + pr, tmp); } pr = sorted[j].back(); } cout << (tmp<=k) << '\n'; } }

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

sortbooks.cpp: In function 'void init(int, int, int)':
sortbooks.cpp:37:6: warning: unused variable 'n1' [-Wunused-variable]
   37 |  int n1  =sorted[idx*2+1].size(), m1 = sorted[idx*2+2].size();
      |      ^~
sortbooks.cpp:37:35: warning: unused variable 'm1' [-Wunused-variable]
   37 |  int n1  =sorted[idx*2+1].size(), m1 = sorted[idx*2+2].size();
      |                                   ^~
#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...