oj.uz

Submission #779961

# Submission time Handle Problem Language Result Execution time Memory
779961 2023-07-12T03:59:38 Z 79brue Bodyguards (CEOI10_bodyguards) C++17
100 / 100
 682 ms 28264 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(__int128 a, __int128 b){
    return a/b;
}
inline ll ceilDiv(__int128 a, __int128 b){
    return (a+b-1)/b;
}

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

bool 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 false;
    tree.setOne(1, 1, m, l, C1+C2, V1+V2);
    tree.setOne(1, 1, m, r, 0, 0);
    st.erase(r);
    return true;
}

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(__int128(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(__int128(V2)*C3 - __int128(V3)*C2, C3*weight));
            }

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

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

            /// 합칠 수 있는지 봄
            while(it != st.end() && next(it) != st.end()){
                if(!checkMerge(*it, *next(it))) break;
            }
            while(it != st.begin()){
                --it;
                if(!checkMerge(*it, *next(it))) {++it; break;}
            }
        }

//        printf("After %2d: (Val %lld, Cnt %lld)\n", i, a[i].first, a[i].second);
//        for(int i=1; i<=m; i++){
//            ll c=tree.cntOne(1, 1, m, i), v=tree.sumOne(1, 1, m, i);
//            printf("%2d: (C %6lld, sum %6lld, min %6lld)\n", i, c, v, !c?0:v/c);
//        }
    }

    puts("1");
}

Compilation message

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 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 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 264 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 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 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory 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 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 340 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 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 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 0 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 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 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory 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 440 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 3 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 2 ms 340 KB Output is correct
18 Correct 2 ms 468 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 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 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1084 KB Output is correct
2 Correct 5 ms 596 KB Output is correct
3 Correct 6 ms 892 KB Output is correct
4 Correct 6 ms 468 KB Output is correct
5 Correct 8 ms 996 KB Output is correct
6 Correct 12 ms 1048 KB Output is correct
7 Correct 11 ms 980 KB Output is correct
8 Correct 9 ms 724 KB Output is correct
9 Correct 14 ms 1092 KB Output is correct
10 Correct 12 ms 1112 KB Output is correct
11 Correct 13 ms 980 KB Output is correct
12 Correct 13 ms 980 KB Output is correct
13 Correct 13 ms 1052 KB Output is correct
14 Correct 9 ms 980 KB Output is correct
15 Correct 9 ms 980 KB Output is correct
16 Correct 9 ms 980 KB Output is correct
17 Correct 9 ms 980 KB Output is correct
18 Correct 13 ms 1048 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 4064 KB Output is correct
2 Correct 54 ms 3284 KB Output is correct
3 Correct 113 ms 6304 KB Output is correct
4 Correct 120 ms 6200 KB Output is correct
5 Correct 104 ms 6228 KB Output is correct
6 Correct 143 ms 7220 KB Output is correct
7 Correct 80 ms 3960 KB Output is correct
8 Correct 159 ms 7232 KB Output is correct
9 Correct 149 ms 6840 KB Output is correct
10 Correct 150 ms 6832 KB Output is correct
11 Correct 180 ms 6836 KB Output is correct
12 Correct 152 ms 7296 KB Output is correct
13 Correct 148 ms 6828 KB Output is correct
14 Correct 113 ms 7180 KB Output is correct
15 Correct 112 ms 7244 KB Output is correct
16 Correct 112 ms 7292 KB Output is correct
17 Correct 112 ms 7284 KB Output is correct
18 Correct 147 ms 6824 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 253 ms 12460 KB Output is correct
2 Correct 211 ms 8424 KB Output is correct
3 Correct 298 ms 13460 KB Output is correct
4 Correct 41 ms 2116 KB Output is correct
5 Correct 260 ms 14232 KB Output is correct
6 Correct 257 ms 12564 KB Output is correct
7 Correct 225 ms 13604 KB Output is correct
8 Correct 36 ms 2052 KB Output is correct
9 Correct 292 ms 14364 KB Output is correct
10 Correct 312 ms 13280 KB Output is correct
11 Correct 320 ms 13356 KB Output is correct
12 Correct 317 ms 13324 KB Output is correct
13 Correct 293 ms 14312 KB Output is correct
14 Correct 249 ms 14268 KB Output is correct
15 Correct 250 ms 14156 KB Output is correct
16 Correct 250 ms 14272 KB Output is correct
17 Correct 248 ms 14332 KB Output is correct
18 Correct 245 ms 14192 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 371 ms 15600 KB Output is correct
2 Correct 341 ms 15456 KB Output is correct
3 Correct 341 ms 14200 KB Output is correct
4 Correct 93 ms 5876 KB Output is correct
5 Correct 361 ms 20172 KB Output is correct
6 Correct 127 ms 18828 KB Output is correct
7 Correct 282 ms 13072 KB Output is correct
8 Correct 418 ms 22336 KB Output is correct
9 Correct 661 ms 26320 KB Output is correct
10 Correct 661 ms 26404 KB Output is correct
11 Correct 668 ms 26440 KB Output is correct
12 Correct 682 ms 26312 KB Output is correct
13 Correct 668 ms 26416 KB Output is correct
14 Correct 56 ms 3156 KB Output is correct
15 Correct 588 ms 28264 KB Output is correct
16 Correct 560 ms 28240 KB Output is correct
17 Correct 641 ms 28184 KB Output is correct
18 Correct 667 ms 26424 KB Output is correct