제출 #1284664

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1284664		MMihalev	자리 배치 (IOI18_seats)	C++20	0 / 100	4098 ms	105976 KiB

seats

#include<iostream>
#include<algorithm>
#include<vector>
#include "seats.h"
using namespace std;
const int MAX_N=1e6+6;
int h,w;
struct V
{
    pair<int,int>mi;
    int cntmi,lazy1,lazy3;
};
V tree[4*MAX_N];
int r[MAX_N];
int c[MAX_N];
vector<vector<int>>id;
void push_lazy(int node,int l,int r)
{
    tree[node].mi.first+=tree[node].lazy1;
    tree[node].mi.second+=tree[node].lazy3;
    if(l!=r)
    {
        tree[2*node].lazy1+=tree[node].lazy1;
        tree[2*node].lazy3+=tree[node].lazy3;

        tree[2*node+1].lazy1+=tree[node].lazy1;
        tree[2*node+1].lazy3+=tree[node].lazy3;
    }
    tree[node].lazy1=0;
    tree[node].lazy3=0;
}
void Update(int node,int l,int r,int ql,int qr,int l1,int l3)
{
    push_lazy(node,l,r);
    if(l>qr or r<ql)return;
    if(ql<=l && r<=qr)
    {
        tree[node].lazy1+=l1;
        tree[node].lazy3+=l3;
        push_lazy(node,l,r);
        return;
    }
    int mid=(l+r)/2;
    Update(2*node,l,mid,ql,qr,l1,l3);
    Update(2*node+1,mid+1,r,ql,qr,l1,l3);
    tree[node].mi=min(tree[2*node].mi,tree[2*node+1].mi);
    tree[node].cntmi=(tree[2*node].mi==tree[node].mi ? tree[2*node].cntmi : 0)+
                     (tree[2*node+1].mi==tree[node].mi ? tree[2*node+1].cntmi : 0);
}
vector<int>tmp;
void rem22(int row,int col)
{
    tmp.clear();
    tmp.push_back(id[row][col]);
    tmp.push_back(id[row+1][col]);
    tmp.push_back(id[row][col+1]);
    tmp.push_back(id[row+1][col+1]);
    sort(tmp.begin(),tmp.end());
    Update(1,0,h*w-1,tmp[0],tmp[1]-1,-1,0);
    Update(1,0,h*w-1,tmp[2],tmp[3]-1,0,-1);
}
void add22(int row,int col)
{
    tmp.clear();
    tmp.push_back(id[row][col]);
    tmp.push_back(id[row+1][col]);
    tmp.push_back(id[row][col+1]);
    tmp.push_back(id[row+1][col+1]);
    sort(tmp.begin(),tmp.end());
    Update(1,0,h*w-1,tmp[0],tmp[1]-1,+1,0);
    Update(1,0,h*w-1,tmp[2],tmp[3]-1,0,+1);
}
void rem(int row,int col)
{
    rem22(row-1,col-1);
    rem22(row-1,col);
    rem22(row,col-1);
    rem22(row,col);
}
void add(int row,int col)
{
    add22(row-1,col-1);
    add22(row-1,col);
    add22(row,col-1);
    add22(row,col);
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C)
{
    h=H;
    w=W;
    id.resize(h+5);
    for(int i=0;i<h+5;i++)id[i].resize(w+5);
    for(int i=0;i<h*w;i++)
    {
        r[i]=R[i]+1;
        c[i]=C[i]+1;
        id[r[i]][c[i]]=i;
    }

    for(int i=0;i<h+2;i++)
    {
        for(int j=0;j<w+2;j++)
        {
            if(i==0 or j==0 or i==h+1 or j==w+1)
            {
                id[i][j]=h*w;
            }
        }
    }

    for(int i=0;i<h*w;i++)
    {
        add(r[i],c[i]);
    }
}

int swap_seats(int a, int b)
{
    rem(r[a],c[a]);
    rem(r[b],c[b]);
    swap(id[r[a]][c[a]],id[r[b]][c[b]]);
    swap(r[a],r[b]);
    swap(c[a],c[b]);
    add(r[a],c[a]);
    add(r[b],c[b]);
    return tree[1].cntmi;
}

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