Submission #1291395

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291395		horka	Wall (IOI14_wall)	C++20	61 / 100	3098 ms	147696 KiB

wall

#include <bits/stdc++.h>
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
using namespace std;
#include "wall.h"
const int inf=1e9+10,c=5e5+5;
struct node
{
    int mx=0,mn=inf;
};
node combine(node a, node b)
{
    node x;
    x.mx=max(a.mx,b.mx);
    x.mn=min(a.mn,b.mn);
    return x;
}
node val[4*c];
void upd(int cs, int tl, int tr, int pos, int tip, int x)
{
    if(tl==tr)
    {
        if(tip==1) val[cs].mx=x;
        else val[cs].mn=x;
        return;
    }
    int mid=(tl+tr)/2;
    if(pos<=mid) upd(2*cs,tl,mid,pos,tip,x);
    else upd(2*cs+1,mid+1,tr,pos,tip,x);
    val[cs]=combine(val[2*cs],val[2*cs+1]);
}
node query(int cs, int tl, int tr, int l, int r)
{
    if(l>r) return {0,inf};
    if(l==tl && r==tr) return val[cs];
    int mid=(tl+tr)/2;
    return combine(query(2*cs,tl,mid,l,min(r,mid)),query(2*cs+1,mid+1,tr,max(mid+1,l),r));
}
void buildWall(int n, int k, int op[], int l[], int r[], int h[], int fh[]){

    for(int i=1; i<=4*k; i++)
        val[i]={0,inf};
    vector<vector<array<int, 3>>> be(n+1),ki(n+1);
    for(int i=0; i<k; i++)
    {
        be[l[i]].push_back({op[i],h[i],i});
        ki[r[i]+1].push_back({op[i],i,0});
    }
    int db=0;
    for(int i=0; i<n; i++)
    {
        for(auto &[o,mag,ind]:be[i])
        {
            upd(1,0,k-1,ind,o,mag);
            db++;
        }
        for(auto &[o,ind,dsa]:ki[i])
        {
            if(o==1) upd(1,0,k-1,ind,1,0);
            else upd(1,0,k-1,ind,2,inf);
            db--;
        }
        if(db>0)
        {
            int lo=-1,hi=k-1; //hi: ahol meg nagy<kis
            while(lo<hi-1)
            {
                int mid=(lo+hi)/2;
                auto x=query(1,0,k-1,mid,k-1);
                if(x.mx<x.mn) hi=mid;
                else lo=mid;
            }
            if(lo<0)
            {
                fh[i]=val[1].mx;
            }
            else
            {
                auto x=query(1,0,k-1,hi,k-1);
                auto y=query(1,0,k-1,lo,k-1);
                bool maxi=0;
                if(x.mn!=y.mn) maxi=1;
                if(maxi) fh[i]=x.mx;
                else fh[i]=x.mn;

            }
        }
    }

  return;
}

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