# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
919047 | vjudge1 | Deda (COCI17_deda) | C++17 | 78 ms | 8020 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.
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define sp << " " <<
//#define int long long
#define vi vector<int>
#define pb push_back
#define flag {cout << "OK\n";return;}
#define F(xxx,yyy) for (int xxx=1;xxx<=yyy;xxx++)
#define pii pair<int,int>
const int N = 2e5+1, inf = 1e9+1, MOD = 1e9+7;
struct ST {
vector<int> t;
int n;
ST(int nn) {
n = nn;
t.assign(4*n+1,inf);
}
int walk(int node,int l,int r,int x) {
if (t[node] > x) return -1;
if (l == r) return l;
int m = (l+r) >> 1;
if (t[2*node] <= x) return walk(2*node,l,m,x);
return walk(2*node+1,m+1,r,x);
}
int query(int node,int l,int r,int L,int R,int x) {
// cout << l sp r sp L sp R << endl;
// if (l == r) cout << "v[" << l << "]" << "=" << t[node] << endl;
if (l >= L && r <= R) {
int w = walk(node,l,r,x);
if (w == -1) return inf;
return w;
};
int m = (l+r) >> 1;
if (m >= L){
int y = query(2*node,l,m,L,R,x);
if (y != inf) return y;
}
if (m+1 <= R) {
return query(2*node+1,m+1,r,L,R,x);
}
return inf;
}
void update(int node,int l,int r,int p,int v) {
if (l == r) {
t[node] = v;
return;
}
int m = (l+r) >> 1;
if (p <= m) update(2*node,l,m,p,v);
else update(2*node+1,m+1,r,p,v);
t[node] = min(t[2*node],t[2*node+1]);
}
};
void solve() {
int n,q;
cin >> n >> q;
ST t(n);
while (q--) {
char type;
cin >> type;
if (type == 'M') {
int v,p;
cin >> v >> p;
t.update(1,1,n,p,v);
}
else {
int v,l;
cin >> v >> l;
int vv = t.query(1,1,n,l,n,v);
cout << ((vv == inf)?-1:vv) << '\n';
}
}
}
signed main() {
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#ifdef Local
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
int t = 1;
//cin >> t;
while (t --> 0) solve();
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |