Submission #744646

#	Time	Username	Problem	Language	Result	Execution time	Memory
744646		angels	Wall (IOI14_wall)	C++14	100 / 100	613 ms	69520 KiB

wall

/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

#include <bits/stdc++.h>
 
using namespace std;

int RIGHT=2097152;
int d[5000000], g[5000000];
int N, K;
void update(int l, int r, int p, int h, int n, int a, int b)
{
    if(b<l || r<a) 
        return;
    if(l<=a && b<=r)
    {
        if(p==1)        //add
        {
            d[n]=max(d[n], h);
            g[n]=max(g[n], h);
        }
        if(p==2)        //remove
        {
            d[n]=min(d[n], h);
            g[n]=min(g[n], h);
        }
        return;
    }
    d[2*n]=max(min(d[2*n], d[n]), g[n]);
    g[2*n]=min(max(g[2*n], g[n]), d[n]);
    d[2*n+1]=max(min(d[2*n+1], d[n]), g[n]);
    g[2*n+1]=min(max(g[2*n+1], g[n]), d[n]);
    d[n]=10000000;
    g[n]=0;
    int mid=(a+b)/2;
    update(l, r, p, h, 2*n, a, mid);
    update(l, r, p, h, 2*n+1, mid+1, b);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    N=n, K=k;
    for(int i=0; i<K; i++)
    {
        int p, l, r, h;
        cin>>p>>l>>r>>h;
        p=op[i]; 
        l=left[i];
        r=right[i];
        h=height[i];
        update(l+1, r+1, p, h, 1, 1, RIGHT);
    }
    for(int i=1; i<=RIGHT-1; i++)
    {
        d[2*i]=max(min(d[2*i], d[i]), g[i]);
        g[2*i]=min(max(g[2*i], g[i]), d[i]);
        d[2*i+1]=max(min(d[2*i+1], d[i]), g[i]);
        g[2*i+1]=min(max(g[2*i+1], g[i]), d[i]);
    }
    for(int i=RIGHT; i<=RIGHT+N-1; i++)
    {
        finalHeight[i-RIGHT]=min(d[i],g[i]);
    }
}
/*int main()
{
    cin>>N>>K;
    for(int i=1; i<=K; i++)
    {
        int p, l, r, h;
        cin>>p>>l>>r>>h;
        update(l+1, r+1, p, h, 1, 1, RIGHT);
    }
    for(int i=1; i<=RIGHT-1; i++)
    {
        d[2*i]=max(min(d[2*i], d[i]), g[i]);
        g[2*i]=min(max(g[2*i], g[i]), d[i]);
        d[2*i+1]=max(min(d[2*i+1], d[i]), g[i]);
        g[2*i+1]=min(max(g[2*i+1], g[i]), d[i]);
    }
    for(int i=RIGHT; i<=RIGHT+N-1; i++)
        cout<<min(d[i],g[i])<<"\n";
}*/

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