oj.uz

답안 #779902

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
779902 2023-07-12T02:17:01 Z 79brue Bodyguards (CEOI10_bodyguards) C++17
40 / 100
 1000 ms 15604 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct segTree{
    struct Node{
        ll cnt, sum, lazy;
        Node(){}
        Node(ll cnt, ll sum, ll lazy): cnt(cnt), sum(sum), lazy(lazy){}
    } tree[800002];

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

    void propagate(int i, int l, int r){
        if(l==r) tree[i].sum -= tree[i].lazy * tree[i].cnt;
        else tree[i*2].lazy += tree[i].lazy, tree[i*2+1].lazy += tree[i].lazy;
        tree[i].lazy = 0;
    }

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

    void setOne(int i, int l, int r, int x, ll cnt, ll v){
        propagate(i, l, r);
        if(r<x||x<l) return;
        if(l==r){
            tree[i] = Node(cnt, v, 0);
            return;
        }
        int m = (l+r)>>1;
        setOne(i*2, l, m, x, cnt, v);
        setOne(i*2+1, m+1, r, x, cnt, v);
        tree[i].cnt = tree[i*2].cnt + tree[i*2+1].cnt;
    }

    int kth(int i, int l, int r, ll v){
        propagate(i, l, r);
        if(l==r) return l;
        int m = (l+r)>>1;
        if(tree[i*2].cnt >= v) return kth(i*2, l, m, v);
        else return kth(i*2+1, m+1, r, v-tree[i*2].cnt);
    }

    ll cntsum(int i, int l, int r, int s, int e){
        propagate(i, l, r);
        if(r<s||e<l) return 0;
        if(s<=l&&r<=e) return tree[i].cnt;
        int m = (l+r)>>1;
        return cntsum(i*2, l, m, s, e) + cntsum(i*2+1, m+1, r, s, e);
    }

    ll cntOne(int i, int l, int r, int x){
        propagate(i, l, r);
        if(l==r) return tree[i].cnt;
        int m = (l+r)>>1;
        if(x<=m) return cntOne(i*2, l, m, x);
        else return cntOne(i*2+1, m+1, r, x);
    }

    ll sumOne(int i, int l, int r, int x){
        propagate(i, l, r);
        if(l==r) return tree[i].sum;
        int m = (l+r)>>1;
        if(x<=m) return sumOne(i*2, l, m, x);
        else return sumOne(i*2+1, m+1, r, x);
    }

    void updateOne(int i, int l, int r, int x, ll v){
        propagate(i, l, r);
        if(l==r){
            tree[i].sum -= v;
            return;
        }
        int m = (l+r)>>1;
        if(x<=m) updateOne(i*2, l, m, x, v);
        else updateOne(i*2+1, m+1, r, x, v);
    }
} tree;

inline ll floorDiv(ll a, ll b){
    return a/b;
}
inline ll ceilDiv(ll a, ll b){
    return (a+b-1)/b;
}

int n, m;
pair<ll, ll> a[200002];
pair<ll, ll> b[200002];
set<int> st;

void checkMerge(int l, int r){
    ll C1 = tree.cntOne(1, 1, m, l), V1 = tree.sumOne(1, 1, m, l);
    ll C2 = tree.cntOne(1, 1, m, r), V2 = tree.sumOne(1, 1, m, r);
    if((V1+C1-1)/C1 - V2/C2 > 1) return;
    tree.setOne(1, 1, m, l, C1+C2, V1+V2);
    tree.setOne(1, 1, m, r, 0, 0);
    st.erase(r);
}

void imp(){
    puts("0");
    exit(0);
}

int main(){
    scanf("%d", &n);
    for(int i=1; i<=n; i++) scanf("%lld %lld", &a[i].first, &a[i].second);
    scanf("%d", &m);
    for(int i=1; i<=m; i++) scanf("%lld %lld", &b[i].first, &b[i].second);
    sort(a+1, a+n+1); /// 짧은 것부터
    sort(b+1, b+m+1), reverse(b+1, b+m+1); /// 긴 것부터

    tree.init(1, 1, m);
    for(int i=1; i<=m; i++){
        int j = i; ll len=b[i].second;
        while(j<m&&b[i].first==b[j+1].first) len+=b[++j].second;
        tree.setOne(1, 1, m, i, len, len*b[i].first);
        st.insert(i);
        i=j;
    }

    for(int i=1; i<=n; i++){
        ll C = a[i].first, V = a[i].second;
        while(V){
            int x = tree.kth(1, 1, m, C);
            ll weight = C - tree.cntsum(1, 1, m, 1, x-1);
            ll C2 = tree.cntOne(1, 1, m, x), V2 = tree.sumOne(1, 1, m, x);
            ll C1=-1, V1=-1, C3=-1, V3=-1;
            int l=-1, r=-1;
            auto it = st.lower_bound(x);
            ll tmp = V;

            if(weight > C2) imp();

            if(it != st.begin()){ /// 왼쪽과 합쳐질 가능성 있음
                l = *prev(it);
                C1 = tree.cntOne(1, 1, m, l), V1 = tree.sumOne(1, 1, m, l);
                if(C2 != weight) tmp = min(tmp, ceilDiv(C2 * floorDiv(V1, C1) - V2, C2-weight));
            }
            if(next(it) != st.end()){ /// 오른쪽과 합쳐질 가능성이 있음
                r = *next(it);
                C3 = tree.cntOne(1, 1, m, r), V3 = tree.sumOne(1, 1, m, r);
                tmp = min(tmp, ceilDiv((V2+C2-1)*C3 - V3*C2, C3*weight));
            }

            if(tmp*weight > V2) imp();

            /// 진행함
            tree.update(1, 1, m, 1, x-1, tmp);
            tree.updateOne(1, 1, m, x, tmp*weight);
            V-=tmp;

            /// 합칠 수 있는지 봄
            if(r!=-1) checkMerge(x, r);
            if(l!=-1) checkMerge(l, x);
        }
    }

    puts("1");
}

Compilation message

bodyguards.cpp: In function 'int main()':
bodyguards.cpp:125:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  125 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
bodyguards.cpp:126:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  126 |     for(int i=1; i<=n; i++) scanf("%lld %lld", &a[i].first, &a[i].second);
      |                             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bodyguards.cpp:127:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  127 |     scanf("%d", &m);
      |     ~~~~~^~~~~~~~~~
bodyguards.cpp:128:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  128 |     for(int i=1; i<=m; i++) scanf("%lld %lld", &b[i].first, &b[i].second);
      |                             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Incorrect 1 ms 292 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 2 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 2 ms 340 KB Output is correct
13 Correct 2 ms 340 KB Output is correct
14 Correct 2 ms 340 KB Output is correct
15 Correct 2 ms 340 KB Output is correct
16 Correct 2 ms 340 KB Output is correct
17 Correct 3 ms 468 KB Output is correct
18 Correct 2 ms 492 KB Output is correct

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 980 KB Output is correct
2 Correct 5 ms 672 KB Output is correct
3 Correct 5 ms 852 KB Output is correct
4 Correct 5 ms 600 KB Output is correct
5 Correct 7 ms 980 KB Output is correct
6 Correct 11 ms 1076 KB Output is correct
7 Correct 10 ms 980 KB Output is correct
8 Correct 9 ms 724 KB Output is correct
9 Correct 13 ms 1092 KB Output is correct
10 Correct 10 ms 1100 KB Output is correct
11 Execution timed out 1083 ms 972 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 58 ms 4024 KB Output is correct
2 Correct 51 ms 3248 KB Output is correct
3 Correct 103 ms 6224 KB Output is correct
4 Correct 112 ms 6200 KB Output is correct
5 Correct 104 ms 6276 KB Output is correct
6 Correct 137 ms 7216 KB Output is correct
7 Correct 74 ms 4036 KB Output is correct
8 Correct 148 ms 7252 KB Output is correct
9 Execution timed out 1093 ms 6736 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 241 ms 12592 KB Output is correct
2 Correct 194 ms 8332 KB Output is correct
3 Execution timed out 1080 ms 13400 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 365 ms 15604 KB Output is correct
2 Correct 345 ms 15404 KB Output is correct
3 Correct 329 ms 14284 KB Output is correct
4 Execution timed out 1092 ms 5836 KB Time limit exceeded
5 Halted 0 ms 0 KB -