oj.uz

Submission #779947

# Submission time Handle Problem Language Result Execution time Memory
779947 2023-07-12T03:43:06 Z 79brue Bodyguards (CEOI10_bodyguards) C++17
60 / 100
 396 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;

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 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 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 1 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 0 ms 212 KB Output is correct
10 Correct 1 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 1 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 0 ms 212 KB Output is correct
5 Correct 0 ms 340 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 340 KB Output is correct
10 Correct 0 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

# 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 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 440 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 3 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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 972 KB Output is correct
2 Correct 5 ms 672 KB Output is correct
3 Correct 6 ms 852 KB Output is correct
4 Correct 6 ms 468 KB Output is correct
5 Correct 8 ms 980 KB Output is correct
6 Correct 15 ms 980 KB Output is correct
7 Correct 12 ms 1040 KB Output is correct
8 Correct 9 ms 724 KB Output is correct
9 Correct 13 ms 1096 KB Output is correct
10 Correct 10 ms 1100 KB Output is correct
11 Correct 4 ms 980 KB Output is correct
12 Correct 4 ms 1108 KB Output is correct
13 Correct 4 ms 1108 KB Output is correct
14 Incorrect 9 ms 1240 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 4052 KB Output is correct
2 Correct 55 ms 3216 KB Output is correct
3 Correct 109 ms 6276 KB Output is correct
4 Correct 117 ms 6204 KB Output is correct
5 Correct 106 ms 6272 KB Output is correct
6 Correct 147 ms 7216 KB Output is correct
7 Correct 79 ms 3960 KB Output is correct
8 Correct 152 ms 7244 KB Output is correct
9 Correct 70 ms 6760 KB Output is correct
10 Correct 151 ms 8204 KB Output is correct
11 Correct 158 ms 8140 KB Output is correct
12 Correct 146 ms 8704 KB Output is correct
13 Correct 119 ms 8200 KB Output is correct
14 Correct 111 ms 8604 KB Output is correct
15 Correct 113 ms 8600 KB Output is correct
16 Correct 111 ms 8512 KB Output is correct
17 Correct 111 ms 8476 KB Output is correct
18 Correct 154 ms 8204 KB Output is correct

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 269 ms 12508 KB Output is correct
2 Correct 205 ms 8416 KB Output is correct
3 Incorrect 316 ms 13456 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 396 ms 15604 KB Output is correct
2 Correct 352 ms 15456 KB Output is correct
3 Correct 345 ms 14180 KB Output is correct
4 Incorrect 89 ms 5872 KB Output isn't correct
5 Halted 0 ms 0 KB -