# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
222948 | ngot23 | Deda (COCI17_deda) | C++11 | 1093 ms | 3900 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int N=200005;
int t[N*4], n, Q;
void update(int l, int r, int id, int u, int val) {
if(u<l || u>r) return;
if(l==r) {t[id]=val;return;}
int mid=(r+l)>>1;
update(l, mid, id*2, u, val);
update(mid+1, r, id*2+1, u, val);
t[id]=min(t[id*2], t[id*2+1]);
}
int get(int l, int r, int id, int u, int val) {
if(r<u) return -1;
if(l==r) {
if(t[id]<=val) return l;
return -1;
}
int mid = (r+l)>>1;
if(u<=mid) {
int x=get(l, mid, id*2, u, val);
if(x!=-1) return x;
int y=get(mid+1, r, id*2+1, u, val);
if(y!=-1) return y;
} else {
int x=get(mid+1, r, id*2+1, u, val);
return x;
}
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
if(fopen(".inp", "r")) freopen(".inp", "r", stdin);
cin >> n >> Q;
for(int i=0 ; i<=n*4 ; ++i) t[i]=1e9+1;
for(int i=1 ; i<=Q ; ++i) {
int c, d; char x;
cin >> x >> c >> d;
if(x=='M') {
update(1, n, 1, d, c);
} else {
int id=get(1, n, 1, d, c);
cout << id << '\n';
}
}
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |