oj.uz

Submission #883734

# Submission time Handle Problem Language Result Execution time Memory
883734 2023-12-05T22:42:33 Z andro Wall (IOI14_wall) C++14
32 / 100
 330 ms 63348 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;
    }
}seg;
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;
    }
    seg.build(1,0,n-1);
    for(int i=0;i<k;i++){
        if(op[i]==2)break;
        seg.update_max(1,0,n-1,left[i],right[i],height[i]);
    }
    for(int i=0;i<n;i++){
        int u=seg.query_max(i);
        finalHeight[i]=u;
    }
    seg.reset();
    for(int i=0;i<n;i++)seg.update_min(1,0,n-1,i,i,finalHeight[i]);
    for(int i=0;i<k;i++){
        if(op[i]==1)continue;
        seg.update_min(1,0,n-1,left[i],right[i],height[i]);
    }
    for(int i=0;i<n;i++){
        finalHeight[i]=seg.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 4 ms 31576 KB Output is correct
2 Correct 7 ms 31740 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 32088 KB Output is correct
6 Correct 18 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 117 ms 45212 KB Output is correct
3 Correct 108 ms 40976 KB Output is correct
4 Correct 300 ms 62096 KB Output is correct
5 Correct 222 ms 63176 KB Output is correct
6 Correct 222 ms 61688 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 31580 KB Output is correct
2 Correct 5 ms 31892 KB Output is correct
3 Correct 5 ms 31576 KB Output is correct
4 Correct 17 ms 31836 KB Output is correct
5 Correct 18 ms 31836 KB Output is correct
6 Correct 18 ms 31832 KB Output is correct
7 Correct 5 ms 31576 KB Output is correct
8 Correct 118 ms 45288 KB Output is correct
9 Correct 105 ms 41140 KB Output is correct
10 Correct 330 ms 62124 KB Output is correct
11 Correct 223 ms 63316 KB Output is correct
12 Correct 216 ms 61776 KB Output is correct
13 Correct 4 ms 31580 KB Output is correct
14 Incorrect 119 ms 45276 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 31580 KB Output is correct
2 Correct 6 ms 31884 KB Output is correct
3 Correct 5 ms 31580 KB Output is correct
4 Correct 20 ms 31920 KB Output is correct
5 Correct 18 ms 31836 KB Output is correct
6 Correct 18 ms 31836 KB Output is correct
7 Correct 5 ms 31580 KB Output is correct
8 Correct 118 ms 45392 KB Output is correct
9 Correct 104 ms 41116 KB Output is correct
10 Correct 302 ms 62292 KB Output is correct
11 Correct 245 ms 63348 KB Output is correct
12 Correct 221 ms 61768 KB Output is correct
13 Correct 5 ms 31580 KB Output is correct
14 Incorrect 122 ms 45556 KB Output isn't correct
15 Halted 0 ms 0 KB -