제출 #284373

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
284373		MKopchev	자리 배치 (IOI18_seats)	C++14	17 / 100	4074 ms	57468 KiB

seats

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

const int nmax=1e6+42;

vector< vector<int> > inp;

int n,m;

int min_x[nmax],min_y[nmax],max_x[nmax],max_y[nmax];

bool is[nmax];

int ret;

pair<int,int> where[nmax];

void eval(int from,int to)
{
    for(int i=from;i<=to;i++)
    {
        ret=ret-is[i];

        if(i==0)
        {
            min_x[i]=where[i].first;
            max_x[i]=where[i].first;

            min_y[i]=where[i].second;
            max_y[i]=where[i].second;
        }
        else
        {
            min_x[i]=min(min_x[i-1],where[i].first);
            max_x[i]=max(max_x[i-1],where[i].first);

            min_y[i]=min(min_y[i-1],where[i].second);
            max_y[i]=max(max_y[i-1],where[i].second);
        }

        if(i+1==(max_x[i]-min_x[i]+1)*(max_y[i]-min_y[i]+1))is[i]=1;
        else is[i]=0;

        ret=ret+is[i];
    }
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C)
{
    n=H;
    m=W;

    for(int i=0;i<H*W;i++)
    {
        where[i]={R[i],C[i]};
    }

    eval(0,H*W-1);
}

int swap_seats(int a, int b)
{
    swap(where[a],where[b]);

    eval(min(a,b),max(a,b));

    return ret;
}

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