oj.uz

Submission #779959

# Submission time Handle Problem Language Result Execution time Memory
779959 2023-07-12T03:57:04 Z 79brue Bodyguards (CEOI10_bodyguards) C++17
100 / 100
 946 ms 46072 KB 
#include <bits/stdc++.h>

using namespace std;

typedef __int128 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<long long, long long> a[200002];
pair<long long, long long> 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(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*C3 - 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 1 ms 212 KB Output is correct
2 Correct 1 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 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 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 0 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 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 0 ms 212 KB Output is correct
2 Correct 1 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 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 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 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 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 1 ms 340 KB Output is correct
17 Correct 1 ms 340 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 1 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 1 ms 340 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 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 #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 1 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 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 2 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 2 ms 340 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 3 ms 468 KB Output is correct
9 Correct 3 ms 468 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 3 ms 468 KB Output is correct
12 Correct 3 ms 468 KB Output is correct
13 Correct 3 ms 468 KB Output is correct
14 Correct 2 ms 468 KB Output is correct
15 Correct 2 ms 468 KB Output is correct
16 Correct 2 ms 468 KB Output is correct
17 Correct 2 ms 468 KB Output is correct
18 Correct 3 ms 596 KB Output is correct

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1364 KB Output is correct
2 Correct 7 ms 852 KB Output is correct
3 Correct 7 ms 1284 KB Output is correct
4 Correct 8 ms 596 KB Output is correct
5 Correct 11 ms 1384 KB Output is correct
6 Correct 16 ms 1436 KB Output is correct
7 Correct 16 ms 1428 KB Output is correct
8 Correct 12 ms 980 KB Output is correct
9 Correct 19 ms 1484 KB Output is correct
10 Correct 14 ms 1364 KB Output is correct
11 Correct 18 ms 1432 KB Output is correct
12 Correct 17 ms 1428 KB Output is correct
13 Correct 18 ms 1444 KB Output is correct
14 Correct 13 ms 1484 KB Output is correct
15 Correct 14 ms 1592 KB Output is correct
16 Correct 13 ms 1620 KB Output is correct
17 Correct 14 ms 1740 KB Output is correct
18 Correct 18 ms 1492 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 5548 KB Output is correct
2 Correct 77 ms 4740 KB Output is correct
3 Correct 157 ms 9356 KB Output is correct
4 Correct 169 ms 9052 KB Output is correct
5 Correct 145 ms 8480 KB Output is correct
6 Correct 200 ms 10300 KB Output is correct
7 Correct 116 ms 5576 KB Output is correct
8 Correct 257 ms 10316 KB Output is correct
9 Correct 205 ms 9916 KB Output is correct
10 Correct 209 ms 9804 KB Output is correct
11 Correct 205 ms 9908 KB Output is correct
12 Correct 212 ms 10320 KB Output is correct
13 Correct 206 ms 9844 KB Output is correct
14 Correct 152 ms 10316 KB Output is correct
15 Correct 150 ms 10364 KB Output is correct
16 Correct 152 ms 10240 KB Output is correct
17 Correct 154 ms 10364 KB Output is correct
18 Correct 213 ms 9804 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 368 ms 18668 KB Output is correct
2 Correct 304 ms 11500 KB Output is correct
3 Correct 423 ms 19620 KB Output is correct
4 Correct 54 ms 3160 KB Output is correct
5 Correct 350 ms 23120 KB Output is correct
6 Correct 367 ms 20828 KB Output is correct
7 Correct 317 ms 22308 KB Output is correct
8 Correct 50 ms 3168 KB Output is correct
9 Correct 398 ms 23240 KB Output is correct
10 Correct 480 ms 22300 KB Output is correct
11 Correct 449 ms 22328 KB Output is correct
12 Correct 436 ms 22120 KB Output is correct
13 Correct 401 ms 23116 KB Output is correct
14 Correct 327 ms 23036 KB Output is correct
15 Correct 334 ms 23044 KB Output is correct
16 Correct 326 ms 22960 KB Output is correct
17 Correct 330 ms 22972 KB Output is correct
18 Correct 327 ms 23124 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 545 ms 21760 KB Output is correct
2 Correct 447 ms 21608 KB Output is correct
3 Correct 491 ms 20436 KB Output is correct
4 Correct 127 ms 8952 KB Output is correct
5 Correct 457 ms 30736 KB Output is correct
6 Correct 142 ms 37404 KB Output is correct
7 Correct 405 ms 22440 KB Output is correct
8 Correct 600 ms 38920 KB Output is correct
9 Correct 917 ms 44084 KB Output is correct
10 Correct 915 ms 44024 KB Output is correct
11 Correct 917 ms 43988 KB Output is correct
12 Correct 918 ms 43992 KB Output is correct
13 Correct 946 ms 44108 KB Output is correct
14 Correct 80 ms 5336 KB Output is correct
15 Correct 790 ms 46072 KB Output is correct
16 Correct 717 ms 46064 KB Output is correct
17 Correct 861 ms 46064 KB Output is correct
18 Correct 917 ms 44024 KB Output is correct