oj.uz

Submission #56168

# Submission time Handle Problem Language Result Execution time Memory
56168 2018-07-10T07:16:49 Z 강태규(#1579) Growing Trees (BOI11_grow) C++11
100 / 100
 220 ms 3624 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>

using namespace std;
typedef long long llong;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;

int n, m;
int x[100001];
int seg[1 << 18];
int lay[1 << 18];

void init(int i, int s, int e) {
    if (s == e) {
        seg[i] = lay[i] = x[s];
        return;
    }
    int m = (s + e) / 2;
    init(i << 1, s, m);
    init(i << 1 | 1, m + 1, e);
    seg[i] = max(seg[i << 1], seg[i << 1 | 1]);
}

void update(int i, int s, int e, int x, int y) {
    if (e < x || y < s) return;
    if (x <= s && e <= y) {
        ++seg[i];
        ++lay[i];
        return;
    }
    int m = (s + e) / 2;
    update(i << 1, s, m, x, y);
    update(i << 1 | 1, m + 1, e, x, y);
    seg[i] = max(seg[i << 1], seg[i << 1 | 1]) + lay[i];
}

int find(int i, int s, int e, int h, int v = 0) {
    if (seg[i] + v < h) return n + 1;
    if (s == e) return s;
    int m = (s + e) / 2;
    int ret = find(i << 1, s, m, h, v + lay[i]);
    if (ret <= n) return ret;
    return find(i << 1 | 1, m + 1, e, h, v + lay[i]);
}

int query(int i, int s, int e, int x) {
    if (s == e) return lay[i];
    int m = (s + e) / 2;
    if (x <= m) return query(i << 1, s, m, x) + lay[i];
    return query(i << 1 | 1, m + 1, e, x) + lay[i];
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) scanf("%d", x + i);
    sort(x + 1, x + (n + 1));
    init(1, 1, n);
    while (m--) {
        char in[10]; int x, y;
        scanf("%s%d%d", in, &x, &y);
        if (in[0] == 'F') {
            int s = find(1, 1, n, y);
            if (s == n + 1) continue;
            int e = min(s + x, n + 1);
            x = e - s;
            int l = query(1, 1, n, e - 1);
            int m = find(1, 1, n, l);
            update(1, 1, n, s, m - 1);
            x -= m - s;
            e = find(1, 1, n, l + 1);
            s = e - x;
            update(1, 1, n, s, e - 1);
        }
        else {
            int s = find(1, 1, n, x);
            int e = find(1, 1, n, y + 1);
            printf("%d\n", e - s);
        }
    }
	return 0;
}

Compilation message

grow.cpp: In function 'int main()':
grow.cpp:67:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~
grow.cpp:68: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", x + i);
                                  ~~~~~^~~~~~~~~~~~~
grow.cpp:73:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s%d%d", in, &x, &y);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 2936 KB Output is correct
2 Correct 220 ms 2976 KB Output is correct
3 Correct 162 ms 2976 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2976 KB Output is correct
2 Correct 5 ms 2976 KB Output is correct
3 Correct 5 ms 2976 KB Output is correct
4 Correct 4 ms 2976 KB Output is correct
5 Correct 62 ms 2976 KB Output is correct
6 Correct 86 ms 2976 KB Output is correct
7 Correct 7 ms 2976 KB Output is correct
8 Correct 48 ms 2976 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 2976 KB Output is correct
2 Correct 105 ms 2976 KB Output is correct
3 Correct 3 ms 2976 KB Output is correct
4 Correct 52 ms 2976 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 2976 KB Output is correct
2 Correct 80 ms 2976 KB Output is correct
3 Correct 12 ms 2976 KB Output is correct
4 Correct 71 ms 2976 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 2976 KB Output is correct
2 Correct 156 ms 3180 KB Output is correct
3 Correct 38 ms 3180 KB Output is correct
4 Correct 99 ms 3180 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 3180 KB Output is correct
2 Correct 144 ms 3196 KB Output is correct
3 Correct 135 ms 3196 KB Output is correct
4 Correct 22 ms 3196 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 3260 KB Output is correct
2 Correct 94 ms 3260 KB Output is correct
3 Correct 131 ms 3260 KB Output is correct
4 Correct 23 ms 3260 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 3260 KB Output is correct
2 Correct 156 ms 3260 KB Output is correct
3 Correct 46 ms 3260 KB Output is correct
4 Correct 96 ms 3260 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 3388 KB Output is correct
2 Correct 168 ms 3388 KB Output is correct
3 Correct 213 ms 3388 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 3624 KB Output is correct