Submission #141584

# Submission time Handle Problem Language Result Execution time Memory
141584 2019-08-08T13:06:31 Z SeekingOblivion Deda (COCI17_deda) C++14
80 / 140
691 ms 3736 KB
#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;
}
# Verdict Execution time Memory Grader output
1 Correct 2 ms 308 KB Output is correct
2 Correct 4 ms 252 KB Output is correct
3 Correct 18 ms 428 KB Output is correct
4 Runtime error 5 ms 2808 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Correct 691 ms 3736 KB Output is correct
6 Runtime error 5 ms 2680 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 5 ms 2684 KB Execution killed with signal 11 (could be triggered by violating memory limits)