Submission #117306

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
117306	2019-06-15T13:13:25 Z	FutymyClone	Deda (COCI17_deda)	C++14	60 / 140	1000 ms	2944 KB

deda

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 5;

int n, q;

struct SegmentTree {
    int node[N << 2];
    void init (int i, int l, int r) {
        if (l == r) {
            node[i] = 1e9;
            return;
        }

        int mid = l + r >> 1;
        init(i << 1, l, mid);
        init(i << 1 | 1, mid + 1, r);
        node[i] = min(node[i << 1], node[i << 1 | 1]);
    }

    void update (int i, int l, int r, int pos, int val) {
        if (l == r) {
            node[i] = val;
            return;
        }

        int mid = l + r >> 1;
        if (pos <= mid) update(i << 1, l, mid, pos, val);
        else update(i << 1 | 1, mid + 1, r, pos, val);
    }

    int Find (int i, int l, int r, int a, int b, int val) {
        if (l > r || a > r || b < l) return -1;
        if (l == r) {
            if (node[i] <= val) return l;
            return -1;
        }

        if (a <= l && r <= b) {
            if (node[i] <= val) return l;
        }

        int mid = l + r >> 1;
        int res = Find(i << 1, l, mid, a, b, val);
        if (res != -1) return res;
        return Find(i << 1 | 1, mid + 1, r, a, b, val);
    }
} it;

int main(){
    scanf("%d %d", &n, &q); it.init(1, 1, n);
    for (int i = 1; i <= q; i++) {
        char c; getchar();
        scanf("%c", &c);

        if (c == 'M') {
            int x, a;
            scanf("%d %d", &x, &a);
            it.update(1, 1, n, a, x);
        }
        else {
            int y, b;
            scanf("%d %d", &y, &b);
            printf("%d\n", it.Find(1, 1, n, b, n, y));
        }
    }
    return 0;
}

Compilation message

deda.cpp: In member function 'void SegmentTree::init(int, int, int)':
deda.cpp:17:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid = l + r >> 1;
                   ~~^~~
deda.cpp: In member function 'void SegmentTree::update(int, int, int, int, int)':
deda.cpp:29:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid = l + r >> 1;
                   ~~^~~
deda.cpp: In member function 'int SegmentTree::Find(int, int, int, int, int, int)':
deda.cpp:45:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid = l + r >> 1;
                   ~~^~~
deda.cpp: In function 'int main()':
deda.cpp:53:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &q); it.init(1, 1, n);
     ~~~~~^~~~~~~~~~~~~~~~~
deda.cpp:56:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%c", &c);
         ~~~~~^~~~~~~~~~
deda.cpp:60:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d %d", &x, &a);
             ~~~~~^~~~~~~~~~~~~~~~~
deda.cpp:65:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d %d", &y, &b);
             ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1

60.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	256 KB	Output is correct
2	Correct	2 ms	384 KB	Output is correct
3	Correct	8 ms	384 KB	Output is correct
4	Execution timed out	1061 ms	2592 KB	Time limit exceeded
5	Execution timed out	1073 ms	1692 KB	Time limit exceeded
6	Execution timed out	1063 ms	2944 KB	Time limit exceeded
7	Execution timed out	1077 ms	2752 KB	Time limit exceeded