# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
40896 | Hassoony | Deda (COCI17_deda) | C++14 | 263 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.
#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
typedef long long ll;
typedef double D;
const ll inf=(1ll<<61);
const int mod=1e9+7;
const int MX=2e5+9;
int n,q;
char Q[MX];
int X[MX],A[MX],B[MX],Y[MX];
map<int,int>hashy;
set<int>seg[MX*2];
void up(int node,int l,int r,int ind,int val){
if(l>ind||r<ind)return;
if(l==r){
seg[node].insert(val);
return;
}
int mid=(l+r)/2;
if(l<=ind&&ind<=mid){
up(node*2,l,mid,ind,val);
seg[node].insert(val);
}
else up(node*2+1,mid+1,r,ind,val),seg[node].insert(val);
}
int query(int node,int l,int r,int ind,int low){
if(l>ind)return MX;
if(r<=ind){
auto pp=seg[node].lower_bound(low);
if(pp!=seg[node].end())return *pp;
return MX;
}
int mid=(l+r)/2;
return min(query(node*2,l,mid,ind,low),query(node*2+1,mid+1,r,ind,low));
}
int main(){
cin>>n>>q;
for(int i=1;i<=q;i++){
scanf("%s",&Q[i]);
if(Q[i]=='M'){
scanf("%d%d",&X[i],&A[i]);
hashy[X[i]]=1;
}
if(Q[i]=='D'){
scanf("%d%d",&Y[i],&B[i]);
hashy[Y[i]]=1;
}
}
int tt=0;
for(auto pp:hashy){
hashy[pp.first]=++tt;
}
for(int i=1;i<=q;i++){
if(Q[i]=='M'){
X[i]=hashy[X[i]];
up(1,1,tt,X[i],A[i]);
}
else{
Y[i]=hashy[Y[i]];
int ans=query(1,1,tt,Y[i],B[i]);
if(ans==MX)puts("-1");
else printf("%d\n",ans);
}
}
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |