oj.uz

답안 #401945

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
401945 2021-05-11T03:30:28 Z ja_kingy Pyramid Base (IOI08_pyramid_base) C++14
85 / 100
 1460 ms 47492 KB 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
typedef pair<int,int> pii;
const int mxP = 4e5;
int m,n,b,p,x1[mxP],y1[mxP],x2[mxP],y2[mxP],c[mxP];
vector<pii> lft, rht;
 
struct range_add {
    int st[1<<21], lz[1<<21];
    void push(int t) {
        st[t*2] += lz[t];
        st[t*2+1] += lz[t];
        lz[t*2] += lz[t];
        lz[t*2+1] += lz[t];
        lz[t] = 0;
    }
    void upd(int ul, int ur, int v, int t, int l, int r) {
        if (ur <= l || r <= ul) return;
        if (ul <= l && r <= ur) {
            st[t] += v;
            lz[t] += v;
            return;
        }
        int m = l+r>>1;
        push(t);
        upd(ul, ur, v, t*2, l, m);  
        upd(ul, ur, v, t*2+1, m, r);
        st[t] = min(st[t*2], st[t*2+1]);  
    }
};
 
bool can_do(int sz) {
    range_add st{};
    int l = 0;
    for (auto [x, s]: rht) {
        while (lft[l].first - x <= sz) {
            if (l == lft.size()-1) return 0;
            st.upd(y1[lft[l].second]-sz+1, y2[lft[l].second]+1, c[lft[l].second], 1, 1, n-sz+2);
            l++;
        }
        if (~s) st.upd(y1[s]-sz+1, y2[s]+1, -c[s], 1, 1, n-sz+2);
        if (st.st[1] <= b) return 1;
    }
    return 0;
}
 
struct max_zeros {
    int st[1<<21], ans[1<<21], pfx[1<<21], sfx[1<<21];
    void build(int t, int l, int r) {
        if (r - l > 1) {
            int m = l+r>>1;
            build(t*2, l, m);
            build(t*2+1, m, r);
        }
        ans[t] = pfx[t] = sfx[t] = r-l;
    }
    void pull(int t, int l, int r) {
        int m = l+r>>1;
        pfx[t] = pfx[t*2] + (pfx[t*2] == m-l ? pfx[t*2+1] : 0);
        sfx[t] = sfx[t*2+1] + (sfx[t*2+1] == r-m ? sfx[t*2] : 0);
        ans[t] = max({ans[t*2], ans[t*2+1], sfx[t*2] + pfx[t*2+1]});
    }
    void upd(int ul, int ur, int v, int t, int l, int r) {
        if (ur <= l || r <= ul) return;
        if (ul <= l && r <= ur) {
            st[t] += v;
            if (!st[t]) {
                if (r-l>1) pull(t, l, r);
                else ans[t] = pfx[t] = sfx[t] = 1;
            }
            else ans[t] = pfx[t] = sfx[t] = 0;
            return;
        }
        int m = l+r>>1;
        upd(ul, ur, v, t*2, l, m);  
        upd(ul, ur, v, t*2+1, m, r);
        if (!st[t]) pull(t, l, r);
    }
};
 
void sub3() {
    int ans = 0, r=1, x=0,y=0;
    rht.erase(rht.begin());
    max_zeros st{};
    st.build(1, 1, n+1);
    for (int l = 1; l <= m; l++) {
        while (r <= m && st.ans[1] >= r-l) {
            ans = max(ans, r-l);
            while (lft[x].first == r) {
                st.upd(y1[lft[x].second], y2[lft[x].second]+1, 1, 1, 1, n+1);
                x++;
            }
            r++;
        }
        while (y < rht.size() && rht[y].first == l) {
            st.upd(y1[rht[y].second], y2[rht[y].second]+1, -1, 1, 1, n+1);
            y++;
        }
    }
    cout << ans;
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> m >> n >> b >> p;
    lft.push_back({m+1, -1});
    rht.push_back({0, -1});
    for (int i = 0; i < p; ++i) {
        cin >> x1[i] >> y1[i] >> x2[i] >> y2[i] >> c[i];
        lft.push_back({x1[i], i});
        rht.push_back({x2[i], i});
    }
    sort(lft.begin(), lft.end());
    sort(rht.begin(), rht.end());
    if (b == 0) {
        sub3();
        return 0;
    }
    int lo = 1, hi = min(m,n)+1, mid;
    while (lo != hi) {
        mid = lo+hi>>1;
        if (can_do(mid)) lo = mid+1;
        else hi = mid;
    }
    cout << lo-1;
}

Compilation message

pyramid_base.cpp: In member function 'void range_add::upd(int, int, int, int, int, int)':
pyramid_base.cpp:27:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 |         int m = l+r>>1;
      |                 ~^~
pyramid_base.cpp: In function 'bool can_do(int)':
pyramid_base.cpp:38:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   38 |     for (auto [x, s]: rht) {
      |               ^
pyramid_base.cpp:40:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |             if (l == lft.size()-1) return 0;
      |                 ~~^~~~~~~~~~~~~~~
pyramid_base.cpp: In member function 'void max_zeros::build(int, int, int)':
pyramid_base.cpp:54:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   54 |             int m = l+r>>1;
      |                     ~^~
pyramid_base.cpp: In member function 'void max_zeros::pull(int, int, int)':
pyramid_base.cpp:61:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   61 |         int m = l+r>>1;
      |                 ~^~
pyramid_base.cpp: In member function 'void max_zeros::upd(int, int, int, int, int, int)':
pyramid_base.cpp:77:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   77 |         int m = l+r>>1;
      |                 ~^~
pyramid_base.cpp: In function 'void sub3()':
pyramid_base.cpp:98:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |         while (y < rht.size() && rht[y].first == l) {
      |                ~~^~~~~~~~~~~~
pyramid_base.cpp: In function 'int main()':
pyramid_base.cpp:125:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  125 |         mid = lo+hi>>1;
      |               ~~^~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 18 ms 33100 KB Output isn't correct

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

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

Subtask #6
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 33200 KB Output is correct
2 Correct 34 ms 33296 KB Output is correct

Subtask #7
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 33196 KB Output is correct
2 Correct 36 ms 33196 KB Output is correct

Subtask #8
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 17016 KB Output is correct
2 Correct 81 ms 17016 KB Output is correct
3 Correct 76 ms 17008 KB Output is correct

Subtask #9
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 171 ms 17376 KB Output is correct
2 Correct 301 ms 17384 KB Output is correct
3 Correct 235 ms 17492 KB Output is correct

Subtask #10
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 191 ms 17676 KB Output is correct
2 Correct 34 ms 17696 KB Output is correct
3 Correct 136 ms 17676 KB Output is correct
4 Correct 381 ms 17676 KB Output is correct

Subtask #11
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 321 ms 17812 KB Output is correct
2 Correct 698 ms 17792 KB Output is correct
3 Correct 111 ms 17736 KB Output is correct

Subtask #12
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 236 ms 18024 KB Output is correct
2 Correct 926 ms 18028 KB Output is correct
3 Correct 888 ms 18020 KB Output is correct
4 Correct 934 ms 18112 KB Output is correct
5 Correct 892 ms 18028 KB Output is correct
6 Correct 88 ms 18020 KB Output is correct

Subtask #13
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 705 ms 40424 KB Output is correct
2 Correct 520 ms 40408 KB Output is correct

Subtask #14
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 862 ms 43956 KB Output is correct
2 Correct 972 ms 43988 KB Output is correct
3 Correct 732 ms 43944 KB Output is correct

Subtask #15
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1060 ms 47488 KB Output is correct
2 Correct 1460 ms 47492 KB Output is correct
3 Incorrect 1405 ms 47492 KB Output isn't correct
4 Halted 0 ms 0 KB -