oj.uz

Submission #1067433

# Submission time Handle Problem Language Result Execution time Memory
1067433 2024-08-20T16:58:07 Z DeathIsAwe Wall (IOI14_wall) C++14
100 / 100
 695 ms 73732 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
pair<int,int> lazy[4194304];
bool lazyorder[4194304];


void composeadd(int action, int cur) {
    if (lazyorder[cur]) {
        if (action > lazy[cur].second) {
            lazyorder[cur] = false;
            lazy[cur].first = action;
        } else {
            lazy[cur].first = max(lazy[cur].first, action);
        }
    } else {
        lazy[cur].first = max(lazy[cur].first, action);
    }
}


void composeremove(int action, int cur) {
    if (lazyorder[cur]) {
        lazy[cur].second = min(lazy[cur].second, action);
    } else {
        if (action < lazy[cur].first) {
            lazyorder[cur] = true;
            lazy[cur].second = action;
        } else {
            lazy[cur].second = min(lazy[cur].second, action);
        }
    }
}


void compose(pair<int,int> action, bool actionorder, int cur) {
    if (actionorder) {
        composeadd(action.first, cur); composeremove(action.second, cur);
    } else {
        composeremove(action.second, cur); composeadd(action.first, cur);
    }
}


void update(int cur, int mini, int maxi, int a, int b, bool order, pair<int,int> action) {
    int dummy;
    if (mini == a && maxi == b) {
        compose(action, order, cur);
    } else if (mini <= a && maxi >= b) {
        compose(lazy[cur], lazyorder[cur], cur * 2);
        compose(lazy[cur], lazyorder[cur], cur * 2 + 1);
        lazy[cur].first = 0; lazy[cur].second = 100000;
        dummy = (mini + maxi) / 2;
        if (a <= (mini + maxi) / 2) {
            update(cur * 2, mini, dummy, a, min(b, dummy), order, action);
        }
        dummy++;
        if (b >= dummy) {
            update(cur * 2 + 1, dummy, maxi, max(a, dummy), b, order, action);
        }
    }
}


void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    for (int i=0;i<4194304;i++) {
        lazy[i].first = 0; lazy[i].second = 100000;
        lazyorder[i] = true;
    }

    for (int i=0;i<k;i++) {
        if (op[i] == 1) {
            update(1, 0, 2097151, left[i], right[i], true, make_pair(height[i], 100000));
        } else {
            update(1, 0, 2097151, left[i], right[i], false, make_pair(0, height[i]));
        }
    }

    int bruh, sus, maxans, minans, pos;
    for (int i=0;i<n;i++) {
        bruh = 1048576;
        sus = i;
        maxans = 100000; minans = 0;
        pos = 1;
        while (pos < 4194304) {
            //cout << minans << ' ' << pos << ' ' << lazy[pos].first <<  ' ' << lazy[pos].second;
            //cout << ' ' << lazyorder[pos] << '\n';
            if (!lazyorder[pos]) {
                minans = max(minans, lazy[pos].first); minans = min(minans, maxans);
                maxans = min(maxans, lazy[pos].second); maxans = max(minans, maxans);
            } else {
                maxans = min(maxans, lazy[pos].second); maxans = max(minans, maxans);
                minans = max(minans, lazy[pos].first); minans = min(minans, maxans);
            }
            if (bruh > sus) {
                pos *= 2;
            } else {
                sus -= bruh;
                pos *= 2; pos++;
            }
            bruh /= 2;
        }
        finalHeight[i] = minans; //cout << minans << '\n' << '\n' << '\n';
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 37212 KB Output is correct
2 Correct 16 ms 37468 KB Output is correct
3 Correct 15 ms 37212 KB Output is correct
4 Correct 20 ms 37472 KB Output is correct
5 Correct 18 ms 37576 KB Output is correct
6 Correct 18 ms 37396 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 37212 KB Output is correct
2 Correct 223 ms 50940 KB Output is correct
3 Correct 149 ms 44368 KB Output is correct
4 Correct 380 ms 55376 KB Output is correct
5 Correct 244 ms 56468 KB Output is correct
6 Correct 235 ms 54868 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 37212 KB Output is correct
2 Correct 15 ms 37292 KB Output is correct
3 Correct 14 ms 37212 KB Output is correct
4 Correct 18 ms 37568 KB Output is correct
5 Correct 16 ms 37560 KB Output is correct
6 Correct 17 ms 37584 KB Output is correct
7 Correct 13 ms 37212 KB Output is correct
8 Correct 222 ms 50868 KB Output is correct
9 Correct 154 ms 44376 KB Output is correct
10 Correct 372 ms 55380 KB Output is correct
11 Correct 258 ms 56236 KB Output is correct
12 Correct 236 ms 54772 KB Output is correct
13 Correct 13 ms 37208 KB Output is correct
14 Correct 225 ms 50832 KB Output is correct
15 Correct 45 ms 38480 KB Output is correct
16 Correct 511 ms 55632 KB Output is correct
17 Correct 285 ms 54864 KB Output is correct
18 Correct 257 ms 54844 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 37212 KB Output is correct
2 Correct 15 ms 37464 KB Output is correct
3 Correct 16 ms 37220 KB Output is correct
4 Correct 18 ms 37464 KB Output is correct
5 Correct 17 ms 37468 KB Output is correct
6 Correct 17 ms 37504 KB Output is correct
7 Correct 13 ms 37212 KB Output is correct
8 Correct 221 ms 50888 KB Output is correct
9 Correct 154 ms 44372 KB Output is correct
10 Correct 385 ms 55304 KB Output is correct
11 Correct 253 ms 56272 KB Output is correct
12 Correct 246 ms 55016 KB Output is correct
13 Correct 12 ms 37208 KB Output is correct
14 Correct 221 ms 50860 KB Output is correct
15 Correct 41 ms 38480 KB Output is correct
16 Correct 510 ms 55576 KB Output is correct
17 Correct 266 ms 54868 KB Output is correct
18 Correct 274 ms 55120 KB Output is correct
19 Correct 624 ms 73564 KB Output is correct
20 Correct 611 ms 71028 KB Output is correct
21 Correct 628 ms 73556 KB Output is correct
22 Correct 610 ms 71248 KB Output is correct
23 Correct 619 ms 71496 KB Output is correct
24 Correct 638 ms 71252 KB Output is correct
25 Correct 650 ms 71252 KB Output is correct
26 Correct 684 ms 73656 KB Output is correct
27 Correct 614 ms 73732 KB Output is correct
28 Correct 695 ms 71024 KB Output is correct
29 Correct 622 ms 71180 KB Output is correct
30 Correct 609 ms 71172 KB Output is correct