Submission #871983

#TimeUsernameProblemLanguageResultExecution timeMemory
871983vjudge1Deda (COCI17_deda)C++17
80 / 140
288 ms65536 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; #define F first #define S second #define all(x) x.begin(), x.end() #define len(x) (int) x.size() #define pb push_back mt19937 rnd(time(0)); struct query { char type; int a, b; }; const int N = 2e5 + 7; map<int, int> mp; set<int> seg[N << 2]; vector<query> qu; vector<int> vec; int n, q; void read_input() { cin >> n >> q; for (int i = 0; i < q; i++) { query t; cin >> t.type >> t.a >> t.b; vec.pb(t.a); qu.pb(t); } } void prepare() { sort(all(vec)); vec.resize(unique(all(vec)) - vec.begin()); for (int i = 0; i < len(vec); i++) mp[vec[i]] = i; } void upd(int p, int x, int id = 1, int st = 0, int en = len(vec)) { if (p < st || p >= en) return; if (en - st == 1) { seg[id].insert(x); return; } int mid = (st + en) >> 1; upd(p, x, id << 1, st, mid); upd(p, x, id << 1 | 1, mid, en); seg[id].insert(x); } int get(int l, int r, int b, int id = 1, int st = 0, int en = len(vec)) { if (r <= st || l >= en) return INT_MAX; if (st >= l && en <= r) { if (seg[id].empty()) return INT_MAX; if (*(--seg[id].end()) < b) return INT_MAX; return *seg[id].lower_bound(b); } int mid = (st + en) >> 1; return min(get(l, r, b, id << 1, st, mid), get(l, r, b, id << 1 | 1, mid, en)); } void solve() { for (auto q: qu) { char type; int a, b; type = q.type, a = q.a, b = q.b; a = mp[a]; if (type == 'M') { upd(a, b); } else { int t = get(0, a + 1, b); cout << (t == INT_MAX? -1: t) << '\n'; } } } int32_t main() { ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0); read_input(), prepare(), solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...