Submission #95212

#	Time	Username	Problem	Language	Result	Execution time	Memory
95212		easrui	Pyramid Base (IOI08_pyramid_base)	C++14	0 / 100	3885 ms	38920 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;
    }
    /*bool operator < (const Obs &A) const{
        return
    }*/
} 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],L[4*MP];

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

int sum(int l, int r, int s, int e, int pos)
{
    if(e<l || s>r) return 0;
    /*if(L[pos] && s!=e){
        ST[2*pos] += L[pos];
        ST[2*pos+1] += L[pos];
        L[2*pos] += L[pos];
        L[2*pos+1] += L[pos];
        L[pos] = 0;
    }*/
    if(l<=s && e<=r){
        if(ST[pos]) return e-s+1;
    }
    if(s==e) return 0;
    int m = (s+e)/2;
    return sum(l,r,s,m,2*pos) + sum(l,r,m+1,e,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+1,M+1);
        sy = max(O[i].sy-L,1);
        ey = min(O[i].ey,N-L+1);
        //cout << sx << ex << sy << ey << '\n';
        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 len,tmp = 0, S = 0;
    for(int i=0; i<2*P; i++){
        if(tmp!=E[i].x){
            len = sum(E[i].sy,E[i].ey,0,Y.size(),1);
            //cout << L << ' ' << len << '\n';
            S += len*(E[i].x-tmp);
            tmp = E[i].x;
        }
        upt(E[i].sy,E[i].ey,E[i].c,0,Y.size(),1);
    }
    //cout << S;
    //cout << X.size()-1) << Y.size();
    if(S==(X.size()-1)*Y.size()) return false;
    return true;
}

int main()
{
    ios_base::sync_with_stdio(0),cin.tie(0);
    //freopen("input.txt","r",stdin);
    cin >> M >> N >> B >> P;
    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 = 1, e = min(M,N), m;
    //isable(5);
    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:111:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(S==(X.size()-1)*Y.size()) return false;
        ~^~~~~~~~~~~~~~~~~~~~~~~

• 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