제출 #373595

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
373595		BartolM	자리 배치 (IOI18_seats)	C++17	0 / 100	4070 ms	39532 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
 
using namespace std;
 
#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;
 
const int INF=0x3f3f3f3f;
const int N=1e6+5;
 
int n, r, c;
int sol=0;
pii p[N], maxi[N], mini[N];
 
int ok(int i) {
    return (maxi[i].X-mini[i].X+1)*(maxi[i].Y-mini[i].Y+1)==i+1;
}
 
void upd(int i) {
    maxi[i].X=mini[i].X=p[i].X;
    maxi[i].Y=mini[i].Y=p[i].Y;
    if (i) maxi[i].X=max(maxi[i-1].X, p[i].X), maxi[i].Y=max(maxi[i-1].Y, p[i].Y);
    if (i) mini[i].X=min(mini[i-1].X, p[i].X), mini[i].Y=min(mini[i-1].Y, p[i].Y);
    if (ok(i)) sol++;
}
 
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
    n=H*W; r=H; c=W;
    for (int i=0; i<n; ++i) {
        p[i]=mp(R[i], C[i]);
        upd(i);
    }
}
 
int swap_seats(int a, int b) {
    for (int i=a; i<=b; ++i) if (ok(i)) sol--;
    swap(p[a], p[b]);
    for (int i=a; i<=b; ++i) upd(i);
    return sol;
}

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