Submission #97823

#TimeUsernameProblemLanguageResultExecution timeMemory
97823dalgerokDeda (COCI17_deda)C++17
140 / 140
151 ms6876 KiB
#include<bits/stdc++.h> using namespace std; const int N = 2e5 + 5, INF = 2e9; int n, m, t[4 * N]; void update(int v, int l, int r, int pos, int val){ if(l == r){ t[v] = val; return; } int mid = (r + l) >> 1; if(pos <= mid){ update(v + v, l, mid, pos, val); } else{ update(v + v + 1, mid + 1, r, pos, val); } t[v] = min(t[v + v], t[v + v + 1]); } int get(int v, int l, int r, int tl, int tr, int val){ if(l > r || l > tr || tl > r || t[v] > val){ return -1; } if(l == r){ return l; } int mid = (r + l) >> 1; int x = get(v + v, l, mid, tl, tr, val); if(x == -1){ x = get(v + v + 1, mid + 1, r, tl, tr, val); } return x; } int main(){ ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin >> n >> m; for(int i = 1; i <= n; i++){ update(1, 1, n, i, INF); } while(m--){ char c; cin >> c; if(c == 'M'){ int x, y; cin >> x >> y; update(1, 1, n, y, x); } else{ int x, y; cin >> x >> y; cout << get(1, 1, n, y, n, x) << "\n"; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...