oj.uz

Submission #633203

# Submission time Handle Problem Language Result Execution time Memory
633203 2022-08-21T22:21:36 Z Iwanttobreakfree Deda (COCI17_deda) C++17
140 / 140
 408 ms 10128 KB 
#include <iostream>
#include <vector>
using namespace std;
#define int long long
void pupd(int n,int l,int r,vector<int>& t,int a,int x){
    if(l>a||r<a)return;
    if(l==r&&l==a)t[n]=x;
    else{
        int mid=(r+l)/2;
        pupd(n<<1,l,mid,t,a,x);
        pupd((n<<1)+1,mid+1,r,t,a,x);
        t[n]=min(t[n<<1],t[(n<<1)+1]);
    }
}
int find_child(int n,int l,int r,vector<long long>& t,int a,int x){
    if(r<a||t[n]>x)return 1e18;
    if(l==r&&t[n]<=x)return l;
    int mid=(r+l)/2;
    int ans1=find_child(n<<1,l,mid,t,a,x);
    if(ans1!=1e18)return ans1;
    int ans2=find_child((n<<1)+1,mid+1,r,t,a,x);
    return ans2;
}
signed main(){
    int n,q,x,y;
    cin>>n>>q;
    char c;
    vector<int> t(4*n,1e18);
    while(q--){
        cin>>c>>x>>y;
        y--;
        if(c=='M')pupd(1,0,n-1,t,y,x);
        else {
            int ans=find_child(1,0,n-1,t,y,x);
            if(ans==1e18)cout<<-1<<'\n';
            else cout<<ans+1<<'\n';
        }
    }
}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 8 ms 340 KB Output is correct
4 Correct 408 ms 7628 KB Output is correct
5 Correct 348 ms 6876 KB Output is correct
6 Correct 380 ms 8544 KB Output is correct
7 Correct 398 ms 10128 KB Output is correct