Submission #167449

#TimeUsernameProblemLanguageResultExecution timeMemory
167449tincamateiHedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++14
100 / 100
2186 ms110128 KiB
#include <bits/stdc++.h> using namespace std; const int MAX_N = 1000000; int aint[1+4*MAX_N]; void update(int poz, int val, int l = 1, int r = MAX_N, int nod = 1) { if(poz < l || r < poz) return; if(l == r) aint[nod] = max(aint[nod], val); else { int mid = (l + r) / 2; update(poz, val, l, mid, 2 * nod); update(poz, val, mid + 1, r, 2 * nod + 1); aint[nod] = max(aint[2 * nod], aint[2 * nod + 1]); } } int query(int i, int j, int l = 1, int r = MAX_N, int nod = 1) { if(j < l || r < i || j < i) return -1; if(i <= l && r <= j) return aint[nod]; else { int mid = (l + r) / 2; return max(query(i, j, l, mid, 2 * nod), query(i, j, mid + 1, r, 2 * nod + 1)); } } int v[1+MAX_N]; int stiva[1+MAX_N], top; int nextBigger[1+MAX_N]; bool rez[1+MAX_N]; struct Query { int l, r, k; bool *rez; }; vector<Query> queryBucket[1+MAX_N]; int main() { int N, M; scanf("%d%d", &N, &M); for(int i = 1; i <= N; ++i) { scanf("%d", &v[i]); while(top > 0 && v[stiva[top - 1]] <= v[i]) --top; if(top > 0) nextBigger[i] = stiva[top - 1]; stiva[top++] = i; } for(int i = 0; i < M; ++i) { int l, r, k; scanf("%d%d%d", &l, &r, &k); queryBucket[r].push_back({l, r, k, &rez[i]}); } for(int i = 1; i <= N; ++i) { if(nextBigger[i] != 0) update(nextBigger[i], v[i] + v[nextBigger[i]]); for(auto it: queryBucket[i]) { if(query(it.l, it.r) <= it.k) *it.rez = true; else *it.rez = false; } } for(int i = 0; i < M; ++i) printf("%d\n", rez[i]); return 0; }

Compilation message (stderr)

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:46:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~
sortbooks.cpp:48:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &v[i]);
   ~~~~~^~~~~~~~~~~~~
sortbooks.cpp:59:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &l, &r, &k);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
#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...