oj.uz

Submission #237888

# Submission time Handle Problem Language Result Execution time Memory
237888 2020-06-09T08:06:28 Z wiwiho Wall (IOI14_wall) C++14
100 / 100
 901 ms 99424 KB 
#include "wall.h"

//#define NDEBUG

#include <bits/stdc++.h>
#include <bits/extc++.h>

#define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define iter(a) a.begin(), a.end()
#define riter(a) a.rbegin(), a.rend()
#define lsort(a) sort(iter(a))
#define gsort(a) sort(riter(a))
#define pb(a) push_back(a)
#define eb(a) emplace_back(a)
#define pf(a) push_front(a)
#define pob pop_back()
#define pof pop_front()
#define mp(a, b) make_pair(a, b)
#define F first
#define S second
#define mt make_tuple
#define gt(t, i) get<i>(t)
#define iceil(a, b) ((a + b - 1) / b)
#define tomax(a, b) (a = max(a, b))
#define printv(a, b) {bool pvaspace=false; \
for(auto pva : a){ \
    if(pvaspace) b << " "; pvaspace=true;\
    b << pva;\
}\
b << "\n";}

//#define TEST

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdd = pair<ld, ld>;
using tiii = tuple<int, int, int>;

const ll MOD = 1000000007;
const ll MAX = 2147483647;

template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> p){
    return o << '(' << p.F << ',' << p.S << ')';
}

struct Node{
    int l = -1, r = -1, mx = -MAX, mn = MAX;
};

vector<Node> st;
int ts = 0;

int build(int l, int r){
    int id = ts++;
//    cerr << l << " " << r << " " << id << "\n";
    if(l == r) return id;
    int m = (l + r) / 2;
    st[id].l = build(l, m);
    st[id].r = build(m + 1, r);
    return id;
}

void add(int id, int v){
    st[id].mx = max(st[id].mx, v);
    st[id].mn = max(st[id].mn, v);
}

void remove(int id, int v){
    st[id].mx = min(st[id].mx, v);
    st[id].mn = min(st[id].mn, v);
}

void push(int id){
    add(st[id].l, st[id].mx);
    add(st[id].r, st[id].mx);
    st[id].mx = -MAX;
    remove(st[id].l, st[id].mn);
    remove(st[id].r, st[id].mn);
    st[id].mn = MAX;
}

void modifyadd(int l, int r, int v, int L, int R, int id){
//    cerr << l << " " << r << " " << L << " " << R << " " << id << "\n";
    if(l == L && r == R){
        add(id, v);
        return;
    }
    push(id);
    int M = (L + R) / 2;
    if(r <= M) modifyadd(l, r, v, L, M, st[id].l);
    else if(l > M) modifyadd(l, r, v, M + 1, R, st[id].r);
    else{
        modifyadd(l, M, v, L, M, st[id].l);
        modifyadd(M + 1, r, v, M + 1, R, st[id].r);
    }
}

void modifyremove(int l, int r, int v, int L, int R, int id){
    if(l == L && r == R){
        remove(id, v);
        return;
    }
    push(id);
    int M = (L + R) / 2;
    if(r <= M) modifyremove(l, r, v, L, M, st[id].l);
    else if(l > M) modifyremove(l, r, v, M + 1, R, st[id].r);
    else{
        modifyremove(l, M, v, L, M, st[id].l);
        modifyremove(M + 1, r, v, M + 1, R, st[id].r);
    }
}

void ans(int l, int r, int id, int finalHeight[]){
    if(l == r){
        finalHeight[l] = max(st[id].mx, min(st[id].mn, 0));
        return;
    }
    push(id);
    int m = (l + r) / 2;
    ans(l, m, st[id].l, finalHeight);
    ans(m + 1, r, st[id].r, finalHeight);
}

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

    st.resize(2 * n);
    build(0, n - 1);

    for(int i = 0; i < k; i++){
        if(op[i] == 1) modifyadd(left[i], right[i], height[i], 0, n - 1, 0);
        else modifyremove(left[i], right[i], height[i], 0, n - 1, 0);
    }

    ans(0, n - 1, 0, finalHeight);
}

Subtask #1
8.0 / 8.0

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

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 175 ms 8824 KB Output is correct
3 Correct 202 ms 4856 KB Output is correct
4 Correct 547 ms 21496 KB Output is correct
5 Correct 356 ms 22520 KB Output is correct
6 Correct 349 ms 21112 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 7 ms 512 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 10 ms 896 KB Output is correct
5 Correct 10 ms 896 KB Output is correct
6 Correct 10 ms 896 KB Output is correct
7 Correct 4 ms 256 KB Output is correct
8 Correct 170 ms 13944 KB Output is correct
9 Correct 200 ms 8056 KB Output is correct
10 Correct 598 ms 21464 KB Output is correct
11 Correct 357 ms 22664 KB Output is correct
12 Correct 348 ms 21240 KB Output is correct
13 Correct 6 ms 256 KB Output is correct
14 Correct 181 ms 13944 KB Output is correct
15 Correct 37 ms 2040 KB Output is correct
16 Correct 635 ms 21752 KB Output is correct
17 Correct 353 ms 21240 KB Output is correct
18 Correct 349 ms 21112 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 372 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 10 ms 896 KB Output is correct
5 Correct 10 ms 896 KB Output is correct
6 Correct 10 ms 896 KB Output is correct
7 Correct 4 ms 256 KB Output is correct
8 Correct 173 ms 13944 KB Output is correct
9 Correct 202 ms 8164 KB Output is correct
10 Correct 554 ms 21624 KB Output is correct
11 Correct 360 ms 22716 KB Output is correct
12 Correct 344 ms 20984 KB Output is correct
13 Correct 5 ms 256 KB Output is correct
14 Correct 175 ms 13944 KB Output is correct
15 Correct 36 ms 2040 KB Output is correct
16 Correct 602 ms 21856 KB Output is correct
17 Correct 356 ms 21112 KB Output is correct
18 Correct 354 ms 21240 KB Output is correct
19 Correct 889 ms 99424 KB Output is correct
20 Correct 876 ms 96980 KB Output is correct
21 Correct 900 ms 99392 KB Output is correct
22 Correct 890 ms 96864 KB Output is correct
23 Correct 887 ms 96900 KB Output is correct
24 Correct 878 ms 96920 KB Output is correct
25 Correct 878 ms 96804 KB Output is correct
26 Correct 884 ms 99320 KB Output is correct
27 Correct 891 ms 99368 KB Output is correct
28 Correct 895 ms 96900 KB Output is correct
29 Correct 891 ms 97012 KB Output is correct
30 Correct 901 ms 96888 KB Output is correct