oj.uz

Submission #116645

# Submission time Handle Problem Language Result Execution time Memory
116645 2019-06-13T10:01:02 Z roseanne_pcy Wall (IOI14_wall) C++14
100 / 100
 768 ms 99420 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 52 ms 62968 KB Output is correct
2 Correct 61 ms 63224 KB Output is correct
3 Correct 56 ms 62968 KB Output is correct
4 Correct 58 ms 63352 KB Output is correct
5 Correct 57 ms 63228 KB Output is correct
6 Correct 57 ms 63224 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 63004 KB Output is correct
2 Correct 217 ms 76792 KB Output is correct
3 Correct 221 ms 70240 KB Output is correct
4 Correct 579 ms 81116 KB Output is correct
5 Correct 360 ms 82216 KB Output is correct
6 Correct 342 ms 80696 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 62948 KB Output is correct
2 Correct 53 ms 63036 KB Output is correct
3 Correct 55 ms 62968 KB Output is correct
4 Correct 59 ms 63352 KB Output is correct
5 Correct 57 ms 63224 KB Output is correct
6 Correct 59 ms 63308 KB Output is correct
7 Correct 53 ms 62968 KB Output is correct
8 Correct 200 ms 76664 KB Output is correct
9 Correct 228 ms 70136 KB Output is correct
10 Correct 638 ms 81104 KB Output is correct
11 Correct 357 ms 82068 KB Output is correct
12 Correct 340 ms 80628 KB Output is correct
13 Correct 52 ms 62968 KB Output is correct
14 Correct 339 ms 76536 KB Output is correct
15 Correct 81 ms 64120 KB Output is correct
16 Correct 578 ms 81240 KB Output is correct
17 Correct 389 ms 80860 KB Output is correct
18 Correct 350 ms 80684 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 63096 KB Output is correct
2 Correct 54 ms 63096 KB Output is correct
3 Correct 51 ms 62968 KB Output is correct
4 Correct 68 ms 63224 KB Output is correct
5 Correct 55 ms 63224 KB Output is correct
6 Correct 57 ms 63264 KB Output is correct
7 Correct 53 ms 62968 KB Output is correct
8 Correct 196 ms 76792 KB Output is correct
9 Correct 220 ms 70200 KB Output is correct
10 Correct 593 ms 81016 KB Output is correct
11 Correct 347 ms 82044 KB Output is correct
12 Correct 340 ms 80612 KB Output is correct
13 Correct 54 ms 63096 KB Output is correct
14 Correct 195 ms 76636 KB Output is correct
15 Correct 78 ms 64120 KB Output is correct
16 Correct 565 ms 81260 KB Output is correct
17 Correct 334 ms 80760 KB Output is correct
18 Correct 333 ms 80672 KB Output is correct
19 Correct 665 ms 99300 KB Output is correct
20 Correct 709 ms 96732 KB Output is correct
21 Correct 768 ms 99188 KB Output is correct
22 Correct 678 ms 96684 KB Output is correct
23 Correct 703 ms 96732 KB Output is correct
24 Correct 657 ms 96732 KB Output is correct
25 Correct 662 ms 96764 KB Output is correct
26 Correct 671 ms 99224 KB Output is correct
27 Correct 672 ms 99420 KB Output is correct
28 Correct 714 ms 96768 KB Output is correct
29 Correct 684 ms 96812 KB Output is correct
30 Correct 655 ms 96720 KB Output is correct