oj.uz

Submission #1103951

# Submission time Handle Problem Language Result Execution time Memory
1103951 2024-10-22T12:20:42 Z vjudge1 Wall (IOI14_wall) C++11
61 / 100
 1004 ms 262144 KB 
#include <iostream>
#include <map>
#include <unordered_map>
#include <set>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include "wall.h"
using namespace std;
#define ll long long
#define PLL pair<ll, ll>
#define PB push_back
#define F first
#define S second
#define MP make_pair
 
void build(ll v, ll l, ll r, vector<PLL> &t, vector<PLL> &actu){
    actu[v].F = -1;
    actu[v].S = -1;
    if(l==r){
        t[v] = MP(0ll,0ll);
        return;
    }
    ll m = (l+r)/2;
    build(2*v,l,m,t,actu);
    build(2*v+1,m+1,r,t,actu);
    t[v].F = min(t[2*v].F,t[2*v+1].F);
    t[v].S = max(t[2*v].S,t[2*v+1].S);
}
 
void propagate(ll v, ll l, ll r, vector<PLL>&t, vector<PLL>&actu){
  //cout<<"propagating: "<<v<<" "<<l<<" "<<r<<endl;
  //cout<<t[v].F<<" "<<t[v].S<<endl;
 
  //cout<<actu[v].F<<" "<<actu[v].S<<endl;
    if(actu[v].F!=-1){
        //if(t[v].S>actu[v].F){
            t[v].S = min(actu[v].F,t[v].S);
            t[v].F = min(t[v].F,actu[v].F);
            if(l!=r){
                actu[2*v].F = min(actu[v].F,actu[2*v].F);
                if(actu[2*v].F==-1){
                    actu[2*v].F = actu[v].F;
                }
                if(actu[2*v].S>actu[v].F){
                    actu[2*v].S = actu[v].F;
                    actu[2*v].F = actu[v].F;
                }
                actu[2*v+1].F = min(actu[v].F,actu[2*v+1].F);
                if(actu[2*v+1].F==-1){
                    actu[2*v+1].F = actu[v].F;
                }
                if(actu[2*v+1].S>actu[v].F){
                    actu[2*v+1].S = actu[v].F;
                    actu[2*v+1].F = actu[v].F;
                }
            }
        //}
        actu[v].F = -1;
    }
    if(actu[v].S!=-1){
        //if(t[v].F<actu[v].S){
            t[v].F = max(actu[v].S,t[v].F);
            t[v].S = max(t[v].S,actu[v].S);
            if(l!=r){
                actu[2*v].S = max(actu[v].S,actu[2*v].S);
                if(actu[2*v].F<actu[v].S and actu[2*v].F!=-1){
                    actu[2*v].F = actu[v].S;
                    actu[2*v].S = actu[v].S;
                }
                actu[2*v+1].S = max(actu[v].S,actu[2*v+1].S);
                if(actu[2*v+1].F<actu[v].S and actu[2*v+1].F!=-1){
                    actu[2*v+1].F = actu[v].S;
                    actu[2*v+1].S = actu[v].S;
                }
            }
        //}
        actu[v].S = -1;
    }
    //cout<<t[v].F<<" "<<t[v].S<<endl;
}
 
void adding(ll v, ll l, ll r, ll lx, ll rx, ll h, vector<PLL>&t, vector<PLL>&actu){ 
    if(actu[v].F!=-1 or actu[v].S!=-1){
        propagate(v,l,r,t,actu);
    } 
    if(lx<=l and r<=rx){
        if(actu[v].F<h and actu[v].F !=-1){
            actu[v].S = h;
            actu[v].F = h;
        }
        else{
            actu[v].S = max(actu[v].S,h);
        }
        propagate(v,l,r,t,actu);
        return;
    }
    if(l>rx or r<lx){
        return;
    }
    ll m = (l+r)/2;
    adding(2*v,l,m,lx,rx,h,t,actu);
    adding(2*v+1,m+1,r,lx,rx,h,t,actu);
    t[v].F = min(t[2*v].F,t[2*v+1].F);
    t[v].S = max(t[2*v].S,t[2*v+1].S);
}
 
void removing (ll v, ll l, ll r, ll lx, ll rx, ll h, vector<PLL>&t, vector<PLL>&actu){  
    if(actu[v].F!=-1 or actu[v].S!=-1){
        propagate(v,l,r,t,actu);
    }
    if(lx<=l and r<=rx){
        //actu[v].F = h;
        if(actu[v].S>h){
            actu[v].S = h;
            actu[v].F = h;
        }
        else if(actu[v].F!=-1){
            actu[v].F = min(actu[v].F,h);
        }
        else{
            actu[v].F = h;
        }
        propagate(v,l,r,t,actu);
        return;
    }
    if(l>rx or r<lx){
        return;
    }
    ll m = (l+r)/2;
    removing(2*v,l,m,lx,rx,h,t,actu);
    removing(2*v+1,m+1,r,lx,rx,h,t,actu);
    t[v].F = min(t[2*v].F,t[2*v+1].F);
    t[v].S = max(t[2*v].S,t[2*v+1].S);
}
 
void recover(ll v, ll l, ll r, vector<PLL> &t,vector<PLL> &actu, vector<int> &ans){
    //cout<<v<<" "<<l<<" "<<r<<endl;
    if(actu[v].F!=-1 or actu[v].S!=-1){
        propagate(v,l,r,t,actu); 
    }
    if(l==r){
        //cout<<t[v].F<<endl;
        ans[l] = t[v].F;
        return;
    }
    ll m = (l+r)/2;
    recover(2*v,l,m,t,actu,ans);
    recover(2*v+1,m+1,r,t,actu,ans);
}
 
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    vector<PLL> t(4*n), actu(4*n);
    build(1,0,n-1,t,actu);
    for(ll i=0; i<k; i++){
        //cout<<"### "<<i<<" ###"<<endl;
        if(op[i]==1){
            adding(1,0,n-1,left[i],right[i],height[i],t,actu);
        }
        else{
            removing(1,0,n-1,left[i],right[i],height[i],t,actu);
        }
    }
    vector<int> ans(n);
    recover(1,0,n-1,t,actu,ans);
    for(int i=0; i<n; i++){
        finalHeight[i] = (int)ans[i];
    }
    return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 336 KB Output is correct
3 Correct 2 ms 336 KB Output is correct
4 Correct 8 ms 1872 KB Output is correct
5 Correct 5 ms 1896 KB Output is correct
6 Correct 5 ms 1872 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 85 ms 13896 KB Output is correct
3 Correct 173 ms 9712 KB Output is correct
4 Correct 662 ms 31160 KB Output is correct
5 Correct 224 ms 31560 KB Output is correct
6 Correct 256 ms 29956 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 336 KB Output is correct
3 Correct 2 ms 336 KB Output is correct
4 Correct 9 ms 2044 KB Output is correct
5 Correct 6 ms 1872 KB Output is correct
6 Correct 6 ms 1872 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 123 ms 13896 KB Output is correct
9 Correct 198 ms 9808 KB Output is correct
10 Correct 730 ms 31136 KB Output is correct
11 Correct 238 ms 31520 KB Output is correct
12 Correct 258 ms 30044 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 94 ms 13896 KB Output is correct
15 Correct 42 ms 3648 KB Output is correct
16 Correct 1004 ms 31164 KB Output is correct
17 Correct 269 ms 30536 KB Output is correct
18 Correct 247 ms 30536 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 448 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 9 ms 1872 KB Output is correct
5 Correct 5 ms 1872 KB Output is correct
6 Correct 7 ms 1872 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 96 ms 14076 KB Output is correct
9 Correct 204 ms 9732 KB Output is correct
10 Correct 722 ms 31172 KB Output is correct
11 Correct 241 ms 31560 KB Output is correct
12 Correct 229 ms 30024 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 95 ms 13896 KB Output is correct
15 Correct 47 ms 3668 KB Output is correct
16 Correct 932 ms 31184 KB Output is correct
17 Correct 253 ms 30544 KB Output is correct
18 Correct 262 ms 30536 KB Output is correct
19 Runtime error 578 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -