# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
918837 | noyancanturk | Deda (COCI17_deda) | C++17 | 235 ms | 65536 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.
#ifndef Local
#pragma GCC optimize("O3,unroll-loops")
const int lim=1e5+100;
#else
const int lim=3e3+100;
#endif
#include "bits/stdc++.h"
using namespace std;
//#define int int64_t
#define pb push_back
const int mod=1e9+7;
using pii=pair<int,int>;
int P,VAL;
struct node{
set<int>vals;
node *lc,*rc;
node():lc(nullptr),rc(nullptr){}
void update(int l,int r){
vals.insert(VAL);
if(l==r){
return;
}
int mid=(l+r)>>1;
if(P<=mid){
if(!lc)lc = new node();
lc->update(l,mid);
}else{
if(!rc)rc = new node();
rc->update(mid+1,r);
}
}
int query(int l,int r){
if(r<=P){
auto p=vals.lower_bound(VAL);
if(p!=vals.end()){
return *p;
}
return INT_MAX;
}
if(P<l){
return INT_MAX;
}
int mid=(l+r)>>1,ans=INT_MAX;
if(lc)ans=lc->query(l,mid);
if(rc)ans=min(ans,rc->query(mid+1,r));
return ans;
}
};
struct segtree{
node root;
void update(int p,int val){
P=p,VAL=val;
root.update(1,(int)1e9);
}
int query(int p,int val){
P=p,VAL=val;
int ans=root.query(1,(int)1e9);
if(ans^INT_MAX)return ans;
return -1;
}
};
inline void solve(){
int n,q;
cin>>n>>q;
segtree st;
for(int i=0;i<q;i++){
char ty;
int p,v;
cin>>ty>>p>>v;
if(ty=='M'){
st.update(p,v);
}else{
cout<<st.query(p,v)<<"\n";
}
}
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
#ifdef Local
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#else
#endif
int t=1;
//cin>>t;
while (t--)
{
solve();
}
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |