# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
40898 | Hassoony | Deda (COCI17_deda) | C++14 | 1087 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,ind,val,low;
char Q[MX];
int X[MX],A[MX],B[MX],Y[MX];
vector<int>v;
set<int>seg[MX*3];
void up(int node,int l,int r){
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);
seg[node].insert(val);
}
else up(node*2+1,mid+1,r),seg[node].insert(val);
}
int query(int node,int l,int r){
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),query(node*2+1,mid+1,r));
}
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]);
v.push_back(X[i]);
}
if(Q[i]=='D'){
scanf("%d%d",&Y[i],&B[i]);
v.push_back(Y[i]);
}
}
sort(v.begin(),v.end());
for(int i=1;i<=q;i++){
if(Q[i]=='M'){
X[i]=lower_bound(v.begin(),v.end(),X[i])-v.begin()+1;
ind=X[i];val=A[i];
up(1,1,v.size());
}
else{
Y[i]=lower_bound(v.begin(),v.end(),Y[i])-v.begin()+1;
ind=Y[i];low=B[i];
int ans=query(1,1,v.size());
if(ans==MX)puts("-1");
else printf("%d\n",ans);
}
}
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |