Submission #597025

#	Time	Username	Problem	Language	Result	Execution time	Memory
597025		Bench0310	Wall (IOI14_wall)	C++17	100 / 100	701 ms	169920 KiB

wall

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

using namespace std;
typedef long long ll;

const int inf=(1<<30);

struct node
{
    int a,b;
    node(){a=0;b=inf;}
    node(int x,int y){a=x;b=y;}
    int eval(int x)
    {
        if(x<=a) return a;
        else if(a<=x&&x<=b) return x;
        else return b;
    }
    void pull(node &l,node &r)
    {
        a=r.eval(l.a);
        b=r.eval(l.b);
    }
};

const int N=500000;
node tree[4*N];

void update(int idx,int l,int r,int pos,node x)
{
    if(l==r) tree[idx]=x;
    else
    {
        int m=(l+r)/2;
        if(pos<=m) update(2*idx,l,m,pos,x);
        else update(2*idx+1,m+1,r,pos,x);
        tree[idx].pull(tree[2*idx],tree[2*idx+1]);
    }
}

void buildWall(int n,int k,int op[],int left[],int right[],int height[],int res[])
{
    vector<int> add[n];
    vector<int> rm[n];
    for(int i=0;i<k;i++)
    {
        add[left[i]].push_back(i);
        rm[right[i]].push_back(i);
    }
    for(int i=0;i<n;i++)
    {
        for(int j:add[i])
        {
            if(op[j]==1) update(1,0,k-1,j,node(height[j],inf));
            else update(1,0,k-1,j,node(0,height[j]));
        }
        res[i]=tree[1].a;
        for(int j:rm[i]) update(1,0,k-1,j,node());
    }
}

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