Submission #135701

#	Time	Username	Problem	Language	Result	Execution time	Memory
135701		vince	Wall (IOI14_wall)	C++14	100 / 100	1075 ms	100980 KiB

wall

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<utility>
#include<stack>
#include<queue>
#include<map>
#include<set>

#define fi first
#define se second
#define long long long

using namespace std;

int mn[8000003], mx[8000003];
int lazy[8000003];

void cek_lazy(int pos, int kir, int kan)
{
    if(lazy[pos] != -1)
    {
        mn[pos] = lazy[pos];
        mx[pos] = lazy[pos];
        if(kan-kir) lazy[pos*2] = lazy[pos*2+1] = lazy[pos];
        lazy[pos] = -1;
    }
}

void update(int pos, int kir, int kan, int qkir, int qkan, int op, int val)
{
    
    
    cek_lazy(pos, kir, kan);
//    printf("POS : %d %d %d Q : %d %d\n", pos, kir, kan, qkir, qkan);
    if(kan < qkir || qkan < kir) return;
    if(op == 1 && mn[pos] > val) return;
    if(op == 2 && mx[pos] < val) return;
    if(op == 1 && mx[pos] <= val && qkir <= kir && kan <= qkan)
    {
        lazy[pos] = val;
        cek_lazy(pos, kir, kan);
        return;
    }
    if(op == 2 && mn[pos] >= val && qkir <= kir && kan <= qkan)
    {
        lazy[pos] = val;
        cek_lazy(pos, kir, kan);
        return;
    }
    if(kir == kan) return;
    
    int mid = (kir+kan)/2;
    update(pos*2, kir, mid, qkir, qkan, op, val);
    update(pos*2+1, mid+1, kan, qkir, qkan, op, val);
    mn[pos] = min(mn[pos*2], mn[pos*2+1]);
    mx[pos] = max(mx[pos*2], mx[pos*2+1]);
}

int query(int pos, int kir, int kan, int idx)
{
    cek_lazy(pos, kir, kan);
    
    if(kir == idx && kan == idx) return mx[pos];
    
    int mid = (kir+kan)/2;
    if(idx <= mid) return query(pos*2, kir, mid, idx);
    else return query(pos*2+1, mid+1, kan, idx);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    memset(lazy, -1, sizeof lazy);
    for(int i = 0; i < k; i++)
    {
//        printf("%d %d %d %d\n", op[i], left[i], right[i], height[i]);
        update(1, 0, n-1, left[i], right[i], op[i], height[i]);
    }
    for(int i = 0; i < n; i++)
        finalHeight[i] = query(1, 0, n-1, i);
    return;
}

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