Submission #349260

#	Time	Username	Problem	Language	Result	Execution time	Memory
349260		parsabahrami	Growing Trees (BOI11_grow)	C++17	100 / 100	330 ms	3436 KiB

grow

// 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 (stderr)

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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10