Submission #136846

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
136846	2019-07-26T10:55:18 Z	KCSC	Deda (COCI17_deda)	C++14	140 / 140	868 ms	8080 KB

deda

#include <bits/stdc++.h>
using namespace std;

const int DIM = 200005;
const int INF = 0x3f3f3f3f;

int sgt[DIM * 4];

void update(int nd, int le, int ri, int ps, int vl) {
    if (le == ri)
        sgt[nd] = vl;
    else {
        int md = (le + ri) / 2;
        if (ps <= md)
            update(nd * 2, le, md, ps, vl);
        else
            update(nd * 2 + 1, md + 1, ri, ps, vl);
        sgt[nd] = min(sgt[nd * 2], sgt[nd * 2 + 1]);
    }
}

int query2(int nd, int le, int ri, int vl) {
    if (sgt[nd] > vl)
        return INF;
    if (le == ri)
        return le;
    else {
        int md = (le + ri) / 2;
        int val = query2(nd * 2, le, md, vl);
        if (val == INF)
            val = query2(nd * 2 + 1, md + 1, ri, vl);
        return val;
    }
}

int query(int nd, int le, int ri, int st, int en, int vl) {
    if (en < le || ri < st || sgt[nd] > vl)
        return INF;
    if (st <= le && ri <= en)
        return query2(nd, le, ri, vl);
    else {
        int md = (le + ri) / 2;
        int val = query(nd * 2, le, md, st, en, vl);
        if (val == INF)
            val = query(nd * 2 + 1, md + 1, ri, st, en, vl);
        return val;
    }
}

int main(void) {
 //   freopen("deda.in", "r", stdin);
 //   freopen("deda.out", "w", stdout);
    int n, q;
    cin >> n >> q;
    memset(sgt, INF, sizeof sgt);
    for (int i = 1; i <= q; ++i) {
        char t; int a, b;
        cin >> t >> a >> b;
        if (t == 'M')
            update(1, 1, n, b, a);
        else {
            int val = query(1, 1, n, b, n, a);
            if (val == INF)
                val = -1;
            cout << val << "\n";
        }
    }
    return 0;
}

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	3580 KB	Output is correct
2	Correct	6 ms	3448 KB	Output is correct
3	Correct	20 ms	3576 KB	Output is correct
4	Correct	868 ms	8080 KB	Output is correct
5	Correct	679 ms	7724 KB	Output is correct
6	Correct	746 ms	8068 KB	Output is correct
7	Correct	768 ms	7952 KB	Output is correct