oj.uz

Submission #524576

# Submission time Handle Problem Language Result Execution time Memory
524576 2022-02-09T14:54:53 Z ddy888 Growing Trees (BOI11_grow) C++17
0 / 100
 132 ms 5816 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Runtime error 17 ms 5060 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 328 KB Output is correct
2 Correct 3 ms 332 KB Output is correct
3 Runtime error 1 ms 588 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 65 ms 1608 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 832 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 28 ms 4032 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 15 ms 4428 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 15 ms 4548 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 17 ms 5188 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 132 ms 3704 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 23 ms 5816 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -