Submission #296095

#	Time	Username	Problem	Language	Result	Execution time	Memory
296095		daniel920712	Seats (IOI18_seats)	C++14	0 / 100	542 ms	262148 KiB

seats

#include "seats.h"
#include <stdio.h>
using namespace std;

int N;
int all[1000005];
int what[1000005];
struct A
{
    int l,r;
    int nxl,nxr;
    int small,con;
    int add;
}Node[4000005];
int now=1;
void UPD(int here)
{
    Node[Node[here].nxl].add+=Node[here].add;
    Node[Node[here].nxl].small+=Node[here].add;
    Node[Node[here].nxr].add+=Node[here].add;
    Node[Node[here].nxr].small+=Node[here].add;
    Node[here].add=0;

}
void build(int l,int r,int here)
{
    Node[here].l=l;
    Node[here].r=r;
    Node[here].small=0;
    Node[here].add=0;
    Node[here].con=(r-l+1);
    if(l==r) return ;
    Node[here].nxl=now++;
    Node[here].nxr=now++;
    build(l,(l+r)/2,Node[here].nxl);
    build((l+r)/2+1,r,Node[here].nxr);
}
void cha(int l,int r,int con,int here)
{
    if(Node[here].l==l&&Node[here].r==r)
    {
        Node[here].add+=con;
        Node[here].small+=con;

        return;
    }
    UPD(here);
    if(r<=(Node[here].l+Node[here].r)/2) cha(l,r,con,Node[here].nxl);
    else if(l>(Node[here].l+Node[here].r)/2) cha(l,r,con,Node[here].nxr);
    else
    {
        cha(l,(Node[here].l+Node[here].r)/2,con,here);
        cha((Node[here].l+Node[here].r)/2+1,r,con,here);
    }
    Node[here].con=0;
    Node[here].small=min(Node[Node[here].nxl].small,Node[Node[here].nxr].small);
    if(Node[Node[here].nxl].small==Node[here].small) Node[here].con+=Node[Node[here].nxl].con;
    if(Node[Node[here].nxr].small==Node[here].small) Node[here].con+=Node[Node[here].nxr].con;
}
void give_initial_chart(int H,int W,vector<int> R,vector<int> C)
{
    int i;
    N=H*W;
    for(i=0;i<N;i++)
    {
        R[i]++;
        C[i]++;
        all[i]=C[i];
        what[C[i]]=all[i];
    }
    what[0]=N+1;
    what[N+1]=N+1;
    build(1,N,0);
    for(i=1;i<=N;i++)
    {
        if(what[i]<what[i-1])
        {
            //printf("%d %d\n",what[i],what[i-1]-1);
            cha(what[i],what[i-1]-1,1,0);
        }
        if(what[i]<what[i+1])
        {
            //printf("%d %d\n",what[i],what[i+1]-1);
            cha(what[i],what[i+1]-1,1,0);
        }
    }
    //printf("aa%d\n",Node[0].con);



}

int swap_seats(int a, int b)
{
    int x,y;

    x=all[a];
    y=all[b];

    //printf("%d %d\n",x,y);

    cha(min(what[x],what[x-1]),max(what[x],what[x-1])-1,-1,0);
    cha(min(what[x],what[x+1]),max(what[x],what[x+1])-1,-1,0);

    cha(min(what[y],what[y-1]),max(what[y],what[y-1])-1,-1,0);
    cha(min(what[y],what[y+1]),max(what[y],what[y+1])-1,-1,0);


    swap(all[a],all[b]);
    swap(what[x],what[y]);

    cha(min(what[x],what[x-1]),max(what[x],what[x-1])-1,1,0);
    cha(min(what[x],what[x+1]),max(what[x],what[x+1])-1,1,0);

    cha(min(what[y],what[y-1]),max(what[y],what[y-1])-1,1,0);
    cha(min(what[y],what[y+1]),max(what[y],what[y+1])-1,1,0);



    return Node[0].con;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 6
• Subtask 3: 0 / 20
• Subtask 4: 0 / 6
• Subtask 5: 0 / 33
• Subtask 6: 0 / 30