oj.uz

Submission #883736

# Submission time Handle Problem Language Result Execution time Memory
883736 2023-12-05T22:48:58 Z andro Wall (IOI14_wall) C++14
32 / 100
 310 ms 53096 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;
    }
    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);
    }
}/*
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 8 ms 31580 KB Output is correct
2 Correct 5 ms 31836 KB Output is correct
3 Correct 5 ms 31580 KB Output is correct
4 Correct 17 ms 31864 KB Output is correct
5 Correct 19 ms 31836 KB Output is correct
6 Correct 20 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 122 ms 39476 KB Output is correct
3 Correct 111 ms 37336 KB Output is correct
4 Correct 310 ms 52560 KB Output is correct
5 Correct 229 ms 53008 KB Output is correct
6 Correct 213 ms 53000 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 31836 KB Output is correct
3 Correct 5 ms 31580 KB Output is correct
4 Correct 17 ms 31856 KB Output is correct
5 Correct 18 ms 31832 KB Output is correct
6 Correct 18 ms 31836 KB Output is correct
7 Correct 4 ms 31580 KB Output is correct
8 Correct 114 ms 39516 KB Output is correct
9 Correct 107 ms 37212 KB Output is correct
10 Correct 297 ms 52560 KB Output is correct
11 Correct 223 ms 53068 KB Output is correct
12 Correct 213 ms 53072 KB Output is correct
13 Correct 4 ms 31600 KB Output is correct
14 Incorrect 115 ms 39500 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 31580 KB Output is correct
3 Correct 5 ms 31580 KB Output is correct
4 Correct 17 ms 31836 KB Output is correct
5 Correct 18 ms 31860 KB Output is correct
6 Correct 18 ms 31836 KB Output is correct
7 Correct 4 ms 31580 KB Output is correct
8 Correct 118 ms 39860 KB Output is correct
9 Correct 103 ms 37296 KB Output is correct
10 Correct 300 ms 52560 KB Output is correct
11 Correct 236 ms 53008 KB Output is correct
12 Correct 214 ms 53096 KB Output is correct
13 Correct 4 ms 31576 KB Output is correct
14 Incorrect 115 ms 39384 KB Output isn't correct
15 Halted 0 ms 0 KB -