Submission #380830

#	Time	Username	Problem	Language	Result	Execution time	Memory
380830		IloveN	Wall (IOI14_wall)	C++14	100 / 100	809 ms	171628 KiB

wall

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

using namespace std;
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define all(vr) vr.begin(),vr.end()
#define vi vector<int>
#define vll vector<ll>
const int N=2e6+10;

struct segment_tree
{
    pii it[N * 4];
    int Size;

    pii combine(pii obj, pii range)
    {
        obj.fi = max(obj.fi, range.fi);
        obj.se = max(obj.se, range.fi);
        obj.fi = min(obj.fi, range.se);
        obj.se = min(obj.se, range.se);
        return obj;
    }

    void build(int id, int l, int r)
    {
        if (l == r)
        {
            it[id] = mp(0,1e5);
            return;
        }
        int mid = (l+r) / 2;
        build(id * 2, l, mid);
        build(id * 2 + 1, mid + 1, r);
        it[id] = combine(it[id * 2], it[id * 2 + 1]);
    }

    void update(int id, int l, int r, int pos, pii range)
    {
        if (l == r)
        {
            it[id] = range;
            return;
        }
        int mid = (l+r) / 2;
        if (pos <= mid) update(id * 2, l, mid, pos, range);
        else update(id * 2 + 1, mid + 1, r, pos, range);
        it[id] = combine(it[id * 2], it[id * 2 + 1]);
    }

    void change(int pos, pii range) { update(1, 1, Size, pos, range);}
    int get() { return it[1].fi;}
} seg;

struct event
{
    int id;
    pii range;
};

vector<event> vt[N];

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    for (int i = 0; i < k; ++i)
    {
        pii range = mp(0,1e5);
        if (op[i] == 1) range.fi = height[i];
        else range.se = height[i];
        vt[left[i]].pb({i + 1, range});
        vt[right[i] + 1].pb({i + 1, mp(0,1e5)});
    }
    seg.Size = k;
    seg.build(1, 1, k);
    for (int i = 0; i < n; ++i)
    {
        for (event e : vt[i]) seg.change(e.id, e.range);
        finalHeight[i] = seg.get();
    }
    return;
}


/*int main()
{
    //freopen("ss.inp","r",stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    return 0;
}*/

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