Submission #516616

#	Time	Username	Problem	Language	Result	Execution time	Memory
516616		status_coding	Wall (IOI14_wall)	C++14	100 / 100	601 ms	123980 KiB

wall

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

using namespace std;

struct segS
{
    pair<int, int> val= {0, 1e9};
    bool lazy = false;
};

vector<segS> seg;

void calc(int p, pair<int, int> val)
{
    if(val.first > seg[p].val.second)
        seg[p].val = {val.first, val.first};

    else if(val.second < seg[p].val.first)
        seg[p].val = {val.second, val.second};

    else
    {
        seg[p].val.first = max(seg[p].val.first, val.first);
        seg[p].val.second = min(seg[p].val.second, val.second);
    }

    seg[p].lazy = true;
}

void push(int p)
{
    if(!seg[p].lazy)
        return;

    calc(2*p, seg[p].val);
    calc(2*p+1, seg[p].val);

    seg[p].val = {0, 1e9};
    seg[p].lazy=false;
}

void upd(int stt, int drt, int st, int dr, int p, pair<int, int> val)
{
    if(stt == st && drt == dr)
    {
        calc(p, val);
        return;
    }

    push(p);

    int mij=(st+dr)/2;

    if(drt <= mij)
        upd(stt, drt, st, mij, 2*p, val);
    else if(stt > mij)
        upd(stt, drt, mij+1, dr, 2*p+1, val);
    else
    {
        upd(stt, mij, st, mij, 2*p, val);
        upd(mij+1, drt, mij+1, dr, 2*p+1, val);
    }
}

void pushAll(int st, int dr, int p, int ans[])
{
    if(st == dr)
    {
        ans[st] = seg[p].val.first;
        return;
    }

    push(p);

    int mij=(st+dr)/2;

    pushAll(st, mij, 2*p, ans);
    pushAll(mij+1, dr, 2*p+1, ans);
}

void afis(int st, int dr, int p)
{
    cout<<st<<' '<<dr<<' '<<seg[p].val.first<<' '<<seg[p].val.second<<' '<<seg[p].lazy<<'\n';

    if(st < dr)
    {
        int mij=(st+dr)/2;
        afis(st, mij, 2*p);
        afis(mij+1, dr, 2*p+1);
    }
}

void buildWall(int n, int k, int op[], int l[], int r[], int h[], int ans[])
{
    seg.resize(4*n + 4);

    for(int i=0; i<k; i++)
    {
        if(op[i] == 1)
            upd(l[i], r[i], 0, n-1, 1, {h[i], 1e9});
        else
            upd(l[i], r[i], 0, n-1, 1, {0, h[i]});
    }

    pushAll(0, n-1, 1, ans);
}

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