oj.uz

Submission #1000671

# Submission time Handle Problem Language Result Execution time Memory
1000671 2024-06-18T06:55:19 Z bachhoangxuan Pyramid Base (IOI08_pyramid_base) C++17
80 / 100
 5000 ms 106956 KB 
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+5;

int N,M,B,P,C[maxn];
struct Rec{
    int x,y,u,v;
}R[maxn];
int tree[4*maxn],lazy[4*maxn];
vector<int> pos[maxn];

void update(int l,int r,int id,int tl,int tr,int val){
    if(tr<l || r<tl) return;
    if(tl<=l && r<=tr){
        tree[id]+=val;
        lazy[id]+=val;
        return;
    }
    int mid=(l+r)>>1;
    update(l,mid,id<<1,tl,tr,val);update(mid+1,r,id<<1|1,tl,tr,val);
    tree[id]=min(tree[id<<1],tree[id<<1|1])+lazy[id];
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    cin >> N >> M >> B >> P;
    for(int i=1;i<=P;i++) cin >> R[i].x >> R[i].y >> R[i].u >> R[i].v >> C[i];
    auto check = [&](int d){
        for(int i=1;i<=N-d+1;i++) pos[i].clear();
        for(int i=1;i<=4*(M-d+1);i++) tree[i]=lazy[i]=0;
        for(int i=1;i<=P;i++){
            int x=max(1,R[i].x-d+1),y=max(1,R[i].y-d+1),u=R[i].u,v=R[i].v;
            pos[x].push_back(i);pos[u+1].push_back(i);
        }
        for(int i=1;i<=N-d+1;i++){
            for(int id:pos[i]){
                int l=max(1,R[id].y-d+1),r=R[id].v,c=C[id];
                if(i==R[id].u+1) c=-c;
                update(1,M-d+1,1,l,r,c);
            }
            //cout << i << ' ' << tree[1] << '\n';
            if(tree[1]<=B) return true;
        }
        return false;
    };
    int l=1,r=min(N,M),res=0;
    while(l<=r){
        int mid=(l+r)>>1;
        if(check(mid)) res=mid,l=mid+1;
        else r=mid-1;
    }
    cout << res << '\n';
}

Compilation message

pyramid_base.cpp: In lambda function:
pyramid_base.cpp:33:37: warning: unused variable 'y' [-Wunused-variable]
   33 |             int x=max(1,R[i].x-d+1),y=max(1,R[i].y-d+1),u=R[i].u,v=R[i].v;
      |                                     ^
pyramid_base.cpp:33:66: warning: unused variable 'v' [-Wunused-variable]
   33 |             int x=max(1,R[i].x-d+1),y=max(1,R[i].y-d+1),u=R[i].u,v=R[i].v;
      |                                                                  ^

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23900 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 24412 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 27224 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 39964 KB Output is correct
2 Correct 122 ms 55636 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 53792 KB Output is correct
2 Correct 38 ms 39748 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 24668 KB Output is correct
2 Correct 37 ms 24620 KB Output is correct
3 Correct 32 ms 24664 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 29520 KB Output is correct
2 Correct 184 ms 30288 KB Output is correct
3 Correct 144 ms 30544 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 46560 KB Output is correct
2 Correct 40 ms 29068 KB Output is correct
3 Correct 96 ms 56904 KB Output is correct
4 Correct 325 ms 63212 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 294 ms 57428 KB Output is correct
2 Correct 597 ms 66256 KB Output is correct
3 Correct 91 ms 45652 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 48724 KB Output is correct
2 Correct 745 ms 68944 KB Output is correct
3 Correct 679 ms 68740 KB Output is correct
4 Correct 776 ms 69068 KB Output is correct
5 Correct 750 ms 69068 KB Output is correct
6 Correct 62 ms 46164 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3548 ms 95816 KB Output is correct
2 Correct 503 ms 61616 KB Output is correct

Subtask #14
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5048 ms 101620 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 5027 ms 106956 KB Time limit exceeded
2 Halted 0 ms 0 KB -