oj.uz

답안 #965588

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
965588 2024-04-19T01:08:50 Z idiotcomputer Pyramid Base (IOI08_pyramid_base) C++11
65 / 100
 4646 ms 38016 KB 
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define f first
#define s second 

const int mxP = 4e5;
const int mxN = 1e6;
int n,m;

int segtree[4*mxN+1];
int laz[4*mxN+1];
int curr;

void build(int l = 0, int r = n-1, int idx = 0){
    if (r+1<curr){
        segtree[idx] = m+1;
        laz[idx] = m+1;
        return;
    }
    segtree[idx] = 0;
    laz[idx] = 0;
    if (l == r) return;
    int m = (l+r)/2;
    build(l,m,2*idx+1);
    build(m+1,r,2*idx+2);
}

void upd(int tl, int tr, int v, int l = 0, int r = n-1, int idx = 0){
    if (l > tr || r < tl || r+1<curr) return;
    if (l >= tl && r <= tr){
        laz[idx] = max(laz[idx],v);
        return;
    }
    laz[2*idx+1] = max(laz[idx],laz[2*idx+1]);
    laz[2*idx+2] = max(laz[idx],laz[2*idx+2]);
    laz[idx] = 0;
    int m = (l+r)/2;
    upd(tl,tr,v,l,m,2*idx+1);
    upd(tl,tr,v,m+1,r,2*idx+2);
    segtree[idx] = min(max(segtree[2*idx+1],laz[2*idx+1]),max(segtree[2*idx+2],laz[2*idx+2]));
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int b,p;
    cin >> m >> n >> b >> p;
    
    
    int r[p];
    pii y[p];
    vector<pii> vals(p);
    int x1,y1,x2,y2,c1;
    for (int i =0; i < p; i++){
        cin >> x1 >> y1 >> x2 >> y2 >> c1;
        x1 -= 1;
        y1 -= 1;
        x2 -= 1;
        y2 -= 1;
        r[i] = x2;
        y[i] = {y1,y2};
        vals[i] = {x1,i};
    }
    if (b > 0){
       // while (true) continue;
        return 0;
    }
    sort(vals.begin(),vals.end());
    
    int start = 0;
    int end = min(n,m)+1;
    bool w;
    int best;
    while (end - start > 1){
        curr = (start+end)/2;
        build();
        w = false;
    //    cout << curr << ": ";
        for (int i = 0; i < p; i++){
           // cout << vals[i].s << " - " << vals[i].f << " " << r[vals[i].s] << " " << y[vals[i].s].f << ',' << y[vals[i].s].s << "  ";
            best = max(laz[0],segtree[0]);
            if (vals[i].f-best >= curr){
                w = true;
                break;
            }
            upd(y[vals[i].s].f,min(n-1,y[vals[i].s].s+curr-1),r[vals[i].s]+1);
        }
        //cout << '\n';
        best = max(laz[0],segtree[0]);
        if (m-best >= curr) w = true;
        if (w) start = curr;
        else end = curr;
    }
    cout << start << "\n";
    return 0;
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct

Subtask #3
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2648 KB Output is correct

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 6748 KB Output is correct

Subtask #6
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 19036 KB Output is correct
2 Correct 86 ms 19036 KB Output is correct

Subtask #7
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 88 ms 19120 KB Output is correct
2 Correct 34 ms 19036 KB Output is correct

Subtask #8
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 860 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 856 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 860 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1813 ms 23052 KB Output is correct
2 Correct 179 ms 15640 KB Output is correct

Subtask #14
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3098 ms 24960 KB Output is correct
2 Correct 2748 ms 33120 KB Output is correct
3 Correct 1963 ms 32592 KB Output is correct

Subtask #15
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3315 ms 26912 KB Output is correct
2 Correct 4416 ms 38016 KB Output is correct
3 Correct 4646 ms 37972 KB Output is correct
4 Correct 3900 ms 37800 KB Output is correct
5 Correct 2856 ms 37968 KB Output is correct