oj.uz

Submission #1043481

# Submission time Handle Problem Language Result Execution time Memory
1043481 2024-08-04T09:57:45 Z nisanduu Wall (IOI14_wall) C++14
32 / 100
 264 ms 32036 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
vector<ll> seg,arr,lazy,seg1,lazy1;
class SGT{
    
    public:
        SGT(ll n){
            seg.resize(4*n + 3,0);
            lazy.resize(4*n + 3,0);
        }
        void update(ll l,ll r,ll ind,ll left,ll right,ll val){
            if(lazy[ind]!=0){
                ll am = lazy[ind];
                seg[ind]=max(seg[ind],am);
                if(l!=r){
                    lazy[2*ind+1] = max(lazy[2*ind+1],lazy[ind]);
                    lazy[2*ind+2] = max(lazy[2*ind+2],lazy[ind]);
                }
                lazy[ind]=0;
            }
            if(r<left||l>right) return;
            if(r<=right&&l>=left){
                ll am = val;
                seg[ind]=max(seg[ind],am);
                if(l!=r){
                    lazy[2*ind+1] = max(lazy[2*ind+1],lazy[ind]);
                    lazy[2*ind+2] = max(lazy[2*ind+2],lazy[ind]);
                }
                return;
            }
            ll mid = (l+r)/2;
            update(l,mid,2*ind+1,left,right,val);
            update(mid+1,r,2*ind+2,left,right,val);
            //seg[ind]=max({seg[ind],seg[2*ind+1],seg[2*ind+2]});
        }
};


class SGT2{
    
    public:
        SGT2(ll n){
            seg1.clear();
            lazy1.clear();
            seg1.resize(4*n + 3,1e9);
            lazy1.resize(4*n + 3,1e9);
        }
        void update(ll l,ll r,ll ind,ll left,ll right,ll val){
            if(lazy1[ind]!=1e9){
                ll am = lazy1[ind];
                seg1[ind]=min(seg1[ind],am);
                if(l!=r){
                    lazy1[2*ind+1] = min(lazy1[2*ind+1],lazy1[ind]);
                    lazy1[2*ind+2] = min(lazy1[2*ind+2],lazy1[ind]);
                }
                lazy1[ind]=1e9;
            }
            if(r<left||l>right) return;
            if(r<=right&&l>=left){
                ll am = val;
                seg1[ind]=min(seg1[ind],am);
                if(l!=r){
                    lazy1[2*ind+1] = min(lazy1[2*ind+1],lazy1[ind]);
                    lazy1[2*ind+2] = min(lazy1[2*ind+2],lazy1[ind]);
                }
                return;
            }
            ll mid = (l+r)/2;
            update(l,mid,2*ind+1,left,right,val);
            update(mid+1,r,2*ind+2,left,right,val);
            //seg[ind]=max({seg[ind],seg[2*ind+1],seg[2*ind+2]});
        }
};

void dfs(ll ind,ll l,ll r,ll maxi,int finalHeight[]){
    if(l==r){
        maxi = max({maxi,lazy[ind],seg[ind]});
        finalHeight[l]=max((ll) finalHeight[l],maxi);
        return;
    }
    ll mid = (l+r)/2;
    maxi = max({maxi,lazy[ind],seg[ind]});
    dfs(2*ind+1,l,mid,maxi,finalHeight);
    dfs(2*ind+2,mid+1,r,maxi,finalHeight);
}

void dfs2(ll ind,ll l,ll r,ll maxi,int finalHeight[]){
    if(l==r){
        maxi = min({maxi,lazy1[ind],seg1[ind]});
        finalHeight[l]=min((ll) finalHeight[l],maxi);
        return;
    }
    ll mid = (l+r)/2;
    maxi = min({maxi,lazy1[ind],seg1[ind]});
    dfs2(2*ind+1,l,mid,maxi,finalHeight);
    dfs2(2*ind+2,mid+1,r,maxi,finalHeight);
}

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++){
            int o = op[i];
            for(int j=left[i];j<=right[i];j++){
                if(finalHeight[j]<height[i] && o==1) finalHeight[j] = height[i];
                if(finalHeight[j]>height[i] && o==2) finalHeight[j] = height[i];
            }
        }
        return;
    }
    bool ok=1;
    SGT sg(n);
    SGT2 sg2(n);
    for(int i=0;i<k;i++){
        int o = op[i];
        if(o==1){
            sg.update(0,n-1,0,left[i],right[i],height[i]);
            continue;
        }
        if(o==2 && ok==1){
            ok=0;
        }
        sg2.update(0,n-1,0,left[i],right[i],height[i]);
    }
    dfs(0,0,n-1,0,finalHeight);
    dfs2(0,0,n-1,1e9,finalHeight);
    
  return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 18 ms 636 KB Output is correct
5 Correct 14 ms 636 KB Output is correct
6 Correct 16 ms 600 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 68 ms 8120 KB Output is correct
3 Correct 84 ms 5972 KB Output is correct
4 Correct 264 ms 21364 KB Output is correct
5 Correct 128 ms 21840 KB Output is correct
6 Correct 139 ms 21828 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 15 ms 604 KB Output is correct
5 Correct 13 ms 636 KB Output is correct
6 Correct 13 ms 604 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 70 ms 14036 KB Output is correct
9 Correct 81 ms 9808 KB Output is correct
10 Correct 256 ms 30804 KB Output is correct
11 Correct 144 ms 32036 KB Output is correct
12 Correct 130 ms 30292 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Incorrect 70 ms 14064 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 13 ms 636 KB Output is correct
5 Correct 13 ms 604 KB Output is correct
6 Correct 14 ms 636 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 73 ms 13952 KB Output is correct
9 Correct 82 ms 9812 KB Output is correct
10 Correct 238 ms 31060 KB Output is correct
11 Correct 132 ms 31828 KB Output is correct
12 Correct 137 ms 30328 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Incorrect 70 ms 13968 KB Output isn't correct
15 Halted 0 ms 0 KB -