oj.uz

Submission #122103

# Submission time Handle Problem Language Result Execution time Memory
122103 2019-06-27T14:41:23 Z Gustav Wall (IOI14_wall) C++14
100 / 100
 1089 ms 232240 KB 
#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<pi> vpi;
typedef vector<vi> vvi;
const int inf = 0x3f3f3f3f;
const ll linf = 123456789012345678;
const ll mod = 998244353;
#pragma GCC optimize("Ofast")
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " = " << x << endl

struct Tree{
    Tree *left, *right;
    int lo, hi;
    int lazymin = 0;
    int lazymax = 0;

    Tree(int lo, int hi) : lo(lo), hi(hi){
        if(lo+1 == hi) return;
        int mid = (lo+hi)/2;
        left = new Tree(lo, mid);
        right = new Tree(mid, hi);
    }

    void update(int from, int to, int h, int op){
        if(to <= lo || from >= hi) return;
        push();
        if(from <= lo && to >= hi){
            if(op == 1){
                lazymin = max(lazymin, h);
                lazymax = max(lazymax, h);
            }
            else{
                lazymax = min(lazymax, h);
                lazymin = min(lazymin, h);
            }
            return;
        }
        left->update(from, to, h, op);
        right->update(from, to, h, op);
    }

    void push(){
        if(lo+1 == hi) return;
        left->lazymax = min(left->lazymax, lazymax);
        left->lazymax = max(left->lazymax, lazymin);
        right->lazymax = min(right->lazymax, lazymax);
        right->lazymax = max(right->lazymax, lazymin);
        
        left->lazymin = max(left->lazymin, lazymin);
        left->lazymin = min(left->lazymin, lazymax);
        right->lazymin = max(right->lazymin, lazymin);
        right->lazymin = min(right->lazymin, lazymax);
        lazymin = 0;
        lazymax = inf;
    }

    int ans(vi* ans, int i){
        push();
        if(lo+1 == hi) {
            assert(lazymin == lazymax);
            ans->at(i) = lazymin;
            return i+1; 
        }
        i = left->ans(ans, i);
        i = right->ans(ans, i);
        return i;
    }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    Tree st(0, n);
    for(int i = 0; i < k; i++){
        st.update(left[i], right[i]+1, height[i], op[i]);
    }
    vi *ans = new vi(n);
    st.ans(ans, 0);
    for(int i = 0; i < n; i++) finalHeight[i] = ans->at(i);
}

Subtask #1
8.0 / 8.0

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

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 144 ms 8668 KB Output is correct
3 Correct 193 ms 6136 KB Output is correct
4 Correct 699 ms 19004 KB Output is correct
5 Correct 303 ms 29244 KB Output is correct
6 Correct 294 ms 27640 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 13 ms 384 KB Output is correct
4 Correct 9 ms 1536 KB Output is correct
5 Correct 7 ms 1536 KB Output is correct
6 Correct 8 ms 1536 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 154 ms 8696 KB Output is correct
9 Correct 208 ms 6008 KB Output is correct
10 Correct 696 ms 18996 KB Output is correct
11 Correct 315 ms 29288 KB Output is correct
12 Correct 298 ms 27640 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 146 ms 13944 KB Output is correct
15 Correct 33 ms 3192 KB Output is correct
16 Correct 687 ms 28408 KB Output is correct
17 Correct 322 ms 27760 KB Output is correct
18 Correct 312 ms 27780 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 11 ms 1536 KB Output is correct
5 Correct 8 ms 1536 KB Output is correct
6 Correct 8 ms 1536 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 145 ms 8660 KB Output is correct
9 Correct 196 ms 6008 KB Output is correct
10 Correct 748 ms 19000 KB Output is correct
11 Correct 300 ms 29308 KB Output is correct
12 Correct 296 ms 27600 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 148 ms 13968 KB Output is correct
15 Correct 33 ms 3196 KB Output is correct
16 Correct 710 ms 28352 KB Output is correct
17 Correct 298 ms 27768 KB Output is correct
18 Correct 318 ms 27896 KB Output is correct
19 Correct 1058 ms 232164 KB Output is correct
20 Correct 949 ms 229740 KB Output is correct
21 Correct 940 ms 232240 KB Output is correct
22 Correct 937 ms 229784 KB Output is correct
23 Correct 958 ms 229676 KB Output is correct
24 Correct 1089 ms 229676 KB Output is correct
25 Correct 977 ms 229728 KB Output is correct
26 Correct 968 ms 232232 KB Output is correct
27 Correct 975 ms 232232 KB Output is correct
28 Correct 942 ms 229784 KB Output is correct
29 Correct 945 ms 229680 KB Output is correct
30 Correct 936 ms 229728 KB Output is correct