Submission #68365

#	Time	Username	Problem	Language	Result	Execution time	Memory
68365		MKopchev	Wall (IOI14_wall)	C++14	100 / 100	960 ms	211720 KiB

wall

#include<bits/stdc++.h>
#include "wall.h"
using namespace std;
const int nmax=1<<21,inf=1e9;
struct vert
{
    int small,big,red/*forced reduce*/,add/*forced add*/;
    //red>=add
};
vert tree[2*nmax+42];
void upd(int &node,int &_node)
{
    /*
    tree[_node].add=max(tree[_node].add,tree[node].add);
    tree[_node].red=min(tree[_node].red,tree[node].red);
    if(tree[_node].add>tree[_node].red)
    {
        tree[_node].add=tree[node].add;
        tree[_node].red=tree[node].red;
    }
    */
    tree[_node].add=min(tree[_node].add,tree[node].red);
    tree[_node].add=max(tree[_node].add,tree[node].add);

    tree[_node].red=min(tree[_node].red,tree[node].red);
    tree[_node].red=max(tree[_node].red,tree[node].add);
    assert(tree[_node].add<=tree[_node].red);
}
int _;
void update_node(int &node)
{
    if(tree[node].red==inf&&tree[node].add==0)return;
    _=node*2;
    upd(node,_);
    _++;
    upd(node,_);
    tree[node].red=inf;
    tree[node].add=0;
}
void update_add(int node,int l,int r,int lq,int rq,int h)
{
    if(l==lq&&r==rq)
    {
        if(tree[node].add>=h)return;
        if(tree[node].add<=h&&h<=tree[node].red)
        {
        tree[node].add=h;
        tree[node].small=h;
        return;
        }
        //tree[node].add<h
        tree[node].add=h;
        tree[node].red=h;
        tree[node].small=h;
        tree[node].big=h;
        return;
    }
    update_node(node);
    int av=(l+r)/2;
    if(lq<=av)update_add(node*2,l,av,lq,min(av,rq),h);
    if(av<rq)update_add(node*2+1,av+1,r,max(av+1,lq),rq,h);
    tree[node].small=min(tree[node*2].small,tree[node*2+1].small);
    tree[node].big=min(tree[node*2].big,tree[node*2+1].big);
}
void update_reduce(int node,int l,int r,int lq,int rq,int h)
{
    if(l==lq&&r==rq)
    {
        if(tree[node].red<=h)return;
        if(tree[node].red>=h&&h>=tree[node].add)
        {
        tree[node].red=h;
        tree[node].big=h;
        return;
        }
        //tree[node].red>h
        tree[node].add=h;
        tree[node].red=h;
        tree[node].small=h;
        tree[node].big=h;
        return;
    }
    update_node(node);
    int av=(l+r)/2;
    if(lq<=av)update_reduce(node*2,l,av,lq,min(av,rq),h);
    if(av<rq)update_reduce(node*2+1,av+1,r,max(av+1,lq),rq,h);
    tree[node].small=min(tree[node*2].small,tree[node*2+1].small);
    tree[node].big=min(tree[node*2].big,tree[node*2+1].big);
}
int cop[nmax];
void move_down(int node,int l,int r)
{
    if(l==r)
    {
        cop[l]=tree[node].add;
        return;
    }
    update_node(node);
    int av=(l+r)/2;
    move_down(node*2,l,av);
    move_down(node*2+1,av+1,r);
}
void buildWall(int n, int k, int op[], int left[], int right[],int height[], int finalHeight[])
{
    for(int i=1;i<2*nmax+42;i++)
        tree[i].red=inf;
    for(int i=0;i<k;i++)
    {
        if(op[i]==1)update_add(1,0,n-1,left[i],right[i],height[i]);
        else update_reduce(1,0,n-1,left[i],right[i],height[i]);
        /*
        for(int j=1;j<=4*n;j++)
            cout<<tree[j].small<<" "<<tree[j].big<<" "<<tree[j].red<<" "<<tree[j].add<<endl;
        */
    }
    move_down(1,0,n-1);
    for(int j=0;j<n;j++)
        finalHeight[j]=cop[j];
}
/*
const int n=10,k=6;
int op[k]={1,2,2,1,1,2};
int lef[k]={1,4,3,0,2,6};
int righ[k]={8,9,6,5,2,7};
int height[k]={4,1,5,3,5,0};
int fin[n];
int main()
{
buildWall(n,k,op,lef,righ,height,fin);
for(int i=0;i<n;i++)cout<<fin[i]<<" ";cout<<endl;
return 0;
}
*/

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