oj.uz

Submission #102797

# Submission time Handle Problem Language Result Execution time Memory
102797 2019-03-27T14:40:09 Z Nnandi Deda (COCI17_deda) C++14
140 / 140
 442 ms 8676 KB 
#include <bits/stdc++.h>
using namespace std;

const int maxn = 200005;

int t[maxn];
int fa[maxn*8];

int n, q;

void epit(int hol, int tol, int ig) {
    if(tol == ig) {
        fa[hol] = tol;
        return;
    }
    int mid = (tol + ig) / 2;
    epit(hol*2,tol,mid);
    epit(hol*2+1,mid+1,ig);
    fa[hol] = (t[fa[hol*2]] < t[fa[hol*2+1]] ? fa[hol*2] : fa[hol*2+1]);
    return;
}

void allit(int hol, int tol, int ig, int cel, int x) {
    if(tol == ig) {
        t[tol] = x;
        return;
    }
    int mid = (tol + ig) / 2;
    if(cel <= mid) allit(hol*2,tol,mid,cel,x);
    else allit(hol*2+1,mid+1,ig,cel,x);
    fa[hol] = (t[fa[hol*2]] < t[fa[hol*2+1]] ? fa[hol*2] : fa[hol*2+1]);
    return;
}

int kiaz(int hol, int tol, int ig, int idos, int y) {
    if(tol == ig) {
        return (idos <= tol && t[tol] <= y ? tol : -2);
    }
    if(ig < idos) {
        return -2;
    }
    if(tol <= idos && idos <= ig) {
        int mid = (tol + ig) / 2;
        int res = kiaz(hol*2,tol,mid,idos,y);
        if(res != -2) return res;
        if(t[fa[hol*2 + 1]] > y) return -2;
        return kiaz(hol*2+1,mid+1,ig,idos,y);
    }
    int mid = (tol + ig) / 2;
    if(t[fa[hol*2]] <= y) {
        return kiaz(hol*2,tol,mid,idos,y);
    }
    if(t[fa[hol*2 + 1]] > y) return -2;
    return kiaz(hol*2+1,mid+1,ig,idos,y);
}



void setup() {
    for(int i=0;i<n;i++) {
        t[i] = INT_MAX;
    }
    epit(1,0,n-1);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>q;
    setup();
    vector<int> sol;
    for(int i=0;i<q;i++) {
        char ez;
        cin>>ez;
        if(ez == 'M') {
            int x, a;
            cin>>x>>a;
            allit(1,0,n-1,a-1,x);
        }
        else {
            int y, b;
            cin>>y>>b;
            sol.push_back(kiaz(1,0,n-1,b-1,y) + 1);
        }
    }
    for(int d:sol) {
        cout<<d<<endl;
    }
    return 0;
}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 13 ms 440 KB Output is correct
4 Correct 442 ms 8676 KB Output is correct
5 Correct 295 ms 6480 KB Output is correct
6 Correct 325 ms 8044 KB Output is correct
7 Correct 353 ms 8592 KB Output is correct