제출 #1032958

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1032958		lovrot	자리 배치 (IOI18_seats)	C++17	17 / 100	4086 ms	60500 KiB

seats

#include "seats.h"
#include <cassert>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 1e6 + 10;

int n, m, x[N], y[N];
int maxx[N], minx[N], maxy[N], miny[N];
int ans, state[N];

void update(int k, int x) { 
	ans += x - state[k];
	state[k] = x;
}

void give_initial_chart(int hh, int ww, vector<int> R, vector<int> C) {
	n = hh;
	m = ww;
	for(int i = 1; i <= n * m; ++i) { 
		x[i] = R[i - 1];
		y[i] = C[i - 1];
	}
	
	maxx[0] = 0;
	maxy[0] = 0;
	minx[0] = n - 1;
	miny[0] = m - 1;
	for(int i = 1; i <= n * m; ++i) { 
		maxx[i] = max(maxx[i - 1], x[i]);
		maxy[i] = max(maxy[i - 1], y[i]);
		minx[i] = min(minx[i - 1], x[i]);
		miny[i] = min(miny[i - 1], y[i]);

		update(i, ((maxx[i] - minx[i] + 1) * (maxy[i] - miny[i] + 1)) == i);
	}
}

int swap_seats(int a, int b) {
	++a; ++b;
	if(a > b) { swap(a, b); }

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

	for(int i = a; i <= b; ++i) { 
		maxx[i] = max(maxx[i - 1], x[i]);
		maxy[i] = max(maxy[i - 1], y[i]);
		minx[i] = min(minx[i - 1], x[i]);
		miny[i] = min(miny[i - 1], y[i]);

		update(i, ((maxx[i] - minx[i] + 1) * (maxy[i] - miny[i] + 1)) == i);
	}
	return ans;
}

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