oj.uz

Submission #373376

# Submission time Handle Problem Language Result Execution time Memory
373376 2021-03-04T11:15:26 Z Atill83 Deda (COCI17_deda) C++14
100 / 140
 1000 ms 8172 KB 
#include <bits/stdc++.h>
#define ff first
#define ss second
#define endl '\n'
using namespace std;
const long long INF = (long long) 1e18;
const int mod = (int) 1e9+7;
const int MAXN = (int) 2e5+5;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
int n, q;
int t[4*MAXN];
void upd(int v, int tl, int tr, int pos, int coc){
    if(tl == tr){
        t[v] = coc;
    }else{
        int tm = (tl + tr) / 2;
        if(pos <= tm)
            upd(2*v, tl, tm, pos, coc);
        else 
            upd(2*v + 1, tm + 1, tr, pos, coc);
        t[v] = min(t[2*v], t[2*v + 1]);
    }
}


int que(int v, int tl, int tr, int l, int r){
    if(l > r){
        return mod;
    }else if(tl == l && tr == r){
        return t[v];
    }else {
        int tm = (tl + tr) / 2;
        return min(que(2*v, tl, tm, l, min(tm, r)), que(2*v + 1, tm + 1, tr, max(tm + 1, l), r));
    }
}




int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);

    #ifdef Local
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/int.txt","r",stdin);
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/out.txt","w",stdout);
    #endif

    cin>>n>>q;

    memset(t, 0x7f, sizeof(t));
    upd(1, 1, n + 1, n + 1, 0);

    set<pii> st;
    while(q--){
        char ty;
        cin>>ty;
        if(ty == 'D'){
            int y, b;
            cin>>y>>b;
            int l = b, r = n + 1;

            while(l < r){
                int m = (l + r) / 2;
                if(que(1, 1, n + 1, b, m) <= y){
                    r = m;
                }else{
                    l = m + 1;
                }
            }

            cout<<(l >= n + 1 ? -1 : l )<<endl;
        }else{
            int x, a;   
            cin>>x>>a;
            upd(1, 1, n + 1, a, x);
        }
    }



    #ifdef Local
        cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

Subtask #1
100.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3436 KB Output is correct
2 Correct 3 ms 3436 KB Output is correct
3 Correct 9 ms 3564 KB Output is correct
4 Execution timed out 1089 ms 7628 KB Time limit exceeded
5 Correct 736 ms 7716 KB Output is correct
6 Correct 889 ms 7788 KB Output is correct
7 Execution timed out 1025 ms 8172 KB Time limit exceeded