oj.uz

Submission #261592

# Submission time Handle Problem Language Result Execution time Memory
261592 2020-08-11T21:54:53 Z Hehehe Wall (IOI14_wall) C++14
100 / 100
 849 ms 77688 KB 
#include<bits/stdc++.h> //:3
using namespace std;
typedef long long ll;
#define all(a) (a).begin(), (a).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define sz(x) (int)((x).size())
//#define int long long
#include "wall.h"

const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};

const int inf = 2e9;
const ll mod = 1e9 + 7;
const int N = 2e6 + 11;
const ll INF64 = 3e18 + 1;
const double eps = 1e-14;
const double PI = acos(-1);

//ifstream in(".in");
//ofstream out(".out");

int mx[4*N], mn[4*N], ans[N];

void build(int v, int l, int r){
    mx[v] = 0;
    mn[v] = inf;
    if(l == r)return;
    int mid = (l + r) >> 1;
    build(2*v, l, mid);
    build(2*v + 1, mid + 1, r);
}

void push(int v, int l, int r){
    if(l == r)return;

    int L = 2*v, R = 2*v + 1;

    mx[L] = min(mx[L],mn[v]);
    mn[L] = min(mn[L],mn[v]);

    mn[L] = max(mn[L],mx[v]);
    mx[L] = max(mx[L],mx[v]);


    mx[R] = min(mx[R],mn[v]);
    mn[R] = min(mn[R],mn[v]);

    mn[R] = max(mn[R],mx[v]);
    mx[R] = max(mx[R],mx[v]);

    mn[v] = inf;
    mx[v] = 0;
}

void update(int v, int tl, int tr, int l, int r, int H, int type){

    //if(tl > r || tr < l)return;
    push(v, tl, tr);

    if(l <= tl && tr <= r){
        if(type == 1){
            mx[v] = max(mx[v], H);
            mn[v] = max(mn[v], H);
        }else{
            mx[v] = min(mx[v], H);
            mn[v] = min(mn[v], H);
        }
        return;
    }

    int mid = (tl + tr) >> 1;
    if(l <= mid)update(2*v, tl, mid, l, r, H, type);
    if(r > mid)update(2*v + 1, mid + 1, tr, l, r, H, type);
}

void WooHoo(int v, int l, int r){
    push(v, l, r);
    if(l == r){
        ans[l] = mx[v];
        return;
    }
    int mid = (l + r) >> 1;
    WooHoo(2*v, l, mid);
    WooHoo(2*v + 1, mid + 1, r);
}

void buildWall (int n, int k, int op[], int left[], int right[], int h[], int finalHeight[]){

    build(1, 1, n);

    for(int i = 0; i < k; i++){
        update(1, 1, n, left[i] + 1, right[i] + 1, h[i], op[i]);
    }

    WooHoo(1, 1, n);

    for(int i = 0; i < n; i++)finalHeight[i] = ans[i + 1];

}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 6 ms 896 KB Output is correct
5 Correct 6 ms 896 KB Output is correct
6 Correct 6 ms 896 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 216 ms 8184 KB Output is correct
3 Correct 198 ms 8188 KB Output is correct
4 Correct 554 ms 20856 KB Output is correct
5 Correct 348 ms 22024 KB Output is correct
6 Correct 326 ms 20344 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 416 KB Output is correct
4 Correct 6 ms 896 KB Output is correct
5 Correct 11 ms 896 KB Output is correct
6 Correct 6 ms 960 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 193 ms 14036 KB Output is correct
9 Correct 212 ms 8104 KB Output is correct
10 Correct 623 ms 20828 KB Output is correct
11 Correct 352 ms 21912 KB Output is correct
12 Correct 323 ms 20344 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 218 ms 13968 KB Output is correct
15 Correct 31 ms 2168 KB Output is correct
16 Correct 575 ms 21112 KB Output is correct
17 Correct 342 ms 20600 KB Output is correct
18 Correct 336 ms 20472 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 9 ms 896 KB Output is correct
5 Correct 6 ms 896 KB Output is correct
6 Correct 7 ms 888 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 197 ms 13948 KB Output is correct
9 Correct 193 ms 8056 KB Output is correct
10 Correct 580 ms 20788 KB Output is correct
11 Correct 345 ms 22008 KB Output is correct
12 Correct 317 ms 20292 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 185 ms 14024 KB Output is correct
15 Correct 31 ms 2168 KB Output is correct
16 Correct 538 ms 21208 KB Output is correct
17 Correct 323 ms 20472 KB Output is correct
18 Correct 321 ms 20600 KB Output is correct
19 Correct 796 ms 77560 KB Output is correct
20 Correct 808 ms 75000 KB Output is correct
21 Correct 849 ms 77432 KB Output is correct
22 Correct 797 ms 75004 KB Output is correct
23 Correct 802 ms 75056 KB Output is correct
24 Correct 791 ms 74924 KB Output is correct
25 Correct 789 ms 74872 KB Output is correct
26 Correct 813 ms 77688 KB Output is correct
27 Correct 804 ms 77560 KB Output is correct
28 Correct 801 ms 74872 KB Output is correct
29 Correct 799 ms 74920 KB Output is correct
30 Correct 818 ms 75028 KB Output is correct