oj.uz

Submission #520254

# Submission time Handle Problem Language Result Execution time Memory
520254 2022-01-29T03:55:07 Z qwerasdfzxcl Pyramid Base (IOI08_pyramid_base) C++14
0 / 100
 5000 ms 96472 KB 
#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
struct Seg{
    int tree[2202000], lazy[2202000];
    void init(int i, int l, int r){
        tree[i] = lazy[i] = 0;
        if (l==r) return;

        int m = (l+r)>>1;
        init(i<<1, l, m); init(i<<1|1, m+1, r);
    }
    void propagate(int i, int l, int r){
        tree[i] += lazy[i];
        if (l!=r) lazy[i<<1] += lazy[i], lazy[i<<1|1] += lazy[i];
        lazy[i] = 0;
    }
    void update(int i, int l, int r, int s, int e, int x){
        propagate(i, l, r);
        if (r<s || e<l) return;
        if (s<=l && r<=e){
            lazy[i] += x;
            propagate(i, l, r);
            return;
        }

        int m = (l+r)>>1;
        update(i<<1, l, m, s, e, x);
        update(i<<1|1, m+1, r, s, e, x);
        tree[i] = min(tree[i<<1], tree[i<<1|1]);
    }
}tree;
struct Query{
    int l, r, c;
    Query(){}
    Query(int _l, int _r, int _c): l(_l), r(_r), c(_c) {}
};
vector<Query> L[1001000], R[1001000];
int n, m, B;

bool calc(int x){
    tree.init(1, 1, m-x+1);
    for (int i=1;i<=x;i++){
        for (auto &p:L[i]){
            tree.update(1, 1, m-x+1, max(1, p.l-x+1), min(m-x+1, p.r), p.c);
            //if (x==3) printf("%d: %d %d -> %d %d\n", i, p.l, p.r, max(1, p.l-x+1), min(m-x+1, p.r));
        }
    }
    if (tree.tree[1]<=B) return 1;
    for (int i=x+1;i<=n;i++){
        for (auto &p:R[i-x]){
            tree.update(1, 1, m-x+1, max(1, p.l-x+1), min(m-x+1, p.r), p.c);
        }
        for (auto &p:L[i]){
            tree.update(1, 1, m-x+1, max(1, p.l-x+1), min(m-x+1, p.r), p.c);
        }

        if (tree.tree[1]<=B) return 1;
    }
    return 0;
}

int main(){
    scanf("%d %d %d", &m, &n, &B);
    int q;
    scanf("%d", &q);
    for (int i=0;i<q;i++){
        int x1, y1, x2, y2, c;
        scanf("%d %d %d %d %d", &x1, &y1, &x2, &y2, &c);
        if (B==0) c = 1;
        L[y1].emplace_back(x1, x2, c);
        R[y2].emplace_back(x1, x2, c);
    }

    int l = 1, r = min(m, n), ans = 0;
    while(l<=r){
        int mid = (l+r)>>1;
        if (calc(mid)) l = mid+1, ans = mid;
        else r = mid-1;
    }

    //printf("YES\n");
    //printf("%d\n", calc(3));
    printf("%d\n", ans);
    return 0;
}

Compilation message

pyramid_base.cpp: In function 'int main()':
pyramid_base.cpp:65:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |     scanf("%d %d %d", &m, &n, &B);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
pyramid_base.cpp:67:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
pyramid_base.cpp:70:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |         scanf("%d %d %d %d %d", &x1, &y1, &x2, &y2, &c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 47312 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 47304 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 47508 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 28 ms 47500 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 36 ms 49436 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 217 ms 63692 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 160 ms 63740 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 30 ms 47740 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 132 ms 50504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 304 ms 57324 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 447 ms 65984 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 303 ms 58224 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3913 ms 80920 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #14
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5058 ms 88908 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #15
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5058 ms 96472 KB Time limit exceeded
2 Halted 0 ms 0 KB -