oj.uz

Submission #218893

# Submission time Handle Problem Language Result Execution time Memory
218893 2020-04-03T04:40:04 Z dung11112003 Wall (IOI14_wall) C++11
100 / 100
 834 ms 99664 KB 
#include <bits/stdc++.h>
#include "wall.h"

#define taskname ""
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define for0(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

using namespace std;

typedef long long ll;
typedef long double ld;
typedef complex <ld> cd;
typedef vector <cd> vcd;
typedef vector <int> vi;

template<class T> using v2d = vector <vector <T> >;
template<class T> bool uin(T &a, T b)
{
    return a > b ? (a = b, true) : false;
}
template<class T> bool uax(T &a, T b)
{
    return a < b ? (a = b, true) : false;
}

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

const int maxN = 2e6 + 10;
const int inf = 1e9;

struct node
{
    int mi, ma;
    node() : mi(0), ma(0) {}
    node(int mi, int ma) : mi(mi), ma(ma) {}
} f[maxN * 4];
int L, R, val;
int *ans;

void down(int x)
{
    uin(f[x * 2 + 1].mi, f[x].mi);
    uin(f[x * 2 + 1].ma, f[x * 2 + 1].mi);
    uax(f[x * 2 + 1].ma, f[x].ma);
    uax(f[x * 2 + 1].mi, f[x * 2 + 1].ma);
    uin(f[x * 2 + 2].mi, f[x].mi);
    uin(f[x * 2 + 2].ma, f[x * 2 + 2].mi);
    uax(f[x * 2 + 2].ma, f[x].ma);
    uax(f[x * 2 + 2].mi, f[x * 2 + 2].ma);
}

void minimize(int x, int lo, int hi)
{
    if (lo > R || hi < L)
    {
        return;
    }
    if (lo >= L && hi <= R)
    {
        uin(f[x].mi, val);
        uin(f[x].ma, f[x].mi);
        return;
    }
    down(x);
    int mid = (lo + hi) / 2;
    minimize(x * 2 + 1, lo, mid);
    minimize(x * 2 + 2, mid + 1, hi);
    f[x].mi = max(f[x * 2 + 1].mi, f[x * 2 + 2].mi);
    f[x].ma = min(f[x * 2 + 1].ma, f[x * 2 + 2].ma);
}

void maximize(int x, int lo, int hi)
{
    if (lo > R || hi < L)
    {
        return;
    }
    if (lo >= L && hi <= R)
    {
        uax(f[x].ma, val);
        uax(f[x].mi, f[x].ma);
        return;
    }
    down(x);
    int mid = (lo + hi) / 2;
    maximize(x * 2 + 1, lo, mid);
    maximize(x * 2 + 2, mid + 1, hi);
    f[x].mi = max(f[x * 2 + 1].mi, f[x * 2 + 2].mi);
    f[x].ma = min(f[x * 2 + 1].ma, f[x * 2 + 2].ma);
}

void build(int x, int lo, int hi)
{
    if (lo == hi)
    {
        ans[lo] = f[x].mi;
        return;
    }
    down(x);
    int mid = (lo + hi) / 2;
    build(x * 2 + 1, lo, mid);
    build(x * 2 + 2, mid + 1, hi);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    for0(i, k)
    {
        if (op[i] == 1)
        {
            //adding phase
            L = left[i], R = right[i], val = height[i];
            maximize(0, 0, n - 1);
        }
        else
        {
            //removing phase
            L = left[i], R = right[i], val = height[i];
            minimize(0, 0, n - 1);
        }
    }
    ans = finalHeight;
    build(0, 0, n - 1);
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 62968 KB Output is correct
2 Correct 42 ms 63224 KB Output is correct
3 Correct 40 ms 62968 KB Output is correct
4 Correct 48 ms 63224 KB Output is correct
5 Correct 44 ms 63352 KB Output is correct
6 Correct 45 ms 63224 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 62968 KB Output is correct
2 Correct 215 ms 76628 KB Output is correct
3 Correct 242 ms 70256 KB Output is correct
4 Correct 559 ms 81016 KB Output is correct
5 Correct 393 ms 82168 KB Output is correct
6 Correct 385 ms 80504 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 62968 KB Output is correct
2 Correct 41 ms 63096 KB Output is correct
3 Correct 41 ms 63020 KB Output is correct
4 Correct 45 ms 63224 KB Output is correct
5 Correct 45 ms 63224 KB Output is correct
6 Correct 45 ms 63224 KB Output is correct
7 Correct 40 ms 62976 KB Output is correct
8 Correct 215 ms 76796 KB Output is correct
9 Correct 232 ms 70136 KB Output is correct
10 Correct 559 ms 81016 KB Output is correct
11 Correct 400 ms 82104 KB Output is correct
12 Correct 380 ms 80632 KB Output is correct
13 Correct 42 ms 62968 KB Output is correct
14 Correct 218 ms 76664 KB Output is correct
15 Correct 74 ms 64252 KB Output is correct
16 Correct 649 ms 81352 KB Output is correct
17 Correct 398 ms 80760 KB Output is correct
18 Correct 395 ms 80888 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 62976 KB Output is correct
2 Correct 41 ms 63096 KB Output is correct
3 Correct 45 ms 63096 KB Output is correct
4 Correct 45 ms 63224 KB Output is correct
5 Correct 44 ms 63224 KB Output is correct
6 Correct 44 ms 63224 KB Output is correct
7 Correct 40 ms 62968 KB Output is correct
8 Correct 213 ms 76664 KB Output is correct
9 Correct 236 ms 70136 KB Output is correct
10 Correct 567 ms 81024 KB Output is correct
11 Correct 394 ms 82168 KB Output is correct
12 Correct 384 ms 80504 KB Output is correct
13 Correct 40 ms 62972 KB Output is correct
14 Correct 219 ms 76664 KB Output is correct
15 Correct 73 ms 64124 KB Output is correct
16 Correct 651 ms 81272 KB Output is correct
17 Correct 402 ms 80728 KB Output is correct
18 Correct 398 ms 80760 KB Output is correct
19 Correct 816 ms 99664 KB Output is correct
20 Correct 792 ms 97144 KB Output is correct
21 Correct 828 ms 99576 KB Output is correct
22 Correct 823 ms 97148 KB Output is correct
23 Correct 808 ms 97296 KB Output is correct
24 Correct 828 ms 96888 KB Output is correct
25 Correct 809 ms 96888 KB Output is correct
26 Correct 819 ms 99572 KB Output is correct
27 Correct 804 ms 99484 KB Output is correct
28 Correct 797 ms 96888 KB Output is correct
29 Correct 804 ms 97016 KB Output is correct
30 Correct 834 ms 96932 KB Output is correct