제출 #344403

#제출 시각아이디문제언어결과실행 시간메모리
344403TosicHedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++14
0 / 100
244 ms44908 KiB
#include <bits/stdc++.h> #define maxn 800010 using namespace std; int n, m, a[maxn], allR[maxn], ans; vector<int> sorted[maxn]; void init(int idx, int l, int r){ if(l == r){ sorted[idx]={a[l]}; return; } int mid = (r+l)/2, lC = idx*2+1, rC = idx*2+2; init(lC, l, mid); init(rC, mid+1, r); sorted[idx].resize(sorted[lC].size()+sorted[rC].size()); int tmp = lower_bound(sorted[rC].begin(), sorted[rC].end(), sorted[lC].back()) - sorted[rC].begin(); --tmp; allR[idx] = max(allR[lC], allR[rC]); if(!sorted[lC].empty() and !sorted[rC].empty() and tmp >= 0){ allR[idx] = max(allR[idx], sorted[rC][tmp] + sorted[lC].back() ); } merge(sorted[lC].begin(), sorted[lC].end(), sorted[rC].begin(), sorted[rC].end(), sorted[idx].begin()); //sort(sorted[idx].begin(), sorted[idx].end()); } 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 allR[idx]; } 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; allIx.clear(); int tmp = query(0,0, n-1,l,r), pr = -1; for(int i1 = 0; i1 < allIx.size();++i1){ int j = allIx[i1]; 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 = max(pr, sorted[j].back()); } cout << (tmp<=k) << '\n'; } }

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

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:57:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |   for(int i1 = 0; i1 < allIx.size();++i1){
      |                   ~~~^~~~~~~~~~~~~~
#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...