Submission #860311

#TimeUsernameProblemLanguageResultExecution timeMemory
860311pctirziuDeda (COCI17_deda)C++17
140 / 140
451 ms6196 KiB
#include <iostream> using namespace std; const int nmax = 3e5 + 5; const int valmax = 2e9 + 5; int aint[nmax * 4]; void update(int node, int st, int dr, int l, int r, int val) { if(st > r or dr < l) return ; if(st == dr){ aint[node] = val; return; } int mid = (st + dr) / 2; update(node * 2, st, mid, l, r, val); update(node * 2 + 1, mid + 1, dr, l, r, val); aint[node] = min(aint[2 * node], aint[2 * node + 1]); } int query(int node, int st, int dr, int l, int r, int val) { if(st > r or dr < l) return -1; if(l <= st and dr <= r){ if(aint[node] > val) return -1; int rasp; while(st <= dr){ int mid = (st + dr) / 2; if(st == dr){ if(aint[node] <= val) return st; } if(aint[2 * node] <= val){ dr = mid; rasp = mid; node = node * 2; } else{ st = mid + 1; node = node * 2 + 1; } } return rasp; } int mid = (st + dr) / 2; int rasp = query(node * 2, st, mid, l, r, val); if(rasp != -1) return rasp; return query(node * 2 + 1, mid + 1, dr, l, r, val); } int main() { int n, q; cin >> n >> q; for(int i = 0; i <= 4 * nmax; i++) aint[i] = valmax; while(q--){ string s; cin >> s; if(s == "M"){ int x, y; cin >> x >> y; update(1, 1, n, y, y, x); } else{ int x, y; cin >> x >> y; cout << query(1, 1, n, y, n, x) << "\n"; } } }

Compilation message (stderr)

deda.cpp: In function 'int main()':
deda.cpp:61:17: warning: iteration 1200020 invokes undefined behavior [-Waggressive-loop-optimizations]
   61 |         aint[i] = valmax;
      |         ~~~~~~~~^~~~~~~~
deda.cpp:60:22: note: within this loop
   60 |     for(int i = 0; i <= 4 * nmax; i++)
      |                    ~~^~~~~~~~~~~
deda.cpp: In function 'int query(int, int, int, int, int, int)':
deda.cpp:30:13: warning: 'rasp' may be used uninitialized in this function [-Wmaybe-uninitialized]
   30 |         int rasp;
      |             ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...