Submission #909913

#TimeUsernameProblemLanguageResultExecution timeMemory
909913crafticatDeda (COCI17_deda)C++17
120 / 140
419 ms23668 KiB
#include <bits/stdc++.h> using namespace std; constexpr int inf = 1e9 + 7; struct Segment { Segment *left = nullptr, *right = nullptr; int minY = inf; int l, r, mid; Segment(int l, int r) : l(l), r(r), mid((l + r) / 2) { if (r - 1 > l) { left = new Segment(l,mid); right = new Segment(mid,r); } } void checkForUpdates() { minY = min(left->minY,right->minY); } void update(int x, int u) { if (r - 1 <= l) { minY = u; return; } if (x >= mid) { right->update(x,u); } else { left->update(x,u); } checkForUpdates(); } int get(int a, int b, int k) { // Fully in if (a <= l && b >= r) { //return l; } // Fully out if (a >= r || b <= l) { return inf; } if (minY > k) return inf; if (r - 1 <= l) { if (minY > k) return inf; return l; } if (left->minY <= k) { int v = left->get(a,b,k); if (v == inf) return right->get(a,b,k); return v; } else return right->get(a,b,k); } }; int main() { int n, m; cin >> n >> m; Segment seg(0,n + 1); for (int i = 0; i < m; i++) { char t; cin >> t; if (t == 'M') { int a, b; cin >> a >> b; seg.update(b,a); } else { int a, b; cin >> a >> b; int v = seg.get(b,n,a); if (v == inf) v = -1; cout << v << "\n"; } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...