Submission #361389

#TimeUsernameProblemLanguageResultExecution timeMemory
361389pure_memHedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++14
0 / 100
1131 ms91240 KiB
#include <cstdio> #include <vector> #include <algorithm> #include <stack> #define X first #define Y second #define MP make_pair #define ll long long using namespace std; const int N = 1e6 + 3; int n, q, w[N], ans[N], fw[N]; vector< pair< pair<int, int>, int > > aybar[N]; void upd(int v, int val){ for(;v <= n;v |= v + 1) fw[v] = max(fw[v], val); } int get(int v){ int val = 0; for(;v >= 0;v = (v & (v + 1)) - 1) val += fw[v]; return val; } int main () { scanf("%d %d", &n, &q); for(int i = 1;i <= n;i++) scanf("%d", w + i); for(int i = 1, l, r, x;i <= q;i++){ scanf("%d %d %d", &l, &r, &x); aybar[l].push_back(MP(MP(r, x), i)); } stack<int> b; for(int i = n;i >= 1;i--){ while(!b.empty() && w[i] > w[b.top()]) upd(b.top(), w[b.top()] + w[i]), b.pop(); b.push(i); for(pair< pair<int, int>, int > tmp: aybar[i]) ans[tmp.Y] = get(tmp.X.X) <= tmp.X.Y;//, cerr << get(n - tmp.X.X + 1) << " " << tmp.Y << "\n"; } for(int i = 1;i <= q;i++) printf("%d\n", ans[i]); }

Compilation message (stderr)

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:30:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   30 |  scanf("%d %d", &n, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~
sortbooks.cpp:32:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   32 |   scanf("%d", w + i);
      |   ~~~~~^~~~~~~~~~~~~
sortbooks.cpp:34:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   34 |   scanf("%d %d %d", &l, &r, &x);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#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...