제출 #296863

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
296863		daniel920712	자리 배치 (IOI18_seats)	C++14	0 / 100	4038 ms	131288 KiB

seats

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

int N,H,W;
pair < int , int > all[1000005];
vector < int > what[1000005];
int how1[1000005]={0};
int how2[1000005]={0};
struct A
{
    int l,r;
    int nxl,nxr;
    int small1,small2,con;
    int add1,add2;
}Node[4000005];
int now=1;
void UPD(int here)
{
    Node[Node[here].nxl].add1+=Node[here].add1;
    Node[Node[here].nxl].small1+=Node[here].add1;
    Node[Node[here].nxr].add1+=Node[here].add1;
    Node[Node[here].nxr].small1+=Node[here].add1;
    Node[here].add1=0;

    Node[Node[here].nxl].add2+=Node[here].add2;
    Node[Node[here].nxl].small2+=Node[here].add2;
    Node[Node[here].nxr].add2+=Node[here].add2;
    Node[Node[here].nxr].small2+=Node[here].add2;
    Node[here].add2=0;

}
void build(int l,int r,int here)
{
    Node[here].l=l;
    Node[here].r=r;
    Node[here].small1=0;
    Node[here].small2=0;
    Node[here].add1=0;
    Node[here].add2=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 cha1(int l,int r,int con,int here)
{

    if(l>r) return;


    if(Node[here].l==l&&Node[here].r==r)
    {
        Node[here].add1+=con;
        Node[here].small1+=con;
        return;
    }
    UPD(here);
    if(r<=(Node[here].l+Node[here].r)/2) cha1(l,r,con,Node[here].nxl);
    else if(l>(Node[here].l+Node[here].r)/2) cha1(l,r,con,Node[here].nxr);
    else
    {
        cha1(l,(Node[here].l+Node[here].r)/2,con,Node[here].nxl);
        cha1((Node[here].l+Node[here].r)/2+1,r,con,Node[here].nxr);
    }
    Node[here].con=0;
    Node[here].small1=min(Node[Node[here].nxl].small1,Node[Node[here].nxr].small1);
    Node[here].small2=min(Node[Node[here].nxl].small2,Node[Node[here].nxr].small2);
    if(Node[Node[here].nxl].small1==Node[here].small1&&Node[Node[here].nxl].small2==0) Node[here].con+=Node[Node[here].nxl].con;
    if(Node[Node[here].nxr].small1==Node[here].small1&&Node[Node[here].nxr].small2==0) Node[here].con+=Node[Node[here].nxr].con;
}

void cha2(int l,int r,int con,int here)
{
    if(l>r) return;

    if(Node[here].l==l&&Node[here].r==r)
    {
        Node[here].add2+=con;
        Node[here].small2+=con;
        return;
    }
    UPD(here);
    if(r<=(Node[here].l+Node[here].r)/2) cha2(l,r,con,Node[here].nxl);
    else if(l>(Node[here].l+Node[here].r)/2) cha2(l,r,con,Node[here].nxr);
    else
    {
        cha2(l,(Node[here].l+Node[here].r)/2,con,Node[here].nxl);
        cha2((Node[here].l+Node[here].r)/2+1,r,con,Node[here].nxr);
    }
    Node[here].con=0;
    Node[here].small1=min(Node[Node[here].nxl].small1,Node[Node[here].nxr].small1);
    Node[here].small2=min(Node[Node[here].nxl].small2,Node[Node[here].nxr].small2);
    if(Node[Node[here].nxl].small1==Node[here].small1&&Node[Node[here].nxl].small2==0) Node[here].con+=Node[Node[here].nxl].con;
    if(Node[Node[here].nxr].small1==Node[here].small1&&Node[Node[here].nxr].small2==0) Node[here].con+=Node[Node[here].nxr].con;
}
void F(int x,int y,int t)
{
    //printf("aa %d %d %d\n",x,y,t);
    int a=what[x][y],b=what[x+1][y],c=what[x][y+1],d=what[x+1][y+1];
    if(a>b) swap(a,b);
    if(a>c) swap(a,c);
    if(a>d) swap(a,d);
    if(b>c) swap(b,c);
    if(b>d) swap(b,d);
    if(c>d) swap(c,d);
    //if(!(a<=b&&b<=c&&c<=d)) while(1) ;
    cha1(a,b-1,t,0);
    cha2(c,d-1,t,0);

}
void give_initial_chart(int H,int W,vector<int> R,vector<int> C)
{
    //printf("aa\n");
    int i,j;
    N=H*W;
    ::H=H;
    ::W=W;
    for(i=0;i<=H+1;i++) for(j=0;j<=W+1;j++) what[i].push_back(N);
    for(i=0;i<N;i++)
    {
        R[i]++;
        C[i]++;
        all[i]=make_pair(R[i],C[i]);
        what[R[i]][C[i]]=i;

    }
    build(0,N-1,0);
    for(i=0;i<=H;i++) for(j=0;j<=W;j++) F(i,j,1);
    //printf("%d\n",Node[0].small1);
}

int swap_seats(int a, int b)
{
    int x1,y1,x2,y2,ans=0;
    x1=all[a].first;
    y1=all[a].second;

    x2=all[b].first;
    y2=all[b].second;

    F(x1-1,y1-1,-1);
    F(x1-1,y1,-1);
    F(x1,y1-1,-1);
    F(x1,y1,-1);

    F(x2-1,y2-1,-1);
    F(x2-1,y2,-1);
    F(x2,y2-1,-1);
    F(x2,y2,-1);

    swap(all[a],all[b]);
    swap(what[x1][y1],what[x2][y2]);

    F(x1-1,y1-1,1);
    F(x1-1,y1,1);
    F(x1,y1-1,1);
    F(x1,y1,1);

    F(x2-1,y2-1,1);
    F(x2-1,y2,1);
    F(x2,y2-1,1);
    F(x2,y2,1);

    //for(int i=0;i<N;i++) if(how1[i]==4&&how2[i]==0) ans++;

    //printf("%d ",Node[0].con);
    return Node[0].con;
}

컴파일 시 표준 에러 (stderr) 메시지

seats.cpp: In function 'int swap_seats(int, int)':
seats.cpp:137:21: warning: unused variable 'ans' [-Wunused-variable]
  137 |     int x1,y1,x2,y2,ans=0;
      |                     ^~~

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