oj.uz

답안 #40900

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
40900 2018-02-09T22:04:13 Z Hassoony Deda (COCI17_deda) C++14
140 / 140
 910 ms 62412 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,ind,val,low;
char Q[MX];
int X[MX],A[MX],B[MX],Y[MX];
vector<int>v;
set<int>bit[MX*2];
void up(int x,int val){
    while(x<MX*2){
        bit[x].insert(val);
        x+=x&-x;
    }
}
int get(int x,int low){
    int ret=MX*2;
    while(x){
        auto pp=bit[x].lower_bound(low);
        if(pp!=bit[x].end())ret=min(ret,*pp);
        x-=x&-x;
    }
    return ret;
}
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(ind,val);
        }
        else{
            Y[i]=lower_bound(v.begin(),v.end(),Y[i])-v.begin()+1;
            ind=Y[i];low=B[i];
            int ans=get(ind,low);
            if(ans==2*MX)puts("-1");
            else printf("%d\n",ans);
        }
    }
}

Compilation message

deda.cpp: In function 'int main()':
deda.cpp:32:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s",&Q[i]);
                          ^
deda.cpp:34: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:38: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
140.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 19068 KB Output is correct
2 Correct 17 ms 19300 KB Output is correct
3 Correct 28 ms 19888 KB Output is correct
4 Correct 217 ms 28204 KB Output is correct
5 Correct 910 ms 62412 KB Output is correct
6 Correct 770 ms 62412 KB Output is correct
7 Correct 667 ms 62412 KB Output is correct