Submission #141584

#	Time	Username	Problem	Language	Result	Execution time	Memory
141584		SeekingOblivion	Deda (COCI17_deda)	C++14	80 / 140	691 ms	3736 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[400001],a,b,n,q;
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]);
    }
}
int quarry(int i,int st,int dr,int a,int b,int y)
{
    if(st==dr){if(v[i]>y) return -1; return st;}
    int mid=(st+dr)/2;
    if(!(a<=st&&dr<=b))
    {
        int val=-1;
        if(a<=mid) val=quarry(i*2,st,mid,a,b,y);
        if(val!=-1) return val;
        if(mid+1<=b) val=quarry(i*2+1,mid+1,dr,a,b,y);
        return val;
    }
    if(v[2*i]<=y) return quarry(i*2,st,mid,a,b,y);
    if(v[2*i+1]<=y) return quarry(i*2+1,mid+1,dr,a,b,y);
    return -1;
}
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') fout<<quarry(1,1,n,b,n,a)<<"\n";
        //for(int i=1;i<=2*n-1;i++) fout<<v[i]<<" ";
        //fout<<"\n";
    }
    return 0;
}

• Subtask 1: 80 / 140