Submission #42946

#	Time	Username	Problem	Language	Result	Execution time	Memory
42946		PowerOfNinjaGo	Wall (IOI14_wall)	C++14	100 / 100	853 ms	262144 KiB

wall

//Power Of Ninja Go
#include <bits/stdc++.h>
#ifdef atom
#include "grader.cpp"
#else
#include "wall.h"
#endif
using namespace std;
typedef long long ll; typedef pair<int, int> ii;
#define X first
#define Y second
#define vi vector<int>
#define vii vector< ii >
#define pb push_back
struct node
{
    int lo, hi;
    node()
    {
        lo = 0; hi = 1e5;
    }
};
const int maxn = 2e6+5;
node st[4*maxn];
int n;
void change(int p, int op, int v)
{
    if(op == 1) st[p].lo = max(st[p].lo, v), st[p].hi = max(st[p].hi, v);
    else st[p].lo = min(st[p].lo, v), st[p].hi = min(st[p].hi, v);
}
void update(int i, int j, int op, int v, int p = 1, int L = 0, int R = n-1)
{
    if(i> R || j< L) return;
    if(i<= L && R<= j)
    {
        change(p, op, v);
        return;
    }
    change(2*p, 1, st[p].lo); change(2*p+1, 1, st[p].lo);
    change(2*p, 2, st[p].hi); change(2*p+1, 2, st[p].hi);
    st[p].lo = 0, st[p].hi = 1e5;
    int M = (L+R)/2;
    update(i, j, op, v, 2*p, L, M);
    update(i, j, op, v, 2*p+1, M+1, R);
}
int *arr;
void prop(int p = 1, int L = 0, int R = n-1)
{
    if(L == R)
    {
        arr[L] = st[p].lo;
        return;
    }
    change(2*p, 1, st[p].lo); change(2*p+1, 1, st[p].lo);
    change(2*p, 2, st[p].hi); change(2*p+1, 2, st[p].hi);
    int M = (L+R)/2;
    prop(2*p, L, M); prop(2*p+1, M+1, R);
}
void buildWall(int N, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    n = N;
    arr = finalHeight;
    for(int i = 0; i< k; i++) update(left[i], right[i], op[i], height[i]);
    prop();
}

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