Submission #95240

#	Time	Username	Problem	Language	Result	Execution time	Memory
95240		easrui	Pyramid Base (IOI08_pyramid_base)	C++14	0 / 100	4 ms	376 KiB

pyramid_base

#include <bits/stdc++.h>
using namespace std;
const int MP = 4e5+5;
int M,N,B,P;

struct Obs{
    int sx,ex,sy,ey,val;
    Obs(){};
    Obs(int a, int b, int c, int d, int e){
        sx = a, sy = b, ex = c, ey = d, val = e;
    }
} O[MP];

struct Event{
    int x,sy,ey,c;
    Event(){};
    Event(int a, int y1, int y2, int v){
        x = a, sy = y1, ey = y2, c = v;
    }
    bool operator < (const Event &A) const{
        return x<A.x;
    }
} E[2*MP];

int ST[4*MP],SL[4*MP];

void upt(int l, int r, int c, int s, int e, int pos)
{
    if(e<l || s>r) return;
    if(l<=s && e<=r){
        ST[pos] += c;
        if(s==e) SL[pos] = ST[pos] ? 1 : 0;
        else SL[pos] = ST[pos] ? e-s+1 : SL[2*pos] + SL[2*pos+1];
        return;
    }
    int m = (s+e)/2;
    upt(l,r,c,s,m,2*pos);
    upt(l,r,c,m+1,e,2*pos+1);
    SL[pos] = ST[pos]? e-s+1 : SL[2*pos] + SL[2*pos+1];
}

bool isable(int L)
{
    int sx,ex,sy,ey;
    vector<int> X,Y;
    for(int i=0; i<P; i++){
        sx = max(O[i].sx,L);
        ex = min(O[i].ex+L,M+1);
        sy = max(O[i].sy-L+1,1);
        ey = min(O[i].ey,N-L+1);
        X.push_back(sx);
        X.push_back(ex);
        Y.push_back(sy);
        Y.push_back(ey);
        E[i] = Event(sx,sy,ey,1);
        E[i+P] = Event(ex,sy,ey,-1);
    }
    X.push_back(L);
    X.push_back(M+1);
    Y.push_back(1);
    Y.push_back(N-L+1);
    sort(X.begin(),X.end());
    sort(Y.begin(),Y.end());
    X.erase(unique(X.begin(),X.end()),X.end());
    Y.erase(unique(Y.begin(),Y.end()),Y.end());
    for(int i=0; i<2*P; i++){
        E[i].x = lower_bound(X.begin(),X.end(),E[i].x)-X.begin();
        E[i].sy = lower_bound(Y.begin(),Y.end(),E[i].sy)-Y.begin();
        E[i].ey = lower_bound(Y.begin(),Y.end(),E[i].ey)-Y.begin();
    }
    sort(E,E+2*P);
    int tmp = 0;
    for(int i=0; i<2*P; i++){
        if(tmp!=E[i].x){
            if(SL[1]!=Y.size()) return true;
            tmp = E[i].x;
        }
        upt(E[i].sy,E[i].ey,E[i].c,0,Y.size()-1,1);
    }
    return false;
}

int main()
{
    ios_base::sync_with_stdio(0),cin.tie(0);
    freopen("input.txt","r",stdin);
    cin >> M >> N >> B >> P;
    if(B!=0) return 0;
    int sx,ex,sy,ey,val;
    for(int i=0; i<P; i++){
        cin >> sx >> sy >> ex >> ey >> val;
        O[i] = Obs(sx,sy,ex,ey,val);
    }
    int s = 0, e = min(M,N), m;
    while(s<e){
        m = (s+e+1)/2;
        if(isable(m)) s = m;
        else e = m-1;
    }
    cout << s;
}

Compilation message (stderr)

pyramid_base.cpp: In function 'bool isable(int)':
pyramid_base.cpp:75:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(SL[1]!=Y.size()) return true;
                ~~~~~^~~~~~~~~~
pyramid_base.cpp: In function 'int main()':
pyramid_base.cpp:86:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("input.txt","r",stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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