oj.uz

Submission #95241

# Submission time Handle Problem Language Result Execution time Memory
95241 2019-01-29T00:24:46 Z easrui Pyramid Base (IOI08_pyramid_base) C++14
10 / 100
 5000 ms 44152 KB 
#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

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;
                ~~~~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 504 KB Output isn't correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 500 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 504 KB Output isn't correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 380 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5082 ms 26560 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #14
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5087 ms 36740 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #15
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5007 ms 44152 KB Time limit exceeded
2 Halted 0 ms 0 KB -