Submission #555224

#	Time	Username	Problem	Language	Result	Execution time	Memory
555224		new_acc	Deda (COCI17_deda)	C++14	140 / 140	140 ms	8856 KiB

deda

#include<bits/stdc++.h>
#define fi first
#define se second
#define pitem item*
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=1e6+10;
const int SS=1<<19;
const int INFi=2e9;
const ll INFl=1e13;
const ll mod2=998244353;
const ll mod=1e9+7;
const ll mod3=1000696969;
const ll p=70032301;
const ull p2=913;
const int L=20;
int t[N],seg[(SS<<1)+10];
int n,m;
vi pp;
void upd(int a,int ind){
    for(ind+=SS;ind>0;ind>>=1) seg[ind]=min(seg[ind],a);
}
void baz(int a,int b,int p=0,int k=SS-1,int v=1){
    if(p>b or k<a) return;
    if(p>=a and k<=b){
        pp.push_back(v);
        return;
    }
    baz(a,b,p,(p+k)>>1,(v<<1)),baz(a,b,((p+k)>>1)+1,k,(v<<1)+1);
}
int Query1(int x,int v){
    if(v>SS) return v-SS;
    if(seg[(v<<1)]<=x) return Query1(x,(v<<1));
    else return Query1(x,(v<<1)+1);
}
int ans(int a,int b){
    pp.clear();
    baz(b,n);
    for(auto u:pp){
        if(seg[u]<=a) return Query1(a,u);
    }
    return -1;
}
void solve(){
    cin>>n>>m;    
    for(int i=1;i<=(SS<<1);i++) seg[i]=INFi;
    for(int i=1;i<=m;i++){
        int a,b;
        char c;
        cin>>c;
        if(c=='M'){
            cin>>a>>b;
            upd(a,b);
        }else{
            cin>>a>>b;
            cout<<ans(a,b)<<"\n";
        }
    }
}
int main(){
    ios_base::sync_with_stdio(0),cin.tie(0);
    int tt=1;
    while(tt--) solve();
}

• Subtask 1: 140 / 140