oj.uz

Submission #555224

# Submission time Handle Problem Language Result Execution time Memory
555224 2022-04-30T09:47:09 Z new_acc Deda (COCI17_deda) C++14
140 / 140
 140 ms 8856 KB 
#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.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4436 KB Output is correct
2 Correct 3 ms 4436 KB Output is correct
3 Correct 5 ms 4444 KB Output is correct
4 Correct 140 ms 8856 KB Output is correct
5 Correct 109 ms 8364 KB Output is correct
6 Correct 114 ms 8708 KB Output is correct
7 Correct 124 ms 8848 KB Output is correct