oj.uz

답안 #520453

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
520453 2022-01-30T03:25:16 Z qwerasdfzxcl Pyramid Base (IOI08_pyramid_base) C++14
100 / 100
 1330 ms 134208 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;
}

struct Node{
    int l, r, mn, len, prf, suf, ran;
    Node(){}
    Node(int _l, int _r, int _mn, int _len, int _prf, int _suf, int _ran): l(_l), r(_r), mn(_mn), len(_len), prf(_prf), suf(_suf), ran(_ran) {}
    Node operator +(const Node &N) const{
        Node ret(l, N.r, min(mn, N.mn), len + N.len, prf, N.suf, 0);
        if (mn==ret.mn) ret.ran = max(ret.ran, ran);
        if (N.mn==ret.mn) ret.ran = max(ret.ran, N.ran);

        if (prf==len && l==N.l) ret.prf = len + N.prf;
        if (N.suf==N.len && r==N.r) ret.suf = suf + N.len;
        if (r==N.l && r==ret.mn) ret.ran = max(ret.ran, suf + N.prf);
        return ret;
    }
};

struct Seg2{
    Node tree[2202000];
    int lazy[2202000];
    void init(int i, int l, int r){
        lazy[i] = 0;
        if (l==r) {tree[i] = Node(0, 0, 0, 1, 1, 1, 1); return;}

        int m = (l+r)>>1;
        init(i<<1, l, m); init(i<<1|1, m+1, r);
        tree[i] = tree[i<<1] + tree[i<<1|1];
    }
    void propagate(int i, int l, int r){
        tree[i].l += lazy[i];
        tree[i].r += lazy[i];
        tree[i].mn += 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] = tree[i<<1] + tree[i<<1|1];

        //printf("%d %d: %d %d %d %d %d %d %d\n", l, r, tree[i].l, tree[i].r, tree[i].mn, tree[i].len, tree[i].prf, tree[i].suf, tree[i].ran);
    }
    int calc(){
        if (tree[1].mn) return 0;
        return tree[1].ran;
    }
}tree2;

void solve(){
    int l = 0, ans = 0;
    tree2.init(1, 1, m);

    for (int i=1;i<=n;i++){
        for (auto &q:L[i]) tree2.update(1, 1, m, q.l, q.r, q.c);
        while(l<i && tree2.calc() < i-l){
            for (auto &q:R[l+1]) tree2.update(1, 1, m, q.l, q.r, q.c);
            l++;
        }
        ans = max(ans, i-l);
    }
    printf("%d\n", ans);
    exit(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);
    }

    if (B==0) solve();

    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:137:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  137 |     scanf("%d %d %d", &m, &n, &B);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
pyramid_base.cpp:140:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  140 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
pyramid_base.cpp:143:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  143 |         scanf("%d %d %d %d %d", &x1, &y1, &x2, &y2, &c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 47308 KB Output is correct

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 47280 KB Output is correct

Subtask #3
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 47396 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 48332 KB Output is correct

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 55592 KB Output is correct

Subtask #6
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 84 ms 112984 KB Output is correct
2 Correct 75 ms 112940 KB Output is correct

Subtask #7
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 74 ms 113032 KB Output is correct
2 Correct 77 ms 112936 KB Output is correct

Subtask #8
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 47620 KB Output is correct
2 Correct 48 ms 47820 KB Output is correct
3 Correct 60 ms 47828 KB Output is correct

Subtask #9
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 137 ms 50308 KB Output is correct
2 Correct 302 ms 50216 KB Output is correct
3 Correct 236 ms 50144 KB Output is correct

Subtask #10
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 274 ms 56756 KB Output is correct
2 Correct 171 ms 64452 KB Output is correct
3 Correct 53 ms 48544 KB Output is correct
4 Correct 698 ms 64952 KB Output is correct

Subtask #11
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 473 ms 65220 KB Output is correct
2 Correct 883 ms 65096 KB Output is correct
3 Correct 219 ms 57028 KB Output is correct

Subtask #12
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 355 ms 57372 KB Output is correct
2 Correct 1098 ms 65476 KB Output is correct
3 Correct 1035 ms 65476 KB Output is correct
4 Correct 1058 ms 65476 KB Output is correct
5 Correct 995 ms 65428 KB Output is correct
6 Correct 169 ms 57260 KB Output is correct

Subtask #13
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 782 ms 124388 KB Output is correct
2 Correct 567 ms 118636 KB Output is correct

Subtask #14
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 969 ms 129436 KB Output is correct
2 Correct 898 ms 127324 KB Output is correct
3 Correct 546 ms 64944 KB Output is correct

Subtask #15
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1207 ms 134208 KB Output is correct
2 Correct 1330 ms 131952 KB Output is correct
3 Correct 1323 ms 132004 KB Output is correct
4 Correct 1267 ms 131768 KB Output is correct
5 Correct 980 ms 125744 KB Output is correct