oj.uz

Submission #1062891

# Submission time Handle Problem Language Result Execution time Memory
1062891 2024-08-17T11:37:54 Z anango Wall (IOI14_wall) C++17
0 / 100
 3000 ms 78928 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 push(int v, int tl, int tr) {
    if (tl<tr) {
        mergemin(2*v,mins[v]);
        mergemax(2*v,maxes[v]);
        mergemin(2*v+1,mins[v]);
        mergemax(2*v+1,maxes[v]);
        push(2*v,tl,(tl+tr)/2);
        push(2*v+1,(tl+tr)/2+1,tr);
    }
}

void maximize(int v, int l, int r, int tl, int tr, int value) {
    push(v,tl,tr);
    if (l>tr || r<tl) return;
    if (l<=tl && tr<=r) {
        mergemax(v,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) {
    push(v,tl,tr);
    if (l>tr || r<tl) return;
    if (l<=tl && tr<=r) {
        mergemin(v,value);
        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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 65876 KB Output is correct
2 Correct 71 ms 66208 KB Output is correct
3 Execution timed out 3052 ms 66128 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 66076 KB Output is correct
2 Correct 282 ms 78928 KB Output is correct
3 Execution timed out 3017 ms 72544 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 65880 KB Output is correct
2 Correct 67 ms 66140 KB Output is correct
3 Execution timed out 3075 ms 66140 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 65876 KB Output is correct
2 Correct 67 ms 66140 KB Output is correct
3 Execution timed out 3033 ms 65880 KB Time limit exceeded
4 Halted 0 ms 0 KB -