oj.uz

Submission #42946

# Submission time Handle Problem Language Result Execution time Memory
42946 2018-03-06T16:52:55 Z PowerOfNinjaGo Wall (IOI14_wall) C++14
100 / 100
 853 ms 262144 KB 
//Power Of Ninja Go
#include <bits/stdc++.h>
#ifdef atom
#include "grader.cpp"
#else
#include "wall.h"
#endif
using namespace std;
typedef long long ll; typedef pair<int, int> ii;
#define X first
#define Y second
#define vi vector<int>
#define vii vector< ii >
#define pb push_back
struct node
{
    int lo, hi;
    node()
    {
        lo = 0; hi = 1e5;
    }
};
const int maxn = 2e6+5;
node st[4*maxn];
int n;
void change(int p, int op, int v)
{
    if(op == 1) st[p].lo = max(st[p].lo, v), st[p].hi = max(st[p].hi, v);
    else st[p].lo = min(st[p].lo, v), st[p].hi = min(st[p].hi, v);
}
void update(int i, int j, int op, int v, int p = 1, int L = 0, int R = n-1)
{
    if(i> R || j< L) return;
    if(i<= L && R<= j)
    {
        change(p, op, v);
        return;
    }
    change(2*p, 1, st[p].lo); change(2*p+1, 1, st[p].lo);
    change(2*p, 2, st[p].hi); change(2*p+1, 2, st[p].hi);
    st[p].lo = 0, st[p].hi = 1e5;
    int M = (L+R)/2;
    update(i, j, op, v, 2*p, L, M);
    update(i, j, op, v, 2*p+1, M+1, R);
}
int *arr;
void prop(int p = 1, int L = 0, int R = n-1)
{
    if(L == R)
    {
        arr[L] = st[p].lo;
        return;
    }
    change(2*p, 1, st[p].lo); change(2*p+1, 1, st[p].lo);
    change(2*p, 2, st[p].hi); change(2*p+1, 2, st[p].hi);
    int M = (L+R)/2;
    prop(2*p, L, M); prop(2*p+1, M+1, R);
}
void buildWall(int N, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    n = N;
    arr = finalHeight;
    for(int i = 0; i< k; i++) update(left[i], right[i], op[i], height[i]);
    prop();
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 62968 KB Output is correct
2 Correct 50 ms 63204 KB Output is correct
3 Correct 57 ms 63368 KB Output is correct
4 Correct 56 ms 63648 KB Output is correct
5 Correct 52 ms 63648 KB Output is correct
6 Correct 61 ms 63728 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 63744 KB Output is correct
2 Correct 213 ms 77356 KB Output is correct
3 Correct 277 ms 77356 KB Output is correct
4 Correct 627 ms 91280 KB Output is correct
5 Correct 391 ms 101972 KB Output is correct
6 Correct 416 ms 110756 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 110756 KB Output is correct
2 Correct 56 ms 110756 KB Output is correct
3 Correct 51 ms 110756 KB Output is correct
4 Correct 55 ms 110756 KB Output is correct
5 Correct 57 ms 110756 KB Output is correct
6 Correct 56 ms 110756 KB Output is correct
7 Correct 51 ms 110756 KB Output is correct
8 Correct 212 ms 115792 KB Output is correct
9 Correct 258 ms 115792 KB Output is correct
10 Correct 634 ms 129860 KB Output is correct
11 Correct 409 ms 140488 KB Output is correct
12 Correct 386 ms 149024 KB Output is correct
13 Correct 53 ms 149024 KB Output is correct
14 Correct 234 ms 153808 KB Output is correct
15 Correct 84 ms 153808 KB Output is correct
16 Correct 650 ms 164880 KB Output is correct
17 Correct 394 ms 173948 KB Output is correct
18 Correct 426 ms 183020 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 183020 KB Output is correct
2 Correct 52 ms 183020 KB Output is correct
3 Correct 51 ms 183020 KB Output is correct
4 Correct 73 ms 183020 KB Output is correct
5 Correct 59 ms 183020 KB Output is correct
6 Correct 55 ms 183020 KB Output is correct
7 Correct 48 ms 183020 KB Output is correct
8 Correct 212 ms 188176 KB Output is correct
9 Correct 253 ms 188176 KB Output is correct
10 Correct 647 ms 202388 KB Output is correct
11 Correct 396 ms 213032 KB Output is correct
12 Correct 393 ms 221632 KB Output is correct
13 Correct 48 ms 221632 KB Output is correct
14 Correct 211 ms 226336 KB Output is correct
15 Correct 87 ms 226336 KB Output is correct
16 Correct 640 ms 237332 KB Output is correct
17 Correct 393 ms 246400 KB Output is correct
18 Correct 410 ms 255468 KB Output is correct
19 Correct 818 ms 262144 KB Output is correct
20 Correct 839 ms 262144 KB Output is correct
21 Correct 813 ms 262144 KB Output is correct
22 Correct 842 ms 262144 KB Output is correct
23 Correct 791 ms 262144 KB Output is correct
24 Correct 831 ms 262144 KB Output is correct
25 Correct 786 ms 262144 KB Output is correct
26 Correct 853 ms 262144 KB Output is correct
27 Correct 818 ms 262144 KB Output is correct
28 Correct 791 ms 262144 KB Output is correct
29 Correct 782 ms 262144 KB Output is correct
30 Correct 822 ms 262144 KB Output is correct