oj.uz

Submission #919047

# Submission time Handle Problem Language Result Execution time Memory
919047 2024-01-31T06:39:44 Z vjudge1 Deda (COCI17_deda) C++17
140 / 140
 78 ms 8020 KB 
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define sp << " " << 
//#define int long long
#define vi vector<int>
#define pb push_back
#define flag {cout << "OK\n";return;}
#define F(xxx,yyy) for (int xxx=1;xxx<=yyy;xxx++)
#define pii pair<int,int>
const int N = 2e5+1, inf = 1e9+1, MOD = 1e9+7;

struct ST {
    vector<int> t;
    int n;
    ST(int nn) {
        n = nn;
        t.assign(4*n+1,inf);
    }
    int walk(int node,int l,int r,int x) {
        if (t[node] > x) return -1;
        if (l == r) return l;
        int m = (l+r) >> 1;
        if (t[2*node] <= x) return walk(2*node,l,m,x);
        return walk(2*node+1,m+1,r,x);
    }
    int query(int node,int l,int r,int L,int R,int x) {
        // cout << l sp r sp L sp R << endl;
       // if (l == r) cout << "v[" << l << "]" << "=" << t[node] << endl;
        if (l >= L && r <= R) {
            int w = walk(node,l,r,x);
            if (w == -1) return inf;
            return w;
        };
        int m = (l+r) >> 1;
        if (m >= L){
            int y = query(2*node,l,m,L,R,x);
            if (y != inf) return y;
        }
        if (m+1 <= R) {
            return query(2*node+1,m+1,r,L,R,x);
        }
        return inf;
    } 
    void update(int node,int l,int r,int p,int v) {
        if (l == r) {
            t[node] = v;
            return;
        } 
        int m = (l+r) >> 1;
        if (p <= m) update(2*node,l,m,p,v);
        else update(2*node+1,m+1,r,p,v);
        t[node] = min(t[2*node],t[2*node+1]);
    }
};

void solve() {
    int n,q;
    cin >> n >> q;
    ST t(n);
    while (q--) {
        char type;
        cin >> type;
        if (type == 'M') {
            int v,p;
            cin >> v >> p;
            t.update(1,1,n,p,v);
        }
        else {
            int v,l;
            cin >> v >> l;
            int vv = t.query(1,1,n,l,n,v);
            cout << ((vv == inf)?-1:vv) << '\n';
        }
    }
}
    
                 
                             
signed main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef Local    
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t; 
	while (t --> 0) solve();
}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 78 ms 8020 KB Output is correct
5 Correct 68 ms 5968 KB Output is correct
6 Correct 73 ms 6996 KB Output is correct
7 Correct 77 ms 7952 KB Output is correct