oj.uz

Submission #143933

# Submission time Handle Problem Language Result Execution time Memory
143933 2019-08-15T13:15:45 Z WhipppedCream Wall (IOI14_wall) C++17
100 / 100
 842 ms 99448 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 56 ms 63084 KB Output is correct
2 Correct 57 ms 63096 KB Output is correct
3 Correct 57 ms 63056 KB Output is correct
4 Correct 61 ms 63224 KB Output is correct
5 Correct 60 ms 63232 KB Output is correct
6 Correct 61 ms 63188 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 63048 KB Output is correct
2 Correct 227 ms 76676 KB Output is correct
3 Correct 260 ms 70112 KB Output is correct
4 Correct 640 ms 81096 KB Output is correct
5 Correct 402 ms 82020 KB Output is correct
6 Correct 398 ms 80464 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 62968 KB Output is correct
2 Correct 58 ms 63124 KB Output is correct
3 Correct 57 ms 62968 KB Output is correct
4 Correct 62 ms 63224 KB Output is correct
5 Correct 61 ms 63224 KB Output is correct
6 Correct 61 ms 63184 KB Output is correct
7 Correct 55 ms 62968 KB Output is correct
8 Correct 228 ms 76552 KB Output is correct
9 Correct 262 ms 70088 KB Output is correct
10 Correct 648 ms 81016 KB Output is correct
11 Correct 402 ms 82064 KB Output is correct
12 Correct 396 ms 80444 KB Output is correct
13 Correct 56 ms 62868 KB Output is correct
14 Correct 231 ms 76580 KB Output is correct
15 Correct 89 ms 64248 KB Output is correct
16 Correct 643 ms 81220 KB Output is correct
17 Correct 394 ms 80752 KB Output is correct
18 Correct 396 ms 80628 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 63040 KB Output is correct
2 Correct 58 ms 63096 KB Output is correct
3 Correct 58 ms 62968 KB Output is correct
4 Correct 61 ms 63224 KB Output is correct
5 Correct 61 ms 63128 KB Output is correct
6 Correct 61 ms 63276 KB Output is correct
7 Correct 56 ms 62968 KB Output is correct
8 Correct 228 ms 76644 KB Output is correct
9 Correct 263 ms 70092 KB Output is correct
10 Correct 648 ms 80964 KB Output is correct
11 Correct 428 ms 82028 KB Output is correct
12 Correct 391 ms 80584 KB Output is correct
13 Correct 57 ms 62928 KB Output is correct
14 Correct 231 ms 76580 KB Output is correct
15 Correct 89 ms 64164 KB Output is correct
16 Correct 655 ms 81220 KB Output is correct
17 Correct 394 ms 80604 KB Output is correct
18 Correct 395 ms 80676 KB Output is correct
19 Correct 806 ms 99448 KB Output is correct
20 Correct 801 ms 96832 KB Output is correct
21 Correct 825 ms 99412 KB Output is correct
22 Correct 832 ms 96740 KB Output is correct
23 Correct 814 ms 96860 KB Output is correct
24 Correct 801 ms 96764 KB Output is correct
25 Correct 813 ms 96708 KB Output is correct
26 Correct 810 ms 99308 KB Output is correct
27 Correct 809 ms 99320 KB Output is correct
28 Correct 842 ms 96820 KB Output is correct
29 Correct 795 ms 96756 KB Output is correct
30 Correct 794 ms 96756 KB Output is correct