oj.uz

Submission #40896

# Submission time Handle Problem Language Result Execution time Memory
40896 2018-02-09T20:27:36 Z Hassoony Deda (COCI17_deda) C++14
60 / 140
 263 ms 65536 KB 
#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

deda.cpp: In function 'int main()':
deda.cpp:40:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s",&Q[i]);
                          ^
deda.cpp:42:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d",&X[i],&A[i]);
                                      ^
deda.cpp:46:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d",&Y[i],&B[i]);
                                      ^

Subtask #1
60.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 19064 KB Output is correct
2 Correct 16 ms 19172 KB Output is correct
3 Correct 23 ms 20124 KB Output is correct
4 Runtime error 256 ms 63300 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 257 ms 65536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 263 ms 65536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 256 ms 65536 KB Execution killed with signal 11 (could be triggered by violating memory limits)