Submission #213333

#	Time	Username	Problem	Language	Result	Execution time	Memory
213333		mhy908	Pyramid Base (IOI08_pyramid_base)	C++14	70 / 100	5104 ms	97628 KiB

pyramid_base

#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sortvec(x) sort(all(x))
#define compress(x) x.erase(unique(all(x)), x.end())
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
typedef pair<int, LL> pil;
typedef pair<LL, int> pli;
const LL llinf=1987654321987654321;
const int inf=2000000000;
int n, m, p;
pair<pair<pii, pii>, LL> rect[400010];
LL b, tree[4000010], lazy[4000010];
void init(int point, int s, int e){
    tree[point]=lazy[point]=0;
    if(s==e)return;
    init(point*2, s, (s+e)/2);
    init(point*2+1, (s+e)/2+1, e);
}
void propogate(int point){
    tree[point]+=lazy[point];
    lazy[point*2]+=lazy[point];
    lazy[point*2+1]+=lazy[point];
    lazy[point]=0;
}
void alter(int point, int s, int e, int a, int b, LL qu){
    if(a<=s&&e<=b){
        lazy[point]+=qu;
        return;
    }
    if(s>b||e<a)return;
    propogate(point);
    alter(point*2, s, (s+e)/2, a, b, qu);
    alter(point*2+1, (s+e)/2+1, e, a, b, qu);
    tree[point]=min(tree[point*2]+lazy[point*2], tree[point*2+1]+lazy[point*2+1]);
}
bool poss(int num){
    vector<pair<pil, pii> > query;
    vector<int> idy;
    query.pb(mp(mp(1, 0), mp(1, m-num)));
    query.pb(mp(mp(n-num+1, 0), mp(1, m-num)));
    idy.pb(1);
    idy.pb(m-num);
    for(int i=1; i<=p; i++){
        int sx=max(rect[i].F.F.F-num, 1);
        int ex=rect[i].F.S.F;
        int sy=max(rect[i].F.F.S-num, 1);
        int ey=min(rect[i].F.S.S, m-num);
        query.pb(mp(mp(sx, rect[i].S), mp(sy, ey)));
        query.pb(mp(mp(ex+1, -rect[i].S), mp(sy, ey)));
        idy.pb(sy);
        idy.pb(ey);
        if(sy>1)idy.pb(sy-1);
        if(ey<m-num)idy.pb(ey+1);
    }
    sortvec(idy);
    compress(idy);
    sortvec(query);
    init(1, 1, idy.size());
    for(auto &i:query){
        i.S.F=lower_bound(all(idy), i.S.F)-idy.begin()+1;
        i.S.S=lower_bound(all(idy), i.S.S)-idy.begin()+1;
    }
    for(int i=0; i<query.size(); i++){
        if(query[i].F.F>n-num)break;
        alter(1, 1, idy.size(), query[i].S.F, query[i].S.S, query[i].F.S);
        if(query[i].F.F!=query[i+1].F.F&&tree[1]+lazy[1]<=b)return true;
    }
    return false;
}
int main(){
    scanf("%d %d %lld %d", &n, &m, &b, &p);
    for(int i=1; i<=p; i++){
        scanf("%d %d %d %d %lld", &rect[i].F.F.F, &rect[i].F.F.S, &rect[i].F.S.F, &rect[i].F.S.S, &rect[i].S);
    }
    int l=0, r=min(n, m);
    while(l<r){
        int mid=(l+r)/2+1;
        if(poss(mid-1))l=mid;
        else r=mid-1;
    }
    printf("%d", l);
}

Compilation message (stderr)

pyramid_base.cpp: In function 'bool poss(int)':
pyramid_base.cpp:70:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<query.size(); i++){
                  ~^~~~~~~~~~~~~
pyramid_base.cpp: In function 'int main()':
pyramid_base.cpp:78:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %lld %d", &n, &m, &b, &p);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
pyramid_base.cpp:80:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d %d %lld", &rect[i].F.F.F, &rect[i].F.F.S, &rect[i].F.S.F, &rect[i].F.S.S, &rect[i].S);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5
• Subtask 8: 7 / 7
• Subtask 9: 7 / 7
• Subtask 10: 7 / 7
• Subtask 11: 7 / 7
• Subtask 12: 7 / 7
• Subtask 13: 0 / 10
• Subtask 14: 0 / 10
• Subtask 15: 0 / 10