# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1110446 | _uros9 | Deda (COCI17_deda) | C++17 | 131 ms | 17368 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>
#define endl '\n'
#define int long long
using namespace std;
const long long longlongmax=9223372036854775807;
const int modul=998244353;
const long long mod = 1e9 + 7;
mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());
const int N=200009,INF=100000000000009;
struct Cvor{
Cvor(){}
Cvor(int val,int l,int d){this->val=val;this->l=l;this->d=d;}
int val,l,d;
};
Cvor seg[4*N];
void upd(int node,int l,int d,int ind,int value){
if(l==d&&d==ind) {seg[node]=Cvor(value,l,d); return;}
if(d<ind||l>ind) return;
int s=l+d>>1;
upd(2*node,l,s,ind,value);
upd(2*node+1,s+1,d,ind,value);
seg[node]=Cvor(min(seg[2*node].val,seg[2*node+1].val),l,d);
}
vector<int> bitni;
void query(int node,int l,int d,int poc,int kr){
if(poc<=l&&d<=kr){bitni.push_back(node); return;}
if(d<poc||l>kr) return;
int s=l+d>>1;
query(2*node,l,s,poc,kr);
query(2*node+1,s+1,d,poc,kr);
}
int query2(int node,int l,int d,int Y){
if(l==d) return l;
int s=l+d>>1;
if(seg[2*node].val<=Y)
return query2(2*node,l,s,Y);
return query2(2*node+1,s+1,d,Y);
}
int n,q;
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
//freopen("factory.in","r",stdin);
//freopen("factory.out","w",stdout);
cin >> n >> q;
for(int i=1; i<=n; i++) upd(1,1,n,i,INF);
while(q--){
char c;
cin >> c;
if(c=='M'){
int x,ind;
cin >> x >> ind;
upd(1,1,n,ind,x);
}
else{
int Y,B;
cin >> Y >> B;
query(1,1,n,B,n);
int rez=-1;
for(auto x:bitni){
if(seg[x].val<=Y){
rez=query2(x,seg[x].l,seg[x].d,Y);
break;
}
}
cout << rez << endl;
bitni.clear();
}
}
return 0;
}
/*
abcde
01234
04321 --> 12340
0 1
011
110
1
3 1
1 2 3
3 5
*/
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |