제출 #1126879

#제출 시각아이디문제언어결과실행 시간메모리
1126879fryingducDeda (COCI17_deda)C++20
20 / 140
109 ms16124 KiB
#include "bits/stdc++.h" using namespace std; #ifdef duc_debug #include "bits/debug.h" #else #define debug(...) #endif const int maxn = 2e5 + 5; int n, q; map<int, int> bit[maxn]; void update(int x, int val) { for(int i = x; i > 0; i -= i & (-i)) { auto it = bit[i].lower_bound(val); if(it != bit[i].end() and it->second <= val) continue; it = bit[i].insert(it, make_pair(val, x)); while(it != bit[i].begin()) { it--; if(it->second >= val) { it = bit[i].erase(it); } else break; } } } int get(int i, int val) { int res = 2e9; for(; i <= n; i += i & (-i)) { auto it = bit[i].upper_bound(val); if(it != bit[i].begin()) { it--; res = min(res, it->second); } } return res; } void solve() { cin >> n >> q; while(q--) { char op; cin >> op; if(op == 'M') { int x, a; cin >> x >> a; update(a, x); } else { int y, b; cin >> y >> b; int res = get(b, y); cout << (res > 1e9 ? -1 : res) << '\n'; } } } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...