oj.uz

Submission #261596

# Submission time Handle Problem Language Result Execution time Memory
261596 2020-08-11T21:59:39 Z Hehehe Wall (IOI14_wall) C++14
100 / 100
 823 ms 66936 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;
 
    //left
    mx[2*v] = min(mx[2*v], mn[v]);
    mx[2*v] = max(mx[2*v], mx[v]);
 
    mn[2*v] = min(mn[2*v], mn[v]);
    mn[2*v] = max(mn[2*v], mx[v]);
 
    //right
    mx[2*v + 1] = min(mx[2*v + 1], mn[v]);
    mx[2*v + 1] = max(mx[2*v + 1], mx[v]);
 
    mn[2*v + 1] = min(mn[2*v + 1], mn[v]);
    mn[2*v + 1] = max(mn[2*v + 1], mx[v]);
 
    mx[v] = 0;
    mn[v] = inf;
}
 
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 1 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 6 ms 768 KB Output is correct
5 Correct 5 ms 768 KB Output is correct
6 Correct 5 ms 768 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 167 ms 8184 KB Output is correct
3 Correct 197 ms 4316 KB Output is correct
4 Correct 515 ms 11256 KB Output is correct
5 Correct 324 ms 11768 KB Output is correct
6 Correct 353 ms 11768 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 384 KB Output is correct
4 Correct 6 ms 768 KB Output is correct
5 Correct 6 ms 768 KB Output is correct
6 Correct 6 ms 768 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 174 ms 8184 KB Output is correct
9 Correct 197 ms 4344 KB Output is correct
10 Correct 554 ms 11256 KB Output is correct
11 Correct 323 ms 11768 KB Output is correct
12 Correct 307 ms 12024 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 173 ms 8176 KB Output is correct
15 Correct 30 ms 1528 KB Output is correct
16 Correct 519 ms 11512 KB Output is correct
17 Correct 314 ms 11640 KB Output is correct
18 Correct 305 ms 11656 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 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 6 ms 768 KB Output is correct
5 Correct 7 ms 768 KB Output is correct
6 Correct 5 ms 768 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 165 ms 8184 KB Output is correct
9 Correct 186 ms 4472 KB Output is correct
10 Correct 526 ms 11256 KB Output is correct
11 Correct 324 ms 11820 KB Output is correct
12 Correct 305 ms 11768 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 171 ms 8312 KB Output is correct
15 Correct 31 ms 1528 KB Output is correct
16 Correct 524 ms 11460 KB Output is correct
17 Correct 373 ms 11512 KB Output is correct
18 Correct 316 ms 11640 KB Output is correct
19 Correct 810 ms 66932 KB Output is correct
20 Correct 805 ms 64632 KB Output is correct
21 Correct 809 ms 66936 KB Output is correct
22 Correct 795 ms 64504 KB Output is correct
23 Correct 823 ms 64620 KB Output is correct
24 Correct 800 ms 64544 KB Output is correct
25 Correct 798 ms 64556 KB Output is correct
26 Correct 809 ms 66936 KB Output is correct
27 Correct 821 ms 66916 KB Output is correct
28 Correct 791 ms 64504 KB Output is correct
29 Correct 794 ms 64396 KB Output is correct
30 Correct 812 ms 64516 KB Output is correct