oj.uz

Submission #151968

# Submission time Handle Problem Language Result Execution time Memory
151968 2019-09-05T17:22:08 Z erebos Wall (IOI14_wall) C++17
100 / 100
 1530 ms 98348 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
int inf = 1e9;
struct wall {
    int mn=0, mx=0;
};
wall operator+(wall a, wall b) {
    return {min({max({a.mn, b.mn}), b.mx}), min({max({a.mx, b.mn}), b.mx})};
}
vector<wall>tree;
void update(int node, int s, int e, int l, int r, wall diff) {
    if(e<l || r<s) return;
    if(s!=e) {
        tree[node*2]=tree[node*2]+tree[node];
        tree[node*2+1]=tree[node*2+1]+tree[node];
        tree[node]= {0, inf};
    }
    if(l<=s && e<=r) {
        tree[node]=tree[node]+diff;
    } else {
        update(node*2, s, (s+e)/2, l, r, diff);
        update(node*2+1, (s+e)/2+1, e, l, r, diff);
    }
}
wall query(int node, int s, int e, int num) {
    if(e<num || num<s) return{0, inf};
    if(s==e) return tree[node];
    return query(node*2, s, (s+e)/2, num)+query(node*2+1, (s+e)/2+1, e, num)+tree[node];
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    tree.resize(4*n);
    for(int i=0; i<k; ++i) {
        if(op[i]==1) { //+
            update(1, 1, n, left[i]+1, right[i]+1, {height[i], inf});
        } else { //-
            update(1, 1, n, left[i]+1, right[i]+1, {0, height[i]});
        }
    }
    for(int i=0; i<n; ++i) {
        finalHeight[i]=query(1, 1, n, i+1).mx;
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 4 ms 504 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 10 ms 888 KB Output is correct
5 Correct 9 ms 888 KB Output is correct
6 Correct 10 ms 920 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 176 ms 8412 KB Output is correct
3 Correct 229 ms 4600 KB Output is correct
4 Correct 677 ms 21464 KB Output is correct
5 Correct 375 ms 21336 KB Output is correct
6 Correct 362 ms 20960 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 10 ms 884 KB Output is correct
5 Correct 9 ms 888 KB Output is correct
6 Correct 9 ms 888 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 178 ms 13916 KB Output is correct
9 Correct 231 ms 8056 KB Output is correct
10 Correct 694 ms 21496 KB Output is correct
11 Correct 375 ms 21224 KB Output is correct
12 Correct 364 ms 21024 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 181 ms 13988 KB Output is correct
15 Correct 40 ms 2040 KB Output is correct
16 Correct 694 ms 21800 KB Output is correct
17 Correct 370 ms 21392 KB Output is correct
18 Correct 362 ms 21148 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 11 ms 888 KB Output is correct
5 Correct 9 ms 888 KB Output is correct
6 Correct 9 ms 888 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 180 ms 14020 KB Output is correct
9 Correct 227 ms 8056 KB Output is correct
10 Correct 689 ms 21608 KB Output is correct
11 Correct 380 ms 21340 KB Output is correct
12 Correct 365 ms 20984 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 182 ms 13944 KB Output is correct
15 Correct 42 ms 2040 KB Output is correct
16 Correct 703 ms 21824 KB Output is correct
17 Correct 367 ms 21240 KB Output is correct
18 Correct 364 ms 21276 KB Output is correct
19 Correct 1530 ms 97508 KB Output is correct
20 Correct 1491 ms 95924 KB Output is correct
21 Correct 1511 ms 98348 KB Output is correct
22 Correct 1495 ms 95908 KB Output is correct
23 Correct 1491 ms 95932 KB Output is correct
24 Correct 1493 ms 95776 KB Output is correct
25 Correct 1497 ms 95808 KB Output is correct
26 Correct 1501 ms 98340 KB Output is correct
27 Correct 1501 ms 98276 KB Output is correct
28 Correct 1486 ms 95756 KB Output is correct
29 Correct 1486 ms 95824 KB Output is correct
30 Correct 1492 ms 95852 KB Output is correct