제출 #525225

#제출 시각아이디문제언어결과실행 시간메모리
525225PetyHedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++14
64 / 100
557 ms262148 KiB
#include <iostream> #include<vector> #include<algorithm> #pragma GCC optimize("O2") #pragma GCC optimize("Os") #pragma GCC optimize("Ofast") #pragma GCC optimize("O1") #pragma GCC optimize("O3") #pragma GCC target("avx,avx2,fma") using namespace std; const long long N = 1e6; long long n, m, w[N + 2], cnt, lg2[N + 2]; struct nodA { long long inv, st, dr; bool sorted; } aint[4 * N + 2]; vector<long long>all; long long ans = 0, mx = 0; void build (long long nod, long long st, long long dr) { if (st == dr) { aint[nod].inv = 0; aint[nod].st = all.size(); all.push_back(w[st]); aint[nod].dr = all.size(); aint[nod].sorted = 1; return; } long long mid = (st + dr) / 2; build(2 * nod, st, mid); build(2 * nod + 1, mid + 1, dr); aint[nod].inv = max(aint[2 * nod].inv, aint[2 * nod + 1].inv); auto it = lower_bound(all.begin() + aint[2 * nod + 1].st, all.begin() + aint[2 * nod + 1].dr, all[aint[2 * nod].dr - 1])-all.begin(); if (it != aint[2 * nod + 1].st) { it--; aint[nod].inv = max(aint[nod].inv, all[aint[2 * nod].dr - 1] + all[it]); } aint[nod].st = all.size(); long long i = aint[2* nod].st, j = aint[2 * nod + 1].st; while (i < aint[2 * nod].dr&& j < aint[2 * nod + 1].dr) { if (all[i] == all[j]) { long long x = all[i]; all.push_back(all[i]); all.push_back(all[i]); i++; j++; } else if (all[i]< all[j]) { all.push_back(all[i]); i++; } else if (all[i] > all[j]) { all.push_back(all[j]); j++; } } while (i < aint[2 * nod].dr) all.push_back(all[i++]); while (j < aint[2 * nod + 1].dr) all.push_back(all[j++]); aint[nod].dr = all.size(); aint[nod].sorted = (aint[2 * nod].sorted & aint[2 * nod + 1].sorted & w[mid] <= w[mid + 1]); } long long lastdr; bool ok; void query (long long nod, long long st, long long dr, long long a, long long b) { if (a <= st && dr <= b) { if (mx == -1) { ans = aint[nod].inv; mx = max(mx, all[aint[nod].dr - 1]); ok &= aint[nod].sorted; lastdr = dr; } else { if (n <= 200000) { ans = max(ans, aint[nod].inv); long long poz = aint[nod].st - 1; long long l = lg2[dr - st + 1]; for (long long pas = (1 << (l + 1)); pas; (pas >>= 1)) if (poz + pas < aint[nod].dr && all[poz + pas] < mx) poz += pas; if (poz != aint[nod].st - 1) { ans = max(ans, mx + all[poz]); } } ok &= aint[nod].sorted; ok &= (w[lastdr] <= w[lastdr + 1]); mx = max(mx, all[aint[nod].dr - 1]); lastdr = dr; } return; } long long mid = (st + dr) / 2; if (a <= mid) query(2 * nod, st, mid, a, b); if (b > mid) query(2 * nod + 1, mid + 1, dr, a, b); } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> m; for (long long i = 2; i <= n; i++) lg2[i] = lg2[i / 2] + 1; for (long long i = 1; i <= n; i++) cin >> w[i]; build(1, 1, n); for (long long i = 1; i <= m; i++) { long long l, r, k; cin >> l >> r >> k; ans = mx = lastdr = -1; ok = 1; query(1, 1, n, l, r); if (n > 200000) { cout << ok << "\n"; } else { cout << (ans <= k) << "\n"; } } return 0; }

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

sortbooks.cpp: In function 'void build(long long int, long long int, long long int)':
sortbooks.cpp:46:17: warning: unused variable 'x' [-Wunused-variable]
   46 |       long long x = all[i];
      |                 ^
sortbooks.cpp:66:80: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   66 |   aint[nod].sorted = (aint[2 * nod].sorted & aint[2 * nod + 1].sorted & w[mid] <= w[mid + 1]);
      |                                                                         ~~~~~~~^~~~~~~~~~~~~
#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...