oj.uz

답안 #791921

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
791921 2023-07-24T12:34:09 Z Trent Growing Trees (BOI11_grow) C++17
100 / 100
 254 ms 7160 KB 
#include "bits/stdc++.h"

using namespace std;
#define forR(i, a) for(int i=0; (i) < (a); ++(i))
#define REP(i, a, b) for(int i=(a); (i) < (b); ++(i))
#define open(x) freopen(((string) x + ".in").c_str(), "r", stdin); freopen(((string) x + ".out").c_str(), "w", stdout);
#define boost() cin.sync_with_stdio(0); cin.tie(0)
#define all(a) (a).begin(), (a).end()
typedef long long ll;

const int MN = 1e5 + 10, ME = 4 * MN, INF=1e8;

struct node{
    int l, r, lz;
};
node seg[ME];
int a[MN];
void push(int v){
    if(2*v+1 < ME){
        seg[2*v].l += seg[v].lz;
        seg[2*v+1].l += seg[v].lz;
        seg[2*v].r += seg[v].lz;
        seg[2*v+1].r += seg[v].lz;
        seg[2*v].lz += seg[v].lz;
        seg[2*v+1].lz += seg[v].lz;
        seg[v].lz = 0;
    }
}
void up(int v){
    seg[v].l = seg[2*v].l;
    seg[v].r = seg[2*v+1].r;
}
void build(int v, int nl, int nr){
    if(nl > nr) return;
    else if(nl == nr) seg[v] = {a[nl], a[nr], 0};
    else {
        int mid = (nl + nr) / 2;
        build(2*v, nl, mid);
        build(2*v+1, mid+1, nr);
        up(v);
    }
}
int las(int v, int nl, int nr, int val){
    push(v);
    if(seg[v].l >= val){
        throw;
    }
    if(nl == nr) return nl;
    else {
        int mid = (nl + nr) / 2;
        if(seg[2*v+1].l < val) return las(2*v+1, mid+1, nr, val);
        else return las(2*v, nl, mid, val);
    }
}
void upd(int v, int nl, int nr, int l, int r){
    push(v);
    if(l > r) return;
    else if(nl == l && nr == r){
        seg[v].l += 1;
        seg[v].r += 1;
        seg[v].lz += 1;
    } else {
        int mid = (nl + nr) / 2;
        upd(2*v, nl, mid, l, min(r, mid));
        upd(2*v+1, mid+1, nr, max(mid+1, l), r);
        up(v);
    }
}
int val(int v, int nl, int nr, int i){
    push(v);
    if(nl == i && nr == i) return seg[v].l;
    else {
        int mid = (nl + nr) / 2;
        if(i <= mid) return val(2*v, nl, mid, i);
        else return val(2*v+1, mid+1, nr, i);
    }
}

signed main(){
    int n, m; cin >> n >> m;
    REP(i, 1, n + 1) cin >> a[i];
    sort(a+1, a+n+1);
    a[0] = -INF;
    build(1,0,n);
    forR(g, m){
        char ins; int p, q;
        cin >> ins >> p >> q;
        if(ins == 'F'){
            int st=las(1,0,n,q)+1;
            if(st > n) continue;
            int fi=min(n, st+p-1);
            int fv=val(1,0,n,fi);
            int j=las(1,0,n,fv);
            // take st...j
            int ex = fi-j;
            int en=las(1,0,n,fv+1);
            // take en-ex+1...en
            upd(1,0,n,st,j);
            upd(1,0,n,en-ex+1,en);
        } else {
            int lef=las(1, 0, n, p)+1, rig=las(1,0,n, q+1);
            cout << rig - lef + 1 << '\n';
        }
        // REP(i, 1, n + 1) cout << val(1,0,n,i) << ' ';
        // cout << '\n';
    }
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 133 ms 6104 KB Output is correct
2 Correct 180 ms 6968 KB Output is correct
3 Correct 152 ms 6748 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 340 KB Output is correct
2 Correct 6 ms 340 KB Output is correct
3 Correct 6 ms 340 KB Output is correct
4 Correct 5 ms 320 KB Output is correct
5 Correct 124 ms 1584 KB Output is correct
6 Correct 162 ms 1880 KB Output is correct
7 Correct 8 ms 724 KB Output is correct
8 Correct 120 ms 1340 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 150 ms 1712 KB Output is correct
2 Correct 149 ms 2048 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 133 ms 1656 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 156 ms 1796 KB Output is correct
2 Correct 161 ms 2020 KB Output is correct
3 Correct 11 ms 840 KB Output is correct
4 Correct 150 ms 2088 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 122 ms 4172 KB Output is correct
2 Correct 171 ms 6736 KB Output is correct
3 Correct 38 ms 2260 KB Output is correct
4 Correct 121 ms 5884 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 136 ms 5864 KB Output is correct
2 Correct 177 ms 6684 KB Output is correct
3 Correct 163 ms 6168 KB Output is correct
4 Correct 39 ms 2296 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 131 ms 6132 KB Output is correct
2 Correct 135 ms 6656 KB Output is correct
3 Correct 154 ms 6840 KB Output is correct
4 Correct 37 ms 2252 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 180 ms 6232 KB Output is correct
2 Correct 166 ms 6532 KB Output is correct
3 Correct 46 ms 6092 KB Output is correct
4 Correct 132 ms 5480 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 162 ms 6356 KB Output is correct
2 Correct 172 ms 7024 KB Output is correct
3 Correct 189 ms 7160 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 254 ms 6848 KB Output is correct