Submission #136621

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
136621	2019-07-25T21:44:36 Z	mariusnicoli	Deda (COCI17_deda)	C++14	140 / 140	875 ms	9080 KB

deda

#include <iostream>
#define INF 1000000001
using namespace std;

struct nod {
    int minim;
    int poz;
};

nod a[3200001];
int sol, psol, n, q, statie, om;
char c;

void build (int nod, int st, int dr) {
    if (st == dr) {
        a[nod].minim = INF;
        a[nod].poz = st;
    } else {
        int mid = (st+dr)/2;
        build(2*nod, st, mid);
        build(2*nod+1, mid+1, dr);

        if (a[2*nod].minim <= a[2*nod+1].minim)
            a[nod] = a[2*nod];
        else
            a[nod] = a[2*nod+1];
    }
}

int update(int nod, int st, int dr, int poz, int value) {
    if (st == dr) {
        a[nod].minim = value;
        a[nod].poz = st;
    } else {
        int mid = (st + dr)/2;
        if (poz <= mid)
            update(2*nod, st, mid, poz, value);
        else
            update(2*nod+1, mid+1, dr, poz, value);

        if (a[2*nod].minim <= a[2*nod+1].minim)
            a[nod] = a[2*nod];
        else
            a[nod] = a[2*nod+1];
    }
}

/// cea mai mica pozitie din intervalul a,b cu valoarea
/// mai mica sau egala cu value
void query(int nod, int st, int dr, int A, int B, int value) {
    if (sol != INF)
        return;
    if (st == dr && a[nod].minim <= value && sol == INF) {
        sol = a[nod].minim;
        psol = a[nod].poz;
        return;
    }

    if (A <= st && dr <= B) {
        if (a[nod].minim <= value) {
            int mid = (st+dr)/2;
            if (a[2*nod].minim <= value)
                query(2*nod, st, mid, A, B, value);
            else
                query(2*nod+1, mid+1, dr, A, B, value);
        }
    } else {
        int mid = (st+dr)/2;
        if (A <= mid)
            query(2*nod, st, mid, A, B, value);
        if (B > mid)
            query(2*nod+1, mid+1, dr, A, B, value);
    }
}

int main () {
    cin>>n>>q;
    build(1, 1, n);
    ///cout<<a[1].poz;
    for (;q--;) {
        cin>>c>>statie>>om;
        if (c == 'M')
            update(1, 1, n, om, statie);
        else {
            sol = INF;
            query(1, 1, n, om, n, statie);
            if (sol > statie)
                cout<<"-1\n";
            else
                cout<<psol<<"\n";
        }
    }
    return 0;
}

Compilation message

deda.cpp: In function 'int update(int, int, int, int, int)':
deda.cpp:46:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	3 ms	376 KB	Output is correct
3	Correct	18 ms	376 KB	Output is correct
4	Correct	875 ms	9080 KB	Output is correct
5	Correct	690 ms	6520 KB	Output is correct
6	Correct	755 ms	8796 KB	Output is correct
7	Correct	798 ms	8960 KB	Output is correct