oj.uz

답안 #411512

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
411512 2021-05-25T12:50:23 Z 반딧불(#7604) The short shank; Redemption (BOI21_prison) C++17
0 / 100
 2000 ms 66312 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct Fenwick {
    int n;
    int tree[2000002];
    Fenwick(){}

    void init(int _n){
        n = _n;
    }
    void add(int x, int y){
        while(x <= n){
            tree[x] += y;
            x += x&-x;
        }
    }
    int sum(int x){
        int ret = 0;
        while(x){
            ret += tree[x];
            x -= x&-x;
        }
        return ret;
    }
    int sum(int l, int r){
        return sum(r) - sum(l-1);
    }
} tree;

struct minSegmentTree{
    int tree[8000002], lazy[8000002], minLoc[8000002];

    void init(int i, int l, int r, int* A){
        if(l==r){
            tree[i] = A[l];
            lazy[i] = 0;
            minLoc[i] = l;
            return;
        }
        lazy[i] = 0;
        int m = (l+r)>>1;
        init(i*2, l, m, A);
        init(i*2+1, m+1, r, A);
        if(tree[i*2] <= tree[i*2+1]) tree[i] = tree[i*2], minLoc[i] = minLoc[i*2];
        else tree[i] = tree[i*2+1], minLoc[i] = minLoc[i*2+1];
    }

    void propagate(int i, int l, int r){
        if(!lazy[i]) return;
        tree[i] += lazy[i];
        if(l!=r) lazy[i*2] += lazy[i], lazy[i*2+1] += lazy[i];
        lazy[i] = 0;
    }

    void update(int i, int l, int r, int s, int e, int val){
        propagate(i, l, r);
        if(r<s || e<l) return;
        if(s<=l && r<=e){
            lazy[i] += val;
            propagate(i, l, r);
            return;
        }
        int m = (l+r)>>1;
        update(i*2, l, m, s, e, val);
        update(i*2+1, m+1, r, s, e, val);
        if(tree[i*2] <= tree[i*2+1]) tree[i] = tree[i*2], minLoc[i] = minLoc[i*2];
        else tree[i] = tree[i*2+1], minLoc[i] = minLoc[i*2+1];
    }
} mstree;

int n, k, t;
int arr[2000002];
int lLim[2000002];
int basic;

stack<pair<int, int> > stk;
vector<int> link[2000002];
int par[2000002], depth[2000002], sz[2000002];
int vCount, leafCnt;
vector<int> leaf;
int ans;

void dfs(int x, int d = 0){
    if((int)link[x].size() == 0) depth[x] = d;
    else depth[x] = 1e9;
    sz[x] = 1;
    for(auto y: link[x]){
        dfs(y, d+1);
        sz[x] += sz[y];
    }
}

int main(){
    scanf("%d %d %d", &n, &k, &t);
    for(int i=1; i<=n; i++){
        scanf("%d", &arr[i]);
        if(arr[i] <= t) lLim[i] = -1;
        else{
            while(!stk.empty() && stk.top().first < i) stk.pop();
            if(stk.empty()) basic++, lLim[i] = -1;
            else lLim[i] = stk.top().second;
        }
        if(arr[i] < t){
            int val = i + (t - arr[i]);
            while(!stk.empty() && stk.top().first <= val) stk.pop();
            stk.push(make_pair(val, i));
        }
    }

    while(!stk.empty()) stk.pop();
    stk.push(make_pair(0, ++vCount));
    for(int i=n; i>=1; i--){
        if(lLim[i] == -1) continue;
        while(stk.top().first > i) stk.pop();
        link[stk.top().second].push_back(++vCount);
        par[vCount] = stk.top().second;
        stk.push(make_pair(lLim[i], vCount));
    }

    for(int i=1; i<=vCount; i++){
        if((int)link[i].size() == 0){
            leafCnt++;
            leaf.push_back(i);
        }
    }
    dfs(1);

    int toDelete = max(0, leafCnt - k);
    tree.init(vCount);
    mstree.init(1, 1, vCount, depth);
    ans = vCount - 1;

    for(int i=1; i<=vCount; i++) tree.add(i, 1);

    while(toDelete--){
        int minLoc = -1, minVal = INT_MAX;
        for(auto x: leaf){
            if(!arr[x]) continue;
            int cnt = 0, tmp = x;
            while(tmp != 1 && arr[tmp]){
                cnt++;
                tmp = par[tmp];
            }
            if(minVal > cnt) minVal = cnt, minLoc = x;
        }

        ans -= minVal;
        while(minLoc != 1 && arr[minLoc]){
            arr[minLoc] = 0;
            minLoc = par[minLoc];
        }
    }

//    while(toDelete--){
//        int minLoc = mstree.minLoc[1];
//
//        mstree.update(1, 1, vCount, minLoc, minLoc, 1e9);
//        while(minLoc != 1 && tree.sum(minLoc, minLoc+sz[minLoc]-1) == 1){
//            tree.add(minLoc, -1);
//            mstree.update(1, 1, vCount, minLoc, minLoc+sz[minLoc]-1, -1);
//            minLoc = par[minLoc];
//            ans--;
//        }
//    }

    printf("%d\n", n - (basic + ans));
}

Compilation message

prison.cpp: In function 'int main()':
prison.cpp:98:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |     scanf("%d %d %d", &n, &k, &t);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
prison.cpp:100:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |         scanf("%d", &arr[i]);
      |         ~~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 47272 KB Output is correct
2 Correct 30 ms 47332 KB Output is correct
3 Correct 29 ms 47292 KB Output is correct
4 Correct 30 ms 47256 KB Output is correct
5 Correct 29 ms 47308 KB Output is correct
6 Incorrect 29 ms 47368 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 47296 KB Output is correct
2 Execution timed out 2070 ms 66312 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 47272 KB Output is correct
2 Correct 30 ms 47332 KB Output is correct
3 Correct 29 ms 47292 KB Output is correct
4 Correct 30 ms 47256 KB Output is correct
5 Correct 29 ms 47308 KB Output is correct
6 Incorrect 29 ms 47368 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 47240 KB Output is correct
2 Execution timed out 2088 ms 51264 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 47272 KB Output is correct
2 Correct 30 ms 47332 KB Output is correct
3 Correct 29 ms 47292 KB Output is correct
4 Correct 30 ms 47256 KB Output is correct
5 Correct 29 ms 47308 KB Output is correct
6 Incorrect 29 ms 47368 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 47272 KB Output is correct
2 Correct 30 ms 47332 KB Output is correct
3 Correct 29 ms 47292 KB Output is correct
4 Correct 30 ms 47256 KB Output is correct
5 Correct 29 ms 47308 KB Output is correct
6 Incorrect 29 ms 47368 KB Output isn't correct
7 Halted 0 ms 0 KB -