oj.uz

Submission #633202

# Submission time Handle Problem Language Result Execution time Memory
633202 2022-08-21T22:20:23 Z Iwanttobreakfree Deda (COCI17_deda) C++17
80 / 140
 1000 ms 11100 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);
    int ans2=find_child((n<<1)+1,mid+1,r,t,a,x);
    return min(ans1,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
80.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 13 ms 404 KB Output is correct
4 Correct 799 ms 11100 KB Output is correct
5 Execution timed out 1082 ms 4416 KB Time limit exceeded
6 Execution timed out 1062 ms 5968 KB Time limit exceeded
7 Execution timed out 1086 ms 7580 KB Time limit exceeded