oj.uz

Submission #779911

# Submission time Handle Problem Language Result Execution time Memory
779911 2023-07-12T02:51:53 Z 79brue Bodyguards (CEOI10_bodyguards) C++17
50 / 100
 1000 ms 15608 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();

            /// 진행함
            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 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 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 1 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 0 ms 212 KB Output is correct
3 Correct 0 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 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 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 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
17 Correct 1 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 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 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 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 212 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 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 404 KB Output is correct
4 Correct 2 ms 328 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 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 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 0 ms 212 KB Output is correct
2 Execution timed out 1081 ms 212 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 980 KB Output is correct
2 Correct 7 ms 656 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 14 ms 1052 KB Output is correct
7 Correct 13 ms 980 KB Output is correct
8 Correct 12 ms 832 KB Output is correct
9 Correct 13 ms 980 KB Output is correct
10 Correct 10 ms 1096 KB Output is correct
11 Execution timed out 1084 ms 980 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 4052 KB Output is correct
2 Correct 55 ms 3312 KB Output is correct
3 Correct 110 ms 6228 KB Output is correct
4 Correct 120 ms 6100 KB Output is correct
5 Correct 105 ms 6276 KB Output is correct
6 Correct 148 ms 7224 KB Output is correct
7 Correct 93 ms 4052 KB Output is correct
8 Correct 154 ms 7152 KB Output is correct
9 Execution timed out 1092 ms 6732 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 255 ms 12520 KB Output is correct
2 Correct 206 ms 8424 KB Output is correct
3 Execution timed out 1083 ms 13416 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 370 ms 15608 KB Output is correct
2 Correct 320 ms 15448 KB Output is correct
3 Correct 349 ms 14268 KB Output is correct
4 Execution timed out 1085 ms 5780 KB Time limit exceeded
5 Halted 0 ms 0 KB -