Submission #82332

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
82332	2018-10-30T02:34:39 Z	Leonardo_Paes	Deda (COCI17_deda)	C++11	140 / 140	444 ms	5696 KB

deda

#include <bits/stdc++.h>

using namespace std;

#define MAXN 200100

int vet[MAXN], tree[4*MAXN];

void update(int node, int l, int r, int idx, int val){

    if(idx<l or idx>r){
        return;
    }

    if(l==idx and r==idx){
        tree[node]=val;
        return;
    }
    int mid = (l+r)>>1;

    update(2*node, l, mid, idx, val);
    update(2*node+1, mid+1, r, idx, val);
    tree[node] = min(tree[2*node], tree[2*node+1]);
}

int query(int node, int tl, int tr, int l, int val){

    if(l > tr){
        return 0x3f3f3f3f;
    }

    if(tree[node]>val){
        return 0x3f3f3f3f;
    }

    if(tl==tr){
        return tl;
    }

    int mid = (tl+tr) >> 1;

    int p1 = query(2*node, tl, mid, l, val);

    if(p1 == 0x3f3f3f3f){
        return query(2*node+1, mid+1, tr, l, val);
    }
    return p1;
}
int n, q;
int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    cin >> n >> q;

    // build

    memset(vet, 0x3f3f3f3f, sizeof vet);
    memset(tree, 0x3f3f3f3f, sizeof tree);

    for(int i=1; i<=q; i++){
        char o;

        cin >> o;

        if(o=='M'){
            int x, a;

            cin >> x >> a;

            update(1, 1, n, a, x);
        }
        if(o=='D'){
            int y, b;

            cin >> y >> b;

            int ans = query(1, 1, n, b, y);

            if(ans==0x3f3f3f3f){
                cout << -1 << endl;
            }
            else{
                cout << query(1, 1, n, b, y) << endl;
            }
        }
    }
    return 0;
}

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	4188 KB	Output is correct
2	Correct	6 ms	4348 KB	Output is correct
3	Correct	14 ms	4452 KB	Output is correct
4	Correct	444 ms	5696 KB	Output is correct
5	Correct	350 ms	5696 KB	Output is correct
6	Correct	370 ms	5696 KB	Output is correct
7	Correct	392 ms	5696 KB	Output is correct