Submission #862211

#	Time	Username	Problem	Language	Result	Execution time	Memory
862211		RobBobBob	Deda (COCI17_deda)	C++14	140 / 140	82 ms	6988 KiB

deda

#include <bits/stdc++.h>

using namespace std;

const int inf = 1024*1024*1024;

struct aint
{
    int nxtp2(int n)
    {
        int p=1;
        while(p<n)p*=2;
        return p;
    }
    int offset;
    int *data;
    aint(int n)
    {
        offset=nxtp2(n);
        data=new int[offset*2];
        for(int i=0;i<offset;i++)
        {
            data[offset+i]=inf;
        }
        init(0,offset-1,1);
    }
    void init(int st,int dr,int node)
    {
        if(st==dr)return;
        else
        {
            int mid=(st+dr)/2;
            init(st,mid,node*2);
            init(mid+1,dr,node*2+1);
            data[node]=min(data[node*2],data[node*2+1]);
        }
    }
    void update(int poz,int val)
    {
        data[offset+poz]=val;
        for(poz=(poz+offset)/2;poz>0;poz/=2)
        data[poz]=min(data[poz*2],data[poz*2+1]);
    }
    int _cb(int l,int x,int &minn,int st,int dr,int node)
    {
        //cerr<<st<<' '<<dr<<'\n';
        if(dr<l)return dr;
        if(l<=st&&min(minn,data[node])>x)
        {
            minn=min(data[node],minn);
            return dr;
        }
        if(st==dr)return st-1;
        int mid=(st+dr)/2;
        int res = _cb(l,x,minn,st,mid,node*2);
        if(res<mid)return res;
        return _cb(l,x,minn,mid+1,dr,node*2+1);
    }
    int cb(int l,int x)
    {
        int minn=inf;
        return _cb(l,x,minn,0,offset-1,1);
    }
    void debug()
    {
        cerr<<data[1]<<'\n';
        cerr<<data[2]<<' '<<data[3]<<'\n';
        cerr<<data[4]<<' '<<data[5]<<' '<<data[6]<<' '<<data[7]<<'\n';
    }
};

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,q;cin>>n>>q;
    aint root = aint(n);
    for(int i=0;i<q;i++)
    {
        //root.debug();
        char c;int a,b;
        cin>>c;cin>>a>>b;
        if(c=='M')
        {
            root.update(b-1,a);
        }
        else
        {
            int res = root.cb(b-1,a);
            if(res+1==root.offset)cout<<"-1\n";
            else cout<<res+2<<'\n';
        }
    }
}

• Subtask 1: 140 / 140