oj.uz

Submission #1099974

# Submission time Handle Problem Language Result Execution time Memory
1099974 2024-10-12T09:58:54 Z vjudge1 Wall (IOI14_wall) C++17
61 / 100
 776 ms 262148 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 0 ms 484 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 8 ms 1884 KB Output is correct
5 Correct 5 ms 1884 KB Output is correct
6 Correct 5 ms 1884 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 98 ms 14076 KB Output is correct
3 Correct 188 ms 9884 KB Output is correct
4 Correct 673 ms 31152 KB Output is correct
5 Correct 259 ms 31524 KB Output is correct
6 Correct 241 ms 30080 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 2 ms 448 KB Output is correct
4 Correct 8 ms 1948 KB Output is correct
5 Correct 5 ms 1884 KB Output is correct
6 Correct 4 ms 1884 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 91 ms 14084 KB Output is correct
9 Correct 171 ms 9812 KB Output is correct
10 Correct 596 ms 31060 KB Output is correct
11 Correct 216 ms 31572 KB Output is correct
12 Correct 233 ms 30056 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 125 ms 13908 KB Output is correct
15 Correct 43 ms 3640 KB Output is correct
16 Correct 776 ms 31116 KB Output is correct
17 Correct 213 ms 30552 KB Output is correct
18 Correct 265 ms 30428 KB Output is correct

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 2 ms 348 KB Output is correct
4 Correct 7 ms 1724 KB Output is correct
5 Correct 4 ms 1884 KB Output is correct
6 Correct 4 ms 1884 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 81 ms 13872 KB Output is correct
9 Correct 173 ms 9816 KB Output is correct
10 Correct 592 ms 31080 KB Output is correct
11 Correct 253 ms 31572 KB Output is correct
12 Correct 247 ms 30036 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 88 ms 13932 KB Output is correct
15 Correct 42 ms 3668 KB Output is correct
16 Correct 771 ms 31064 KB Output is correct
17 Correct 253 ms 30588 KB Output is correct
18 Correct 219 ms 30388 KB Output is correct
19 Runtime error 503 ms 262148 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -