답안 #520576

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
520576 2022-01-30T09:22:21 Z lohacho Pyramid Base (IOI08_pyramid_base) C++14
100 / 100
1996 ms 147152 KB
#include <bits/stdc++.h>
#define int long long
#define mi(x, y) (x = min(x, y))
#define ma(x, y) (x = max(x, y))
using namespace std;
 
const int NS = (int)8e5 + 54;
int tr[NS * 4], tr2[NS * 4], l[NS * 4], r[NS * 4];
vector<int> srt;
 
struct Data{
    int xs, ys, ye, v;
    Data(){}
    Data(int xs, int ys, int ye, int v):xs(xs), ys(ys), ye(ye), v(v){}
    bool operator<(const Data&r)const{
        return xs < r.xs || (xs == r.xs && v > r.v);
    }
};

void build(int x, int s, int e){
    if(s == e){
        tr[x] = l[x] = r[x] = srt[s + 1] - srt[s];
        return;
    }
    int m = s + e >> 1;
    build(x * 2, s, m), build(x * 2 + 1, m + 1, e);
    tr[x] = l[x] = r[x] = tr[x * 2] + tr[x * 2 + 1];
}

void push(int x, int s, int e, int ps, int pe, int val){
    //cout << x << ' ' << s << ' ' << e << ' ' << ps << ' ' << pe << ' ' << val << endl;
    if(pe < s || ps > e) return;
    if(ps <= s && pe >= e){
        tr2[x] += val;
        if(!tr2[x]){
            if(s == e) tr[x] = l[x] = r[x] = srt[s + 1] - srt[s];
            else{
                tr[x] = max({tr[x * 2], tr[x * 2 + 1], r[x * 2] + l[x * 2 + 1]});
                l[x] = (tr[x * 2] == srt[(s + e) / 2 + 1] - srt[s] ? tr[x * 2] + l[x * 2 + 1] : l[x * 2]);
                r[x] = (tr[x * 2 + 1] == srt[e + 1] - srt[(s + e) / 2 + 1] ? tr[x * 2 + 1] + r[x * 2] : r[x * 2 + 1]);
            }
        }
        else{
            tr[x] = l[x] = r[x] = 0;
        }
        return;
    }
    int m = s + e >> 1;
    push(x * 2, s, m, ps, pe, val), push(x * 2 + 1, m + 1, e, ps, pe, val);
    if(!tr2[x]){
        if(s == e) tr[x] = l[x] = r[x] = srt[s + 1] - srt[s];
        else{
            tr[x] = max({tr[x * 2], tr[x * 2 + 1], r[x * 2] + l[x * 2 + 1]});
            l[x] = (tr[x * 2] == srt[(s + e) / 2 + 1] - srt[s] ? tr[x * 2] + l[x * 2 + 1] : l[x * 2]);
            r[x] = (tr[x * 2 + 1] == srt[e + 1] - srt[(s + e) / 2 + 1] ? tr[x * 2 + 1] + r[x * 2] : r[x * 2 + 1]);
        }
    }
    else{
        tr[x] = l[x] = r[x] = 0;
    }
}

struct Seg{
    int n;
    vector<int> tree, lazy;
    Seg(int N):n(N){
        tree.resize(n * 4), lazy.resize(n * 4);
    }
    void add(int x, int l, int r, int val){
        lazy[x] += val;
        tree[x] += val;
    }
    void update(int x, int l, int r){
        if(lazy[x] == 0) return;
        int mid = (l + r) >> 1;
        add(x * 2, l, mid, lazy[x]), add(x * 2 + 1, mid + 1, r, lazy[x]);
        lazy[x] = 0;
    }
    void push(int x, int l, int r, int pl, int pr, int val){
        if(pr < l || pl > r || pl > pr) return;
        if(l >= pl && r <= pr){
            add(x, l, r, val);
            return;
        }
        update(x, l, r);
        int mid = (l + r) >> 1;
        push(x * 2, l, mid, pl, pr, val), push(x * 2 + 1, mid + 1, r, pl, pr, val);
        tree[x] = min(tree[x * 2], tree[x * 2 + 1]);
    }
    int get(int x, int l, int r, int fl, int fr){
        if(fr < l || fl > r || fl > fr) return (int)1e9;
        if(l >= fl && r <= fr) return tree[x];
        update(x, l, r);
        int mid = (l + r) >> 1;
        return min(get(x * 2, l, mid, fl, fr), get(x * 2 + 1, mid + 1, r, fl, fr));
    }
};
 
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int h, w, n, b;
    cin >> h >> w >> b >> n;
    vector<vector<int>> a(n, vector<int>(5));
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < 5; ++j){
            cin >> a[i][j];
        }
    }
    int ans = 0;
    if(b){
        int low = 0, high = (int)1e6;
        vector<Data> vc;
        while(low < high){
            int mid = low + high + 1 >> 1;
            srt.clear();
            for(int i = 0; i < n; ++i){
                srt.push_back(a[i][1] - mid + 1), srt.push_back(a[i][3] + 1);
            }
            srt.push_back(1), srt.push_back(w + 1);
            srt.push_back(w - mid + 1);
            sort(srt.begin(), srt.end());
            srt.erase(unique(srt.begin(), srt.end()), srt.end());
            vector<Data> vc;
            for(int i = 0; i < n; ++i){
                a[i][1] = lower_bound(srt.begin(), srt.end(), a[i][1] - mid + 1) - srt.begin();
                a[i][3] = lower_bound(srt.begin(), srt.end(), a[i][3] + 1) - srt.begin();
            }
            for(int i = 0; i < n; ++i){
                vc.push_back(Data(a[i][0] - mid + 1, a[i][1], a[i][3] - 1, a[i][4]));
                vc.push_back(Data(a[i][2] + 1, a[i][1], a[i][3] - 1, -a[i][4]));
            }
            sort(vc.begin(), vc.end());
            int lst = 1, f = 0;
            Seg tree((int)srt.size() + 4);
            int up = lower_bound(srt.begin(), srt.end(), w - mid + 1) - srt.begin();
            int down = lower_bound(srt.begin(), srt.end(), 1) - srt.begin();
            for(auto&i:vc){
                if(lst < i.xs && lst >= 1 && lst + mid - 1 <= h){
                    if(tree.get(1, 0, (int)srt.size() - 2, down, up) <= b){
                        f = 1;
                        break;
                    }
                }
                lst = max(i.xs, 1ll);
                tree.push(1, 0, (int)srt.size() - 2, i.ys, i.ye, i.v);
            }
            if(lst >= 1 && lst + mid - 1 <= h){
                if(tree.get(1, 0, (int)srt.size() - 2, down, up) <= b){
                    f = 1;
                }
            }
            if(f){
                low = mid;
            }
            else{
                high = mid - 1;
            }
            for(int i = 0; i < n; ++i){
                a[i][1] = srt[a[i][1]] + mid - 1;
                a[i][3] = srt[a[i][3]] - 1;
            }
        }
        ans = low;
    }
    else{
        for(int k = 0; k < 2; ++k){
            srt.clear();
            for(int i = 0; i < n; ++i){
                srt.push_back(a[i][1]), srt.push_back(a[i][3] + 1);
            }
            srt.push_back(1), srt.push_back(w + 1);
            sort(srt.begin(), srt.end());
            srt.erase(unique(srt.begin(), srt.end()), srt.end());
            vector<Data> vc;
            for(int i = 0; i < n; ++i){
                a[i][1] = lower_bound(srt.begin(), srt.end(), a[i][1]) - srt.begin();
                a[i][3] = lower_bound(srt.begin(), srt.end(), a[i][3] + 1) - srt.begin();
                vc.push_back(Data(a[i][0], a[i][1], a[i][3] - 1, 1));
                vc.push_back(Data(a[i][2] + 1, a[i][1], a[i][3] - 1, -1));
            }
            vc.push_back(Data(1, 0, (int)srt.size() - 2, 1));
            vc.push_back(Data(1, 0, (int)srt.size() - 2, -1));
            vc.push_back(Data(h + 1, 0, (int)srt.size() - 2, 1));
            vc.push_back(Data(h + 1, 0, (int)srt.size() - 2, -1));
            sort(vc.begin(), vc.end());
            build(1, 0, (int)srt.size() - 2);
            int r = 0, mr = -1;
            for(int l = 0; l < (int)vc.size(); ++l){
                if(vc[l].v == -1){
                    push(1, 0, (int)srt.size() - 2, vc[l].ys, vc[l].ye, -1);
                }
                while(r + 1 < (int)vc.size()){
                    if(tr[1] < vc[r].xs - vc[l].xs){
                        break;
                    }
                    mr = vc[r].xs;
                    if(tr[1] >= vc[r].xs - vc[l].xs) mr = vc[r].xs;
                    if(vc[r].v == 1) push(1, 0, (int)srt.size() - 2, vc[r].ys, vc[r].ye, 1);
                    ++r;
                }
                if(tr[1] >= vc[r].xs - vc[l].xs){
                    mr = vc[r].xs;
                }
                if(r){
                    ma(ans, mr - vc[l].xs);
                    //cout << vc[l].xs << ' ' << vc[l].ys << ' ' << vc[l].ye << ' ' << vc[l].v << endl;
                    //cout << vc[r - 1].xs << ' ' << vc[r - 1].ys << ' ' << vc[r - 1].ye << ' ' << vc[r - 1].v << endl;
                }
            }
            for(int i = 0; i < n; ++i){
                a[i][1] = srt[a[i][1]];
                a[i][3] = srt[a[i][3]] - 1;
                swap(a[i][0], a[i][1]);
                swap(a[i][2], a[i][3]);
            }
            swap(h, w);
        }
    }
    cout << ans << '\n';
    return 0;
}

Compilation message

pyramid_base.cpp: In function 'void build(long long int, long long int, long long int)':
pyramid_base.cpp:25:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   25 |     int m = s + e >> 1;
      |             ~~^~~
pyramid_base.cpp: In function 'void push(long long int, long long int, long long int, long long int, long long int, long long int)':
pyramid_base.cpp:48:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |     int m = s + e >> 1;
      |             ~~^~~
pyramid_base.cpp: In function 'int main()':
pyramid_base.cpp:115:34: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  115 |             int mid = low + high + 1 >> 1;
      |                       ~~~~~~~~~~~^~~
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 324 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 324 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 460 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 588 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 588 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 588 KB Output is correct
2 Correct 3 ms 676 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 716 KB Output is correct
2 Correct 3 ms 588 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 143 ms 1728 KB Output is correct
2 Correct 144 ms 1668 KB Output is correct
3 Correct 112 ms 1728 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 415 ms 4888 KB Output is correct
2 Correct 480 ms 4828 KB Output is correct
3 Correct 401 ms 4740 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 477 ms 6984 KB Output is correct
2 Correct 275 ms 5848 KB Output is correct
3 Correct 539 ms 6960 KB Output is correct
4 Correct 483 ms 7128 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 701 ms 8408 KB Output is correct
2 Correct 785 ms 7716 KB Output is correct
3 Correct 629 ms 8032 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 863 ms 9056 KB Output is correct
2 Correct 962 ms 8872 KB Output is correct
3 Correct 898 ms 8908 KB Output is correct
4 Correct 1033 ms 8916 KB Output is correct
5 Correct 959 ms 8948 KB Output is correct
6 Correct 772 ms 9072 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 932 ms 80008 KB Output is correct
2 Correct 490 ms 55488 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1350 ms 108460 KB Output is correct
2 Correct 1256 ms 108940 KB Output is correct
3 Correct 870 ms 92320 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1996 ms 147152 KB Output is correct
2 Correct 1996 ms 117788 KB Output is correct
3 Correct 1948 ms 117800 KB Output is correct
4 Correct 1724 ms 117800 KB Output is correct
5 Correct 1238 ms 101412 KB Output is correct