답안 #167730

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
167730 2019-12-09T20:38:46 Z rzbt Deda (COCI17_deda) C++14
140 / 140
235 ms 6904 KB
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define MAXN 200005
typedef long long ll;


using namespace std;


int n,q;
int seg[4*MAXN];
void dodaj(int l,int d,int p,int x,int k){
    if(l==d){
        seg[k]=x;
        return;
    }
    int mid=(l+d)/2;
    if(p<=mid)dodaj(l,mid,p,x,k+k);
    else dodaj(mid+1,d,p,x,k+k+1);
    seg[k]=min(seg[k+k],seg[k+k+1]);
}

int dobij(int l,int d,int tl,int td,int k,int x){
    //printf("    %d   %d   %d %d       %d %d\n",l,d,seg[k],k,seg[k+k],seg[k+k+1]);
    if(l>td || d<tl)return n+1;
    if(l==d && seg[k]<=x)return l;
    else if(l==d)return n+1;
    int mid=(l+d)/2;
    if(l>=tl && d<=td){
        if(seg[k+k]<=x)return dobij(l,mid,tl,td,k+k,x);
        else if(seg[k+k+1]<=x)return dobij(mid+1,d,tl,td,k+k+1,x);
        return n+1;
    }

    return min(dobij(l,mid,tl,td,k+k,x),dobij(mid+1,d,tl,td,k+k+1,x));
}

void init(int l,int d,int k){
    seg[k]=1e9+7;
    //printf("                  %d %d    %d\n",l,d,k);
    if(l==d){

        return;
    }
    int mid=(l+d)/2;
    init(l,mid,k+k);
    init(mid+1,d,k+k+1);
}

int main()
{
    scanf("%d %d", &n, &q);
    init(1,n,1);
    while(q--){
        char s[3];
        int t1,t2;
        scanf("%s %d %d",s,&t1,&t2);
        if(s[0]=='M')
            dodaj(1,n,t2,t1,1);
        else{
            int odg=dobij(1,n,t2,n,1,t1);
            if(odg==n+1)odg=-1;
            printf("%d\n",odg);
        }

    }

    return 0;
}

Compilation message

deda.cpp: In function 'int main()':
deda.cpp:56:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &q);
     ~~~~~^~~~~~~~~~~~~~~~~
deda.cpp:61:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s %d %d",s,&t1,&t2);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 194 ms 6904 KB Output is correct
5 Correct 192 ms 5624 KB Output is correct
6 Correct 219 ms 6644 KB Output is correct
7 Correct 235 ms 6904 KB Output is correct