oj.uz

Submission #883737

# Submission time Handle Problem Language Result Execution time Memory
883737 2023-12-05T22:50:13 Z andro Wall (IOI14_wall) C++14
32 / 100
 313 ms 53076 KB 
#include <bits/stdc++.h>
using namespace std;
int O=0;
const int N=2e6+5;
struct segtree{
    int t[4*N]={(int)-1e9};
    map<pair<int,int>,int>M;
    void build(int v,int tl,int tr){
        M[{tl,tr}]=v;
        if(tl==tr){

        }
        else {
            int tm=(tl+tr)/2;
            build(v*2,tl,tm);
            build(v*2+1,tm+1,tr);
        }
    }
    void reset(){
        for(int i=0;i<N;i++)t[i]=1e9;
    }
    void update_min(int v,int tl,int tr,int l,int r,int x){
        if(tl>=l&&tr<=r){
            t[v]=min(t[v],x);
            return;
        }
        if(tl>r||tr<l)return;
        int tm=(tl+tr)/2;
        update_min(v*2,tl,tm,l,r,x);
        update_min(v*2+1,tm+1,tr,l,r,x);
    }
    void update_max(int v,int tl,int tr,int l,int r,int x){
        if(tl>=l&&tr<=r){
            t[v]=max(t[v],x);
            return;
        }
        if(tl>r||tr<l)return;
        int tm=(tl+tr)/2;
        update_max(v*2,tl,tm,l,r,x);
        update_max(v*2+1,tm+1,tr,l,r,x);
    }
    int query_max(int v){
        v=M[{v,v}];
        int ans=-1e9;
        while(v){
            ans=max(ans,t[v]);
            v/=2;
        }
        return ans;
    }
    int query_min(int v){
        v=M[{v,v}];
        int ans=1e9;
        while(v){
            ans=min(ans,t[v]);
            v/=2;
        }
        return ans;
    }
}segg;
void buildWall(int n, int k, int op[], int left[], int right[],int height[], int finalHeight[]){
    for(int i=0;i<n;i++)finalHeight[i]=0;
    if(n<=10000&&k<=5000){
        for(int i=0;i<k;i++){
            if(op[i]==1){
                for(int j=left[i];j<=right[i];j++)finalHeight[j]=max(finalHeight[j],height[i]);
            }
            else {
                for(int j=left[i];j<=right[i];j++)finalHeight[j]=min(finalHeight[j],height[i]);
            }
        }
        return;
    }
    int subtask=1;
    int bio=0;
    for(int i=0;i<k;i++){
        if(op[i]==1){
            if(bio){
                subtask=0;
            }
        }
        else {
            bio=1;
        }
    }
    if(subtask){
    segg.build(1,0,n-1);
    for(int i=0;i<k;i++){
        if(op[i]==2)break;
        segg.update_max(1,0,n-1,left[i],right[i],height[i]);
    }
    for(int i=0;i<n;i++){
        int u=segg.query_max(i);
        finalHeight[i]=u;
    }
    segg.reset();
    for(int i=0;i<n;i++)segg.update_min(1,0,n-1,i,i,finalHeight[i]);
    for(int i=0;i<k;i++){
        if(op[i]==1)continue;
        segg.update_min(1,0,n-1,left[i],right[i],height[i]);
    }
    for(int i=0;i<n;i++){
        finalHeight[i]=segg.query_min(i);
    }
    return;
    }
}/*
int main(){
    int n,k;
    cin>>n>>k;
    int op[k];
    int l[k];
    int r[k];
    int x[k];
    for(int i=0;i<k;i++)cin>>op[i]>>l[i]>>r[i]>>x[i];
    int ans[n];
    for(int i=0;i<n;i++)ans[i]=0;
    buildWall(n,k,op,l,r,x,ans);
    for(int i=0;i<n;i++)cout<<ans[i]<<" ";
}*/
/*
10
6
1 1 8 4
2 4 9 1
2 3 6 5
1 0 5 3
1 2 2 5
2 6 7 0



10
4
1 1 8 4
1 0 5 3
1 2 2 5
2 6 7 0
3 4 5 4 4 4 0 0 4 0
*/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 31584 KB Output is correct
2 Correct 5 ms 31636 KB Output is correct
3 Correct 5 ms 31580 KB Output is correct
4 Correct 17 ms 31860 KB Output is correct
5 Correct 17 ms 31836 KB Output is correct
6 Correct 17 ms 31836 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 31580 KB Output is correct
2 Correct 108 ms 39332 KB Output is correct
3 Correct 101 ms 37208 KB Output is correct
4 Correct 296 ms 52564 KB Output is correct
5 Correct 218 ms 53076 KB Output is correct
6 Correct 207 ms 53012 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 31576 KB Output is correct
2 Correct 5 ms 31580 KB Output is correct
3 Correct 5 ms 31580 KB Output is correct
4 Correct 17 ms 31852 KB Output is correct
5 Correct 17 ms 31864 KB Output is correct
6 Correct 17 ms 31836 KB Output is correct
7 Correct 4 ms 31624 KB Output is correct
8 Correct 103 ms 39436 KB Output is correct
9 Correct 102 ms 37204 KB Output is correct
10 Correct 313 ms 52820 KB Output is correct
11 Correct 224 ms 53072 KB Output is correct
12 Correct 209 ms 53076 KB Output is correct
13 Correct 4 ms 31580 KB Output is correct
14 Incorrect 100 ms 39416 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 31580 KB Output is correct
2 Correct 5 ms 31576 KB Output is correct
3 Correct 5 ms 31580 KB Output is correct
4 Correct 17 ms 31836 KB Output is correct
5 Correct 17 ms 31860 KB Output is correct
6 Correct 17 ms 31836 KB Output is correct
7 Correct 4 ms 31580 KB Output is correct
8 Correct 105 ms 39536 KB Output is correct
9 Correct 101 ms 37248 KB Output is correct
10 Correct 291 ms 52524 KB Output is correct
11 Correct 219 ms 53000 KB Output is correct
12 Correct 210 ms 53076 KB Output is correct
13 Correct 4 ms 31580 KB Output is correct
14 Incorrect 101 ms 39392 KB Output isn't correct
15 Halted 0 ms 0 KB -