Submission #378100

#	Time	Username	Problem	Language	Result	Execution time	Memory
378100		ntabc05101	Wall (IOI14_wall)	C++14	100 / 100	976 ms	92396 KiB

wall

#ifndef LOCAL
#define NDEBUG 1
#endif // LOCAL
#include<bits/stdc++.h>

const int max_n=2000000;

int nodes[max_n<<2][2];
int L[max_n<<2], H[max_n<<2];

template<class U, class V> void maximize(U& a, V b) { if (a<b) a=b; }
template<class U, class V> void minimize(U& a, V b) { if (a>b) a=b; }

const int inf=1e9+9;

void buildRange(int node, int low, int high) {
        L[node]=low, H[node]=high;
        if (low==high) {
                nodes[node][0]=0, nodes[node][1]=inf;
                return ;
        }

        int mid=low+high>>1;
        buildRange(node<<1, low, mid);
        buildRange(node<<1|1, mid+1, high);
}

void lazyPush(int node) {
        for (int j=2*node; j<2*node+2; ++j) {
                maximize(nodes[j][0], nodes[node][0]);
                maximize(nodes[j][1], nodes[j][0]);
                minimize(nodes[j][1], nodes[node][1]);
                minimize(nodes[j][0], nodes[j][1]);
        }
        nodes[node][0]=0;
        nodes[node][1]=inf;
}

void update(int node, int leftq, int rightq, int op, int height) {
        if (leftq<=L[node] and rightq>=H[node]) {
                if (op==1) {
                        maximize(nodes[node][0], height);
                        maximize(nodes[node][1], height);
                }
                else {
                        minimize(nodes[node][0], height);
                        minimize(nodes[node][1], height);
                }

                return ;
        }

        lazyPush(node);
        if (H[node<<1]>=leftq) update(node<<1, leftq, rightq, op, height);
        if (L[node<<1|1]<=rightq) update(node<<1|1, leftq, rightq, op, height);
}

void modify(int node, int finalHeight[]) {
        if (L[node]==H[node]) {
                finalHeight[H[node]-1]=nodes[node][0];
                return ;
        }

        lazyPush(node);
        modify(node<<1, finalHeight);
        modify(node<<1|1, finalHeight);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
        buildRange(1, 1, n);

        for (int i=0; i<k; ++i) {
                update(1, 1+left[i], 1+right[i], op[i], height[i]);
        }

        modify(1, finalHeight);
}
/*
int main() {
        std::ios_base::sync_with_stdio(0); std::cin.tie(0);

        int n, k; std::cin>>n>>k;
        int op[k], left[k], right[k], height[k];
        for (int i=0; i<k; ++i) {
                std::cin>>op[i]>>left[i]>>right[i]>>height[i];
        }

        int finalHeight[n];
        buildWall(n, k, op, left, right, height, finalHeight);

        for (int i=0; i<n; ++i) {
                std::cout<<finalHeight[i]<<" ";
        }
        
        std::cout<<std::endl;

        return 0;
}
*/
/*
10 6
1 1 8 4
2 4 9 1
2 3 6 5
1 0 5 3
1 2 2 5
2 6 7 0
*/

Compilation message (stderr)

wall.cpp: In function 'void buildRange(int, int, int)':
wall.cpp:23:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 |         int mid=low+high>>1;
      |                 ~~~^~~~~

• Subtask 1: 8 / 8
• Subtask 2: 24 / 24
• Subtask 3: 29 / 29
• Subtask 4: 39 / 39