제출 #375295

#제출 시각아이디문제언어결과실행 시간메모리
375295ezdpDeda (COCI17_deda)C++17
60 / 140
301 ms65540 KiB
#pragma GCC optimize ("O3") #pragma GCC target ("sse4") #include<bits/stdc++.h> #include<ext/pb_ds/assoc_container.hpp> #define endl '\n' #define pb push_back #define fr first #define sc second #define ll long long int #define ld long double #define bit(idx) idx&(-idx) #define bin(x) bitset<32>(x).to_string() #define all(A) A.begin(), A.end() #define de(x) cout << #x << " = " << x << endl; #define row vector<ll> #define row_matrix vector<ll> #define matrix vector<row_matrix> #define ordered_set_T pair<ll, ll> using namespace std; using namespace __gnu_pbds; typedef tree<ordered_set_T, null_type, less<ordered_set_T>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; /// find_by_order(x) -> x-th element in the set /// order_of_key(x) -> how many elements are smaller than x /// insert(x) -> inserts x into the set const ll MAXN = 3e5 + 5; ordered_set segmtree[2 * MAXN]; ll n, q, T = 1; ll smaller_than(ordered_set &container, ll v){ return container.order_of_key({v + 1, 0}); } void upd(int node, int l, int r, int x, int v){ if(l == r){ segmtree[node].insert({v, T}); } else{ int m = (l + r) / 2; if(l <= x && x <= m) upd(2 * node, l, m, x, v); else upd(2 * node + 1, m + 1, r, x, v); segmtree[node].insert({v, T}); } } ll qry(int node, int l, int r, int ql, int qr, int v){ /// cout << node << " " << l << " " << r << " " << ql << " " << qr << " " << v << endl; if(r < ql || qr < l){ return LLONG_MAX; } else if(l == r && smaller_than(segmtree[node], v)){ return l; } else if(ql <= l && r <= qr){ int m = (l + r) / 2; /// cout << "left: \n"; for(auto [x, y] : segmtree[2 * node + 0]) cout << x << " " << y << endl; /// cout << "right:\n"; for(auto [x, y] : segmtree[2 * node + 1]) cout << x << " " << y << endl; if(smaller_than(segmtree[2 * node], v)) return qry(2 * node, l, m, ql, qr, v); else if(smaller_than(segmtree[2 * node + 1], v)) return qry(2 * node + 1, m + 1, r, ql, qr, v); else return LLONG_MAX; } else{ int m = (l + r) / 2; ll q1 = qry(2 * node, l, m, ql, qr, v); ll q2 = qry(2 * node + 1, m + 1, r, ql, qr, v); return min(q1, q2); } } void upd(int x, int v){ upd(1, 1, n, x, v); ++ T; } ll qry(int x, int v){ return qry(1, 1, n, x, n, v); } int main(){ /// ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n >> q; for(int i = 0; i < q; i ++){ char t; int x, y; cin >> t >> x >> y; if(t == 'M'){ upd(y, x); /// for(int i = 1; i <= 4 * n; i ++) { cout << i << ": "; for(auto [x, y] : segmtree[i]) cout << x << " "; cout << endl; } } if(t == 'D'){ ll tmp = qry(y, x); cout << (tmp == LLONG_MAX ? -1 : tmp) << endl; } } } /** */
#Verdict Execution timeMemoryGrader output
Fetching results...