Submission #1290641

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290641		saif_ahmed	Deda (COCI17_deda)	C++20	140 / 140	576 ms	5004 KiB

deda

#include <bits/stdc++.h>
using namespace std;
//define
using ll = long long;
using ld = long double;
#define F first
#define S second
#define pb push_back
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define fio freopen("input.txt","r",stdin);freopen("output.txt","w",stdout)
#define serein ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define MT for(int tt=1;tt<=_t;tt++)
#define CP cout<<"Case "<<tt<<": "
template<typename T> void read(vector<T>& v) { for (auto& x : v) cin >> x; }
void yes(bool f) { cout << (f ? "YES" : "NO") << '\n'; }
void Yes(bool f) { cout << (f ? "Yes" : "No") << '\n'; }
//constants
const int M=1e9+7;
const int N=1e6+3;
const int inf=INT_MAX;

class SegTree {
public:
    int n;                    
    vector<int> tree;

    SegTree(int size) { n = size; tree.assign(4 * n, 0LL); }

    void build(int node, int st, int en) {
        if (st == en) { tree[node] = inf; return; }
        int mid = (st + en) / 2;
        build(node * 2, st, mid);
        build(node * 2 + 1, mid + 1, en);
        tree[node] = min(tree[node * 2], tree[node * 2 + 1]);
    }

    int query(int node, int st, int en, int l, int r) {
        if (st > r || en < l) return INT_MAX;
        if (st >= l && en <= r) return tree[node];
        int mid = (st + en) / 2;
        int q1 = query(node * 2, st, mid, l, r);
        int q2 = query(node * 2 + 1, mid + 1, en, l, r);
        return min(q1,q2);
    }

    void update(int node, int st, int en, int idx, int val) {
        if (st == en) { tree[node] = val; return; }
        int mid = (st + en) / 2;
        if (idx <= mid) update(node * 2, st, mid, idx, val);
        else            update(node * 2 + 1, mid + 1, en, idx, val);
        tree[node] = min(tree[node * 2], tree[node * 2 + 1]);
    }
};

void solve(){
    int n, q;
    cin>>n>>q;
    SegTree seg(n);
    seg.build(1,0,n-1);
    while(q--){
        char t;
        cin>>t;
        if(t=='M'){
            int idx; int val;
            cin>>val>>idx;
            idx--;
            seg.update(1, 0, n-1, idx, val);
        }
        else{
            int y, b;
            cin>>y>>b;
            b--;
            int ans = -1;
            int lo = b, hi = n-1;
            while(lo<=hi){
                int m = (lo+hi)/2;
                int mn = seg.query(1,0,n-1, b,m);
                if(mn>y){
                    lo = m+1;
                }
                else{
                    ans = m+1;
                    hi = m-1;
                }
            }
            cout<<ans<<'\n';
        }
    }
}

int main() {
    serein;
    // clock_t z = clock();
    int _t = 1;
    //cin>>_t;
    MT {
        solve();
    }
    // cerr << "Run Time : " << ((double)(clock() - z) / CLOCKS_PER_SEC);
    return 0;
}

• Subtask 1: 140 / 140