oj.uz

Submission #349260

# Submission time Handle Problem Language Result Execution time Memory
349260 2021-01-17T09:29:50 Z parsabahrami Growing Trees (BOI11_grow) C++17
100 / 100
 330 ms 3436 KB 
// Call my Name and Save me from The Dark
#include <bits/stdc++.h>
 
using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
 
#define SZ(x)                       (int) x.size()
#define F                           first
#define S                           second

const int N = 1e5 + 10;
int F[N], A[N], n, q;

void upd(int pos, int x) {
    for (; pos < N; pos += pos & -pos) F[pos] += x;
}

int get(int pos) {
    int ret = 0;
    for (; pos; pos -= pos & -pos) ret += F[pos];
    return ret;
}

int Find(int x) {
    int res = 0, sum = 0;
    for (int i = 19; ~i; i--) {
        res += (1 << i);
        if (res < N && sum + F[res] <= x) sum += F[res];
        else res -= (1 << i);
    }
    return res;
}

inline void add(int l, int r) {
    if (r < l) return;
    upd(l, 1), upd(r + 1, -1);
}

void print() {
    for (int i = 1; i <= n; i++) printf("%d ", get(i));
    printf("\n");
}

int main() {
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++) scanf("%d", &A[i]);
    sort(A + 1, A + n + 1);
    for (int i = 1; i <= n; i++) upd(i, A[i]), upd(i + 1, -A[i]);
    upd(n + 1, 2e9);
    //print();
    for (; q; q--) {
        char t; int c, h; cin >> t >> c >> h;
        if (t == 'F') {
            int l = Find(h - 1) + 1;
            c = min(c, n + 1 - l);
            int x = get(l + c - 1);
            int r = Find(x - 1); r = max(r, l - 1);
            add(l, r);
            int b = Find(x);
            //printf("l %d r %d x %d b %d\n", l, r, x, b);
            add(b - (l + c - 1 - r) + 1, b);
            //print();
        } else {
            printf("%d\n", Find(h) - Find(c - 1));
        }
    }
    return 0;
}

Compilation message

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 2412 KB Output is correct
2 Correct 203 ms 2796 KB Output is correct
3 Correct 111 ms 2668 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 364 KB Output is correct
2 Correct 11 ms 364 KB Output is correct
3 Correct 11 ms 492 KB Output is correct
4 Correct 8 ms 364 KB Output is correct
5 Correct 219 ms 1516 KB Output is correct
6 Correct 299 ms 1772 KB Output is correct
7 Correct 10 ms 492 KB Output is correct
8 Correct 234 ms 1388 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 275 ms 1772 KB Output is correct
2 Correct 268 ms 1900 KB Output is correct
3 Correct 4 ms 364 KB Output is correct
4 Correct 261 ms 1516 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 2016 KB Output is correct
2 Correct 295 ms 1772 KB Output is correct
3 Correct 8 ms 492 KB Output is correct
4 Correct 273 ms 1900 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 2048 KB Output is correct
2 Correct 193 ms 2284 KB Output is correct
3 Correct 63 ms 876 KB Output is correct
4 Correct 90 ms 2284 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 2028 KB Output is correct
2 Correct 207 ms 2412 KB Output is correct
3 Correct 110 ms 2540 KB Output is correct
4 Correct 62 ms 876 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 2204 KB Output is correct
2 Correct 180 ms 2460 KB Output is correct
3 Correct 109 ms 2668 KB Output is correct
4 Correct 62 ms 876 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 2924 KB Output is correct
2 Correct 195 ms 2284 KB Output is correct
3 Correct 41 ms 1900 KB Output is correct
4 Correct 193 ms 2196 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 2540 KB Output is correct
2 Correct 226 ms 2756 KB Output is correct
3 Correct 117 ms 3052 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 330 ms 3436 KB Output is correct