oj.uz

Submission #53992

# Submission time Handle Problem Language Result Execution time Memory
53992 2018-07-02T07:18:55 Z 노영훈(#1454) Pyramid Base (IOI08_pyramid_base) C++11
35 / 100
 1779 ms 1000 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MX=1010, inf=2e9;

int h, w, n, b;
struct block {
    int x1,y1,x2,y2, c;
} B[MX];
vector<int> X;

bool solve(int a){
    if(a==0) return true;
    // cout<<"SOLVING: "<<a<<'\n';

    map<int, int> P;
    int ans=0;
    for(int x:X){
        if(x+a-1>h) continue;
        // cout<<"X: "<<x<<'\n';
        P.clear();
        for(int i=1; i<=n; i++){
            if(B[i].x1<=x+a-1 && B[i].x2>=x){
                P[B[i].y1]++;
                P[B[i].y2+1]--;
            }
        }
        P[w+1]=P[w+1];
        int cnt=0, prv=1;
        for(auto &p:P){
            int y, df; tie(y,df)=p;
            if(cnt==0){
                if(y-prv>ans){
                }
                ans=max(ans, y-prv);
            }
            cnt+=df; prv=y;
            // cout<<y<<' '<<cnt<<'\n';
        }
    }
    return ans>=a;
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>h>>w>>b>>n;
    for(int i=1; i<=n; i++){
        int x1,y1,x2,y2,c;
        cin>>x1>>y1>>x2>>y2>>c;
        B[i]={x1,y1,x2,y2,c};
    }
    X.push_back(1);
    for(int i=1; i<=n; i++)
        if(B[i].x2<h)
            X.push_back(B[i].x2+1);
    sort(X.begin(), X.end());
    X.resize(unique(X.begin(), X.end())-X.begin());

    int s=0, e=1000000;
    while(s<e){
        int m=(s+e+1)/2;
        if(solve(m)) s=m;
        else e=m-1;
    }
    cout<<s;
    return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 520 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 576 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 421 ms 636 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 330 ms 676 KB Output is correct
2 Correct 1779 ms 676 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 620 ms 676 KB Output is correct
2 Correct 1358 ms 800 KB Output is correct

Subtask #8
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 800 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 916 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #10
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 916 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #11
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 916 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #12
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 932 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #13
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 940 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #14
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 996 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #15
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 1000 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -