Submission #141586

#	Time	Username	Problem	Language	Result	Execution time	Memory
141586		SeekingOblivion	Deda (COCI17_deda)	C++14	60 / 140	1060 ms	4344 KiB

deda

#include<iostream>
#include<fstream>
#define fin cin
#define fout cout
using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
int v[500001],a,b,n,q,ok;
char c;
void build(int i,int st,int dr)
{
    v[i]=1000000001;
    if(st!=dr)
    {
        int mid=(st+dr)/2;
        build(i*2,st,mid);build(i*2+1,mid+1,dr);
    }
}
void update(int i,int st,int dr,int val,int poz)
{
    if(st==dr) v[i]=val;
    else
    {
        int mid=(st+dr)/2;
        if(st<=poz&&poz<=mid) update(i*2,st,mid,val,poz);
        else update(i*2+1,mid+1,dr,val,poz);
        v[i]=min(v[i*2],v[i*2+1]);
    }
}
void quarry(int i,int st,int dr,int a,int b,int y)
{
    if(ok!=-1) return;
    if(st==dr){if(v[i]<=y&&a<=st&&st<=b) ok=st; return;}
    int mid=(st+dr)/2;
    if(!(a<=st&&dr<=b))
    {
        if(a<=mid) quarry(i*2,st,mid,a,b,y);
        if(ok!=-1) return;
        if(mid+1<=b) quarry(i*2+1,mid+1,dr,a,b,y);
    }
    if(v[2*i]<=y)
    {
        quarry(i*2,st,mid,a,b,y);
        return;
    }
    if(v[2*i+1]<=y) quarry(i*2+1,mid+1,dr,a,b,y);
}
int main(){
    fin>>n>>q;
    build(1,1,n);
    for(;q--;)
    {
        fin>>c;fin>>a>>b;///a stop b copil
        if(c=='M') update(1,1,n,a,b);
        if(c=='D')
        {
            ok=-1;
            quarry(1,1,n,b,n,a);
            fout<<ok<<"\n";
        }
        //for(int i=1;i<=2*n-1;i++) fout<<v[i]<<" ";
        //fout<<"\n";
    }
    return 0;
}

• Subtask 1: 60 / 140