Submission #524576

#	Time	Username	Problem	Language	Result	Execution time	Memory
524576		ddy888	Growing Trees (BOI11_grow)	C++17	0 / 100	132 ms	5816 KiB

grow

#undef _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long 
#define pb push_back
#define fi first
#define si second
#define ar array
typedef pair<int,int> pi;
typedef tuple<int,int,int> ti;  
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {cerr << " " << to_string(H);debug_out(T...);}
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)

int N, M, A[100010];

int fw[100010], fw2[100010];

void update(int x, int y, int v) { 
    for (int tx=x; tx <= N; tx += tx&(-tx)) fw[tx] += v, fw2[tx] -= v*(x-1);
    for (int ty=y+1; ty <= N; ty += ty&(-ty)) fw[ty] -= v, fw2[ty] += v*y; 
}
int sum (int x) {
    int res = 0;
    for (int tx=x; tx; tx -= tx&(-tx)) res += fw[tx]*x + fw2[tx];
    return res;
}
int range_sum(int x, int y) { 
    return sum(y)-sum(x-1);
}

void apply(int c, int h) {
    int lo = 0, hi = N + 1;
    while (lo + 1 < hi) {
        int mid = (lo + hi) / 2;
        if (range_sum(mid, mid) >= h) hi = mid;
        else lo = mid;
    }
    int lx = hi; // leftmost >= h
    int target = range_sum(lx + c - 1, lx + c - 1);

    lo = 0, hi = N + 1;
    while (lo + 1 < hi) {
        int mid = (lo + hi) / 2;
        if (range_sum(mid, mid) >= target) hi = mid;
        else lo = mid;
    }
    int mx = hi;
    update(lx, mx - 1, 1);
    // debug(lx, mx - 1);

    lo = 0, hi = N + 1;
    while (lo + 1 < hi) {
        int mid = (lo + hi) / 2;
        if (range_sum(mid, mid) <= target) lo = mid;
        else hi = mid;
    }
    int rx = lo;
    int cnt = lo - (lx + c - 1) + 1;
    update(mx + cnt - 1, rx, 1);
    // debug(rx);
}

void get(int mn, int mx) {
    int lo = 0, hi = N + 1;
    while (lo + 1 < hi) {
        int mid = (lo + hi) / 2;
        if (range_sum(mid, mid) >= mn) hi = mid;
        else lo = mid;
    }
    int lx = hi;
    lo = 0, hi = N + 1;
    while (lo + 1 < hi) {
        int mid = (lo + hi) / 2;
        if (range_sum(mid, mid) <= mx) lo = mid;
        else hi = mid;
    }
    int rx = lo;
    cout << (rx - lx + 1) << '\n';
}

signed main() {
    fast;
    cin >> N >> M;
    for (int i = 1; i <= N; ++i) cin >> A[i];
    sort(A + 1, A + 1 + N);
    for (int i = 1; i <= N; ++i) update(i, i, A[i]);
    while (M--) {
        char op; int x, y;
        cin >> op >> x >> y;
        if (op == 'F') apply(x, y);
        else get(x, y);
        // for (int i = 1; i <= N; ++i) cout << range_sum(i, i) << ' ';
        // cout << '\n';
        // break;
    }
    return 0;   
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10