oj.uz

Submission #95217

# Submission time Handle Problem Language Result Execution time Memory
95217 2019-01-28T15:53:14 Z easrui Pyramid Base (IOI08_pyramid_base) C++14
25 / 100
 5000 ms 38740 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],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,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 len,tmp = L;
    long long S = 0;
    for(int i=0; i<2*P; i++){
        if(tmp!=E[i].x){
            len = sum(0,Y.size(),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() << '\n';
    if(S==(long long)(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;
    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:108:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(S==(long long)(X.size()-1)*Y.size()) return false;
        ~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 376 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 504 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 504 KB Output is correct

Subtask #6
0 / 5.0

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

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 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 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 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 5095 ms 19796 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 5010 ms 30168 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 5097 ms 38740 KB Time limit exceeded
2 Halted 0 ms 0 KB -