oj.uz

Submission #77274

# Submission time Handle Problem Language Result Execution time Memory
77274 2018-09-24T15:23:43 Z FutymyClone Growing Trees (BOI11_grow) C++14
100 / 100
 607 ms 41324 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;

int n, q, a[N];

struct seg {
    struct Node {
        int Min, Max;
    } node[4 * N];

    int lazy[4 * N];
    void init (int i, int l, int r) {
        if (l == r) {
            node[i].Min = node[i].Max = a[l];
            lazy[i] = 0;
            return;
        }

        int m = (l + r) >> 1;
        init(i << 1, l, m);
        init(i << 1 | 1, m + 1, r);

        node[i].Min = min(node[i << 1].Min, node[i << 1 | 1].Min);
        node[i].Max = max(node[i << 1].Max, node[i << 1 | 1].Max);
        lazy[i] = 0;
    }

    void dolazy (int i, int l, int r) {
        if (lazy[i]) {
            node[i].Min += lazy[i];
            node[i].Max += lazy[i];
            if (l != r) {
                lazy[i << 1] += lazy[i];
                lazy[i << 1 | 1] += lazy[i];
            }

            lazy[i] = 0;
        }
    }

    void update (int i, int l, int r, int a, int b, int val) {
        dolazy(i, l, r);
        if (l > r || a > r || b < l) return;
        if (a <= l && r <= b) {
            node[i].Min += val;
            node[i].Max += val;
            if (l != r) {
                lazy[i << 1] += val;
                lazy[i << 1 | 1] += val;
            }

            return;
        }

        int m = (l + r) >> 1;
        update(i << 1, l, m, a, b, val);
        update(i << 1 | 1, m + 1, r, a, b, val);

        node[i].Min = min(node[i << 1].Min, node[i << 1 | 1].Min);
        node[i].Max = max(node[i << 1].Max, node[i << 1 | 1].Max);
    }

    int get_min (int i, int l, int r, int a, int b) {
        if (l > r || a > r || b < l) return (int)2e9 + 2277;
        dolazy(i, l, r);
        if (a <= l && r <= b) return node[i].Min;

        int m = (l + r) >> 1;
        return min(get_min(i << 1, l, m, a, b), get_min(i << 1 | 1, m + 1, r, a, b));
    }

    int get_max (int i, int l, int r, int a, int b) {
        if (l > r || a > r || b < l) return 0;
        dolazy(i, l, r);
        if (a <= l && r <= b) return node[i].Max;

        int m = (l + r) >> 1;
        return max(get_max(i << 1, l, m, a, b), get_max(i << 1 | 1, m + 1, r, a, b));
    }

    int Find_min (int i, int l, int r, int val) {
        dolazy(i, l, r);
        if (l == r) {
            if (node[i].Min >= val) return l;
            return -1;
        }

        int m = (l + r) >> 1;
        int lef = get_max(1, 1, n, 1, m);
        if (lef >= val) return Find_min(i << 1, l, m, val);
        return Find_min(i << 1 | 1, m + 1, r, val);
    }

    int Find_max (int i, int l, int r, int val) {
        dolazy(i, l, r);
        if (l == r) {
            if (node[i].Max <= val) return l;
            return -1;
        }

        int m = (l + r) >> 1;
        int rig = get_min(1, 1, n, m + 1, n);
        if (rig <= val) return Find_max(i << 1 | 1, m + 1, r, val);
        return Find_max(i << 1, l, m, val);
    }
} it;

int main(){
    scanf("%d %d", &n, &q);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    sort(a + 1, a + n + 1);
    it.init(1, 1, n);

    while (q--) {
        getchar();
        char c = getchar();
        int l, r;
        scanf("%d %d", &l, &r);

        if (c == 'F') {
            int pos = it.Find_min(1, 1, n, r);
            if (pos == -1) continue;
            if (pos + l - 1 >= n) {
                it.update(1, 1, n, pos, n, 1);
                continue;
            }

            int lastval = it.get_max(1, 1, n, pos, pos + l - 1);
            int lastpos = it.Find_min(1, 1, n, lastval);
            int nxtpos = it.Find_max(1, 1, n, lastval);
            int diff = lastpos - pos;

            it.update(1, 1, n, pos, lastpos - 1, 1);
            it.update(1, 1, n, nxtpos - (l - diff) + 1, nxtpos, 1);
        }
        else {
            int pos = it.Find_min(1, 1, n, l);
            int lastpos = it.Find_max(1, 1, n, r);

            if (pos == -1 || lastpos == -1) printf("%d\n", 0);
            else printf("%d\n", lastpos - pos + 1);
        }
    }
    return 0;
}

/*
5 7
1 3 2 5 2
F 2 1
C 3 6
F 2 3
C 6 8
F 2 1
F 2 2
C 3 5
*/

Compilation message

grow.cpp: In function 'int main()':
grow.cpp:112:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &q);
     ~~~~~^~~~~~~~~~~~~~~~~
grow.cpp:113:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
                                  ~~~~~^~~~~~~~~~~~~
grow.cpp:121:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &l, &r);
         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 293 ms 5240 KB Output is correct
2 Correct 509 ms 7084 KB Output is correct
3 Correct 197 ms 8496 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8496 KB Output is correct
2 Correct 7 ms 8496 KB Output is correct
3 Correct 8 ms 8496 KB Output is correct
4 Correct 5 ms 8496 KB Output is correct
5 Correct 180 ms 8496 KB Output is correct
6 Correct 230 ms 8496 KB Output is correct
7 Correct 16 ms 8496 KB Output is correct
8 Correct 127 ms 8496 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 9240 KB Output is correct
2 Correct 245 ms 10244 KB Output is correct
3 Correct 5 ms 10244 KB Output is correct
4 Correct 155 ms 11048 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 12168 KB Output is correct
2 Correct 256 ms 13100 KB Output is correct
3 Correct 31 ms 13100 KB Output is correct
4 Correct 229 ms 14312 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 307 ms 16752 KB Output is correct
2 Correct 446 ms 19620 KB Output is correct
3 Correct 59 ms 19620 KB Output is correct
4 Correct 132 ms 21064 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 421 ms 22384 KB Output is correct
2 Correct 444 ms 23596 KB Output is correct
3 Correct 167 ms 25008 KB Output is correct
4 Correct 60 ms 25008 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 346 ms 26620 KB Output is correct
2 Correct 309 ms 27772 KB Output is correct
3 Correct 161 ms 29232 KB Output is correct
4 Correct 59 ms 29232 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 488 ms 31424 KB Output is correct
2 Correct 459 ms 32736 KB Output is correct
3 Correct 77 ms 33148 KB Output is correct
4 Correct 371 ms 34492 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 405 ms 35740 KB Output is correct
2 Correct 484 ms 37244 KB Output is correct
3 Correct 607 ms 38932 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 400 ms 41324 KB Output is correct