oj.uz

Submission #1062929

# Submission time Handle Problem Language Result Execution time Memory
1062929 2024-08-17T12:01:10 Z anango Wall (IOI14_wall) C++17
100 / 100
 1667 ms 91988 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;

int INF = 1<<30;

const int sz = 4194304;

int mins[sz]; //apply mins before maxes
int maxes[sz];
int lazymins[sz];
int lazymaxes[sz];

void mergemin(int v, int c) {
    int a = mins[v];
    int b = maxes[v];
    a = min(a,c);
    b = min(b,c);
    mins[v] = a;
    maxes[v] = b;
}

void mergemax(int v, int c) {
    int a = mins[v];
    int b = maxes[v];
    b = max(b,c);
    mins[v] = a;
    maxes[v] = b;
}

void lazymergemin(int v, int c) {
    int a = lazymins[v];
    int b = lazymaxes[v];
    a = min(a,c);
    b = min(b,c);
    lazymins[v] = a;
    lazymaxes[v] = b;
}

void lazymergemax(int v, int c) {
    int a = lazymins[v];
    int b = lazymaxes[v];
    b = max(b,c);
    lazymins[v] = a;
    lazymaxes[v] = b;
}

void push(int v, int tl, int tr) {
    
    if (tl<tr) {
        lazymergemin(2*v,lazymins[v]);
        lazymergemin(2*v+1,lazymins[v]);
        lazymergemax(2*v,lazymaxes[v]);
        lazymergemax(2*v+1,lazymaxes[v]);
        //push(2*v,tl,(tl+tr)/2);
        //push(2*v+1,(tl+tr)/2+1,tr);
    }
    mergemin(v,lazymins[v]);
    mergemax(v,lazymaxes[v]);
    lazymins[v] = INF;
    lazymaxes[v] = -INF;

}

void maximize(int v, int l, int r, int tl, int tr, int value) {
    //if (tr<=15) cout << "maximizing " << l <<" " << r <<" " << tl <<" " << tr <<" " << value << endl;
    push(v,tl,tr);
    if (l>tr || r<tl) return;
    if (l<=tl && tr<=r) {
        mergemax(v,value);
        if (tl<tr) {
            lazymergemax(2*v,value);
            lazymergemax(2*v+1,value);
        }
        return;
    }
    int m = (tl+tr)/2;
    maximize(2*v,l,r,tl,m,value);
    maximize(2*v+1,l,r,m+1,tr,value);
}

void minimize(int v, int l, int r, int tl, int tr, int value) {
    //if (tr<=15) cout << "minimizing " << l <<" " << r <<" " << tl <<" " << tr <<" " << value << endl;
    push(v,tl,tr);
    if (l>tr || r<tl) return;
    if (l<=tl && tr<=r) {
        mergemin(v,value);
        if (tl<tr) {
            lazymergemin(2*v,value);
            lazymergemin(2*v+1,value);  
        }
        //cout << "merged minimum " << v <<" " << value <<" " << mins[v] <<" " << maxes[v] << endl;
        return;
    }
    int m = (tl+tr)/2;
    minimize(2*v,l,r,tl,m,value);
    minimize(2*v+1,l,r,m+1,tr,value);
}

int query(int v, int l, int r, int tl, int tr, int value) {
    push(v,tl,tr);
    if (l>tr || r<tl) {
        return INF;
    }
    if (l<=tl && tr<=r) {
        int ans = value;
        ans = min(ans,mins[v]);
        ans = max(ans,maxes[v]);
        //cout << "ending query " << l <<" " << r <<" " << value <<" " << mins[v] <<" " << maxes[v] <<" " << ans << endl;
        return ans;
    }
    int m = (tl+tr)/2;
    return min(query(2*v,l,r,tl,m,value),query(2*v+1,l,r,m+1,tr,value));
    
}



void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    for (int i=0; i<sz; i++) {
        mins[i] = INF;
        maxes[i] = -INF;
        lazymins[i] = INF;
        lazymaxes[i] = -INF;
    }
    for (int i=0; i<k; i++) {
        if (op[i]==1) {
            maximize(1,left[i],right[i],0,2097151,height[i]);
            //for (int j=left[i]; j<=right[i]; j++) {
            //    mergemax(j+2097152,height[i]);
            //}
        }
        else {
            assert(op[i]==2);
            minimize(1,left[i],right[i],0,2097151,height[i]);
            //for (int j=left[i]; j<=right[i]; j++) {
            //    mergemin(j+2097152,height[i]);
            //}
        }
    }
    for (int i=0; i<n; i++) {
        int ans = query(1,i,i,0,2097151,0);
        finalHeight[i] = ans;
    }

    return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 65876 KB Output is correct
2 Correct 37 ms 66156 KB Output is correct
3 Correct 30 ms 65872 KB Output is correct
4 Correct 37 ms 66132 KB Output is correct
5 Correct 37 ms 66140 KB Output is correct
6 Correct 47 ms 66132 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 65884 KB Output is correct
2 Correct 770 ms 73812 KB Output is correct
3 Correct 241 ms 69456 KB Output is correct
4 Correct 612 ms 74432 KB Output is correct
5 Correct 378 ms 74952 KB Output is correct
6 Correct 382 ms 74832 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 65880 KB Output is correct
2 Correct 35 ms 66172 KB Output is correct
3 Correct 30 ms 65880 KB Output is correct
4 Correct 38 ms 66128 KB Output is correct
5 Correct 44 ms 66128 KB Output is correct
6 Correct 37 ms 66236 KB Output is correct
7 Correct 27 ms 65876 KB Output is correct
8 Correct 765 ms 73916 KB Output is correct
9 Correct 232 ms 69376 KB Output is correct
10 Correct 687 ms 74324 KB Output is correct
11 Correct 374 ms 74816 KB Output is correct
12 Correct 373 ms 74836 KB Output is correct
13 Correct 30 ms 65880 KB Output is correct
14 Correct 750 ms 73808 KB Output is correct
15 Correct 86 ms 66644 KB Output is correct
16 Correct 594 ms 74580 KB Output is correct
17 Correct 442 ms 74596 KB Output is correct
18 Correct 377 ms 74576 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 65880 KB Output is correct
2 Correct 36 ms 65968 KB Output is correct
3 Correct 31 ms 65872 KB Output is correct
4 Correct 51 ms 66184 KB Output is correct
5 Correct 44 ms 66064 KB Output is correct
6 Correct 38 ms 66200 KB Output is correct
7 Correct 28 ms 65884 KB Output is correct
8 Correct 803 ms 73812 KB Output is correct
9 Correct 242 ms 69356 KB Output is correct
10 Correct 660 ms 74348 KB Output is correct
11 Correct 397 ms 74836 KB Output is correct
12 Correct 382 ms 74836 KB Output is correct
13 Correct 32 ms 65884 KB Output is correct
14 Correct 783 ms 73924 KB Output is correct
15 Correct 68 ms 66572 KB Output is correct
16 Correct 598 ms 74748 KB Output is correct
17 Correct 398 ms 74576 KB Output is correct
18 Correct 389 ms 74576 KB Output is correct
19 Correct 1638 ms 91972 KB Output is correct
20 Correct 1498 ms 89428 KB Output is correct
21 Correct 1593 ms 91988 KB Output is correct
22 Correct 1549 ms 89540 KB Output is correct
23 Correct 1667 ms 89408 KB Output is correct
24 Correct 1653 ms 89432 KB Output is correct
25 Correct 1614 ms 89424 KB Output is correct
26 Correct 1581 ms 91988 KB Output is correct
27 Correct 1583 ms 91852 KB Output is correct
28 Correct 1630 ms 89296 KB Output is correct
29 Correct 1586 ms 89552 KB Output is correct
30 Correct 1601 ms 89548 KB Output is correct