Submission #102797

#	Time	Username	Problem	Language	Result	Execution time	Memory
102797		Nnandi	Deda (COCI17_deda)	C++14	140 / 140	442 ms	8676 KiB

deda

#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 / 140