Submission #501335

#	Time	Username	Problem	Language	Result	Execution time	Memory
501335		Ronin13	Deda (COCI17_deda)	C++14	140 / 140	430 ms	7872 KiB

deda

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
#define inf 1e9+1
#define linf 1e18+1
using namespace std;
const int NMAX=200001;
vector<int>t(4*NMAX,inf);

void update(int v,int l,int r,int pos,int val){
    if(l==r){
        t[v]=val;
        return;
    }
    int m=(l+r)/2;
    if(pos<=m)update(2*v,l,m,pos,val);
    if(pos>m)update(2*v+1,m+1,r,pos,val);
    t[v]=min(t[2*v],t[2*v+1]);
}

int getpos(int v,int l,int r,int st,int fin,int val){
    if(l>fin||r<st)return -1;
    if(l>=st&&r<=fin){
        if(t[v]>val)return -1;
        int li=l,ri=r;
        while(li<ri){
            int mid=(li+ri)/2;
            if(t[2*v]<=val)v*=2,ri=mid;
            else v=v*2+1,li=mid+1;
        }
        return li;
    }
    int mid=(l+r)/2;
    int x=getpos(2*v,l,mid,st,fin,val);
    if(x!=-1)return x;
    else return getpos(2*v+1,mid+1,r,st,fin,val);
}

void solve(){
    int n,m;cin>>n>>m;
    while(m--){
        char c;cin>>c;
        if(c=='M'){
            int pos,val;
            cin>>val>>pos;
            update(1,1,n,pos,val);
        }
        else{
            int b,y;cin>>y>>b;
            cout<<getpos(1,1,n,b,b+n,y)<<"\n";
        }
    }
}

int main(){
    int test=1;//cin>>test;
    while(test--)solve();
    return 0;
}

• Subtask 1: 140 / 140