oj.uz

Submission #333758

# Submission time Handle Problem Language Result Execution time Memory
333758 2020-12-07T17:10:59 Z ijxjdjd Wall (IOI14_wall) C++11
100 / 100
 860 ms 123008 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef string str;
typedef double db;
typedef long double ld;

typedef pair<int, int> pi;
typedef  pair<long, long> pl;

typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pi> vpi;


#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define FR(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define RF(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)


const int MAXK = 500000;
const int MAXH = 100000;
const int MAXN = (int)(2e6);
int maxTree[4*MAXK+5];
int minTree[4*MAXK+5];
vector<int> row[MAXN+5];
void turn(int n, int tl, int tr, int v, bool add, int chg) {
    if (tl != tr) {
        int tm = (tl + tr)/2;
        if (v <= tm) {
            turn(2*n, tl, tm, v, add, chg);
        }
        else {
            turn(2*n+1, tm+1, tr, v, add, chg);
        }
        maxTree[n] = max(maxTree[2*n], maxTree[2*n+1]);
        minTree[n] = min(minTree[2*n], minTree[2*n+1]);
    }
    else {
        int i = n;
        if ((maxTree[i] != -1) || (minTree[i] != MAXH+5)) {
            maxTree[i] = -1;
            minTree[i] = MAXH+5;
        }
        else {
            if (add) {
                maxTree[i] = chg;
            }
            else {
                minTree[i] = chg;
            }
        }

    }
}
int get(int n, int tl, int tr, int ma, int mi) {
    if (tl == tr) {
        if (maxTree[n] != -1) {
            return mi;
        }
        else {
            return ma;
        }
    }
    else {
        int tm = (tl + tr)/2;
        if (max(ma, maxTree[2*n+1]) < min(mi, minTree[2*n+1])) {
            ma = max(ma, maxTree[2*n+1]);
            mi = min(mi, minTree[2*n+1]);
            return get(2*n, tl, tm, ma, mi);
        }
        else {
            return get(2*n+1, tm+1, tr, ma, mi);
        }
    }
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    for (int i = 0; i < 4*MAXK+5; i++) {
        maxTree[i] = -1;
        minTree[i] = MAXH+5;
    }
    FR(i, k) {
        row[left[i]].push_back(i);
        row[right[i]+1].push_back(i);
    }
    FR(i, n) {
        for (auto& p : row[i]) {
            turn(1, 0, k-1, p, (op[p] == 1), height[p]);
        }
        if (maxTree[1] < minTree[1]) {
            if (maxTree[1] == -1) {
                finalHeight[i] = 0;
            }
            else {
                finalHeight[i] = maxTree[1];
            }
        }
        else {
            finalHeight[i] = get(1, 0, k-1, -1, MAXH+5);
        }
    }
}
//int op[101];
//int l[101];
//int r[101];
//int h[101];
//int fH[101];
//int main() {
//    int n, k;
//    cin >> n >> k;
//    FR(i, k) {
//        cin >> op[i] >> l[i] >> r[i] >> h[i];
//    }
//    buildWall(n, k, op, l, r, h, fH);
//    FR(i, n) {
//        cout << fH[i] << endl;
//    }
//}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 63084 KB Output is correct
2 Correct 41 ms 63084 KB Output is correct
3 Correct 40 ms 62956 KB Output is correct
4 Correct 43 ms 63340 KB Output is correct
5 Correct 44 ms 63340 KB Output is correct
6 Correct 44 ms 63340 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 62932 KB Output is correct
2 Correct 293 ms 74960 KB Output is correct
3 Correct 296 ms 69268 KB Output is correct
4 Correct 827 ms 79492 KB Output is correct
5 Correct 425 ms 79084 KB Output is correct
6 Correct 423 ms 78956 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 62956 KB Output is correct
2 Correct 40 ms 63084 KB Output is correct
3 Correct 39 ms 62956 KB Output is correct
4 Correct 46 ms 63468 KB Output is correct
5 Correct 47 ms 63340 KB Output is correct
6 Correct 45 ms 63340 KB Output is correct
7 Correct 40 ms 63040 KB Output is correct
8 Correct 290 ms 74960 KB Output is correct
9 Correct 300 ms 69228 KB Output is correct
10 Correct 814 ms 79348 KB Output is correct
11 Correct 424 ms 79212 KB Output is correct
12 Correct 417 ms 78860 KB Output is correct
13 Correct 39 ms 62956 KB Output is correct
14 Correct 285 ms 74960 KB Output is correct
15 Correct 81 ms 64236 KB Output is correct
16 Correct 860 ms 79724 KB Output is correct
17 Correct 435 ms 78572 KB Output is correct
18 Correct 433 ms 78188 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 62956 KB Output is correct
2 Correct 40 ms 63084 KB Output is correct
3 Correct 42 ms 62956 KB Output is correct
4 Correct 45 ms 63340 KB Output is correct
5 Correct 44 ms 63340 KB Output is correct
6 Correct 44 ms 63340 KB Output is correct
7 Correct 39 ms 62956 KB Output is correct
8 Correct 284 ms 75088 KB Output is correct
9 Correct 278 ms 69228 KB Output is correct
10 Correct 829 ms 79556 KB Output is correct
11 Correct 422 ms 79084 KB Output is correct
12 Correct 416 ms 78884 KB Output is correct
13 Correct 39 ms 62956 KB Output is correct
14 Correct 288 ms 74960 KB Output is correct
15 Correct 70 ms 64364 KB Output is correct
16 Correct 852 ms 79852 KB Output is correct
17 Correct 428 ms 78572 KB Output is correct
18 Correct 462 ms 78148 KB Output is correct
19 Correct 853 ms 112600 KB Output is correct
20 Correct 835 ms 120396 KB Output is correct
21 Correct 841 ms 122916 KB Output is correct
22 Correct 830 ms 120428 KB Output is correct
23 Correct 830 ms 120428 KB Output is correct
24 Correct 860 ms 120556 KB Output is correct
25 Correct 831 ms 120428 KB Output is correct
26 Correct 835 ms 123008 KB Output is correct
27 Correct 843 ms 122836 KB Output is correct
28 Correct 833 ms 120292 KB Output is correct
29 Correct 830 ms 120344 KB Output is correct
30 Correct 831 ms 120300 KB Output is correct