oj.uz

Submission #894043

# Submission time Handle Problem Language Result Execution time Memory
894043 2023-12-27T20:51:07 Z raul2008487 Wall (IOI14_wall) C++17
61 / 100
 2519 ms 262144 KB 
#include<bits/stdc++.h>
#include "wall.h"
#define ll long long
#define vl vector<ll>
#define pll pair<ll,ll>
#define in insert
#define fi first
#define se second
#define all(v) v.begin(), v.end()
using namespace std;
const int sz = 2e6+6;
const ll dh = 1e9;
vector<array<ll, 2>> st(sz<<2), res(sz);
bool last[sz];
void comp(ll x1, ll x2){
    if(st[x1][0] > st[x2][1]){
        st[x2] = {st[x1][0], st[x1][0]};
    }
    else if(st[x1][1] < st[x2][0]){
        st[x2] = {st[x1][1], st[x1][1]};
    }
    else{
        st[x2] = {max(st[x1][0], st[x2][0]), min(st[x1][1], st[x2][1])};
    }
}
void push(ll v, ll l, ll r){
    if(l == r){return ;}
    comp(v, v*2);
    comp(v, v*2+1);
    st[v] = {0, dh};
}
void build(ll v, ll l, ll r){
    if(l == r){
        last[v] = 1;
        res[v] = {0, 0};
        return ;
    }
    ll m = (l + r)>>1;
    build(v*2, l, m);
    build(v*2+1, m+1, r);
}
void update(ll v, ll tl, ll tr, ll l, ll r, ll val, ll  type){
    if(max(l, tl) > min(r, tr)){return ;}
    push(v, tl, tr);
    if(tl >= l && tr <= r){
        if(last[v]){
            if(type == 1){
                st[v][0] = max(st[v][0], val);
                st[v][1] = max(st[v][1], val);
            }
            else{
                st[v][0] = min(st[v][0], val);
                st[v][1] = min(st[v][1], val);
            }
            return ;
        }
        if(type == 1){
            st[v] = {val, dh};
        }
        else{
            st[v] = {0, val};
        }
        push(v, tl, tr);
        return ;
    }
    ll tm = (tl+tr)>>1;
    update(v*2, tl, tm, l, r, val, type);
    update(v*2+1, tm+1, tr, l, r, val, type);
}
void trav(ll v, ll tl, ll tr){
    if(tl == tr){
        res[tl] = st[v];
        return ;
    }
    push(v, tl, tr);
    ll tm = (tl + tr)>>1;
    trav(v*2, tl, tm);
    trav(v*2+1, tm+1, tr);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    ll i, j, z = 0;
    for(i=0;i<=(n<<2);i++){
        st[i] = {0, dh};
    }
    build(1, 0, n-1);
    for(i=0;i<k;i++){
        update(1, 0, n-1, left[i], right[i], height[i], op[i]);
    }
    trav(1, 0, n-1);
    for(i=0;i<n;i++){
        finalHeight[i] = res[i][0];
    }
}

/*
10 6
1 1 8 4
0 4 9 1
0 3 6 5
1 0 5 3
1 2 2 5
0 6 7 0
*/

Compilation message

wall.cpp: In function 'void buildWall(int, int, int*, int*, int*, int*, int*)':
wall.cpp:81:11: warning: unused variable 'j' [-Wunused-variable]
   81 |     ll i, j, z = 0;
      |           ^
wall.cpp:81:14: warning: unused variable 'z' [-Wunused-variable]
   81 |     ll i, j, z = 0;
      |              ^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 157028 KB Output is correct
2 Correct 25 ms 157020 KB Output is correct
3 Correct 24 ms 157052 KB Output is correct
4 Correct 28 ms 157012 KB Output is correct
5 Correct 27 ms 157020 KB Output is correct
6 Correct 27 ms 157012 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 156776 KB Output is correct
2 Correct 119 ms 164608 KB Output is correct
3 Correct 160 ms 160340 KB Output is correct
4 Correct 424 ms 165456 KB Output is correct
5 Correct 234 ms 166052 KB Output is correct
6 Correct 232 ms 166048 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 156764 KB Output is correct
2 Correct 24 ms 157020 KB Output is correct
3 Correct 23 ms 156992 KB Output is correct
4 Correct 29 ms 157188 KB Output is correct
5 Correct 26 ms 157008 KB Output is correct
6 Correct 26 ms 157020 KB Output is correct
7 Correct 23 ms 156816 KB Output is correct
8 Correct 150 ms 164688 KB Output is correct
9 Correct 162 ms 160340 KB Output is correct
10 Correct 409 ms 165476 KB Output is correct
11 Correct 234 ms 165968 KB Output is correct
12 Correct 238 ms 166128 KB Output is correct
13 Correct 23 ms 156760 KB Output is correct
14 Correct 120 ms 164816 KB Output is correct
15 Correct 62 ms 157524 KB Output is correct
16 Correct 607 ms 165972 KB Output is correct
17 Correct 248 ms 165796 KB Output is correct
18 Correct 245 ms 165800 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 156860 KB Output is correct
2 Correct 24 ms 156996 KB Output is correct
3 Correct 23 ms 157020 KB Output is correct
4 Correct 28 ms 157156 KB Output is correct
5 Correct 27 ms 157008 KB Output is correct
6 Correct 27 ms 157016 KB Output is correct
7 Correct 23 ms 156896 KB Output is correct
8 Correct 118 ms 164608 KB Output is correct
9 Correct 157 ms 160356 KB Output is correct
10 Correct 416 ms 165540 KB Output is correct
11 Correct 242 ms 165976 KB Output is correct
12 Correct 234 ms 165924 KB Output is correct
13 Correct 26 ms 157016 KB Output is correct
14 Correct 121 ms 164764 KB Output is correct
15 Correct 54 ms 157548 KB Output is correct
16 Correct 600 ms 165800 KB Output is correct
17 Correct 265 ms 165712 KB Output is correct
18 Correct 240 ms 165684 KB Output is correct
19 Runtime error 2519 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -