Submission #167730

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
167730	2019-12-09T20:38:46 Z	rzbt	Deda (COCI17_deda)	C++14	140 / 140	235 ms	6904 KB

deda

#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);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	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