Submission #1124887

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124887		KhoaDuy	Wall (IOI14_wall)	C++20	100 / 100	547 ms	59136 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>

typedef long long ll;
using namespace std;

#define all(x) x.begin(), x.end()
#define f(i,a,b) for(int i = (a); i <= (b); i++)
#define fd(i,a,b) for(int i = (a); i >= (b); i--)
#define mp make_pair
#define faster_io() ios_base::sync_with_stdio(false)
#define pb push_back
#define pii pair<int,int>
#define SZ(x) ((int)x.size())
#define TRACE(x) cout << #x << " = " << x << "\n";
#define vii vector<pair<int,int>>

const ll INFLL = 100000000000000000;

// --------------------------------------------------------------------------

const int RIGHT = (1<<21);
const int SIZE = (1<<22)+5;

int D[SIZE], U[SIZE];
int N, K;

void combine(int n, int d, int u)
{
    D[n] = min(D[n], d);
    D[n] = max(D[n], u);
    U[n] = max(U[n], u);
    U[n] = min(U[n], d);
}

void process(int n, char t, int h)
{
    if(t == 'd')
    {
        D[n] = min(D[n], h);
        U[n] = min(U[n], h);
    }
    if(t == 'u')
    {
        D[n] = max(D[n], h);
        U[n] = max(U[n], h);
    }
}

void update(int l, int r, char t, int h, int n, int a, int b)
{
    if(a > r || b < l) return;
    if(a >= l && b <= r)
    {
        process(n,t,h);
        return;
    }

    combine(2*n, D[n], U[n]);
    combine(2*n+1, D[n], U[n]);
    D[n] = SIZE, U[n] = 0;

    int mid = (a+b) / 2;
    update(l,r,t,h,2*n,a,mid);
    update(l,r,t,h,2*n+1,mid+1,b);
}

void complete()
{
    f(i,1,RIGHT-1)
    {
        combine(2*i, D[i], U[i]);
        combine(2*i+1, D[i], U[i]);
    }
}
void buildWall(int n,int k,int op[],int left[],int right[],int height[],int finalHeight[]){
    N=n,K=k;
    f(i,1,K)
    {
        int id, l, r, h;
        id=op[i-1],l=left[i-1],r=right[i-1],h=height[i-1];
        char t = id==1 ? 'u' : 'd';
        update(l+1,r+1,t,h,1,1,RIGHT);
    }
    complete();
    f(i,RIGHT,RIGHT+N-1) finalHeight[i-RIGHT]=min(D[i],U[i]);

}

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