제출 #1235486

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1235486		nicolo_010	Seats (IOI18_seats)	C++20	17 / 100	4091 ms	145288 KiB

seats

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include "seats.h"
using namespace std;
template <typename T>
using v = vector<T>;
using ll = long long;
using pii = pair<int, int>;
#define rep(i, k, n) for (int i = k; i < n; i++)

v<v<int>> pos;
int n, m;
v<v<int>> mx;
v<int> c;

struct SegTree {
	v<int> tree;
	SegTree(int n) {
		tree.assign(4*n, 0);
	}
	void query(int p, int l, int r, int u, int x) {
		if (l > u || r < u) return;
		if (l == r && r == u) {
			tree[p] = x;
		}
		else {
			int m = (l+r)/2;
			query(2*p, l, m, u, x);
			query(2*p+1, m+1, r, u, x);
			tree[p] = tree[2*p] + tree[2*p+1];			
		}
	}
};

SegTree* st;

void give_initial_chart(int H, int W, v<int> R, v<int> C) {
	pos.resize(H*W);
	c.assign(H*W, 0);
	rep(i, 0, H*W) {
		pos[i] = {R[i], C[i]};
	}
	int mxx, mnx, mxy, mny;
	mxx = mnx = pos[0][0];
	mxy = mny = pos[0][1];
	mx.resize(H*W+1);
	mx[1] = {mxx, mxy, mnx, mny};
	c[0] = 1;
	mx[0] = {-1, -1, 1000000000, 1000000000};
	rep(i, 1, H*W) {
		mxx = max(mxx, pos[i][0]);
		mnx = min(mnx, pos[i][0]);
		mxy = max(mxy, pos[i][1]);
		mny = min(mny, pos[i][1]);
		mx[i+1] = {mxx, mxy, mnx, mny};
		int h = abs(mxx-mnx)+1;
		int w = abs(mxy-mny)+1;
		if (h*w == i+1) c[i] = 1;
		else c[i] = 0;
	}
	st = new SegTree(H*W);
	rep(i, 0, H*W) {
		st->query(1, 0, H*W-1, i, c[i]);
	}
	n = H, m = W;
}

int swap_seats(int a, int b) {
	int mnx, mny, mxx, mxy;
	swap(pos[a][0], pos[b][0]);
	swap(pos[a][1], pos[b][1]);
	//a < b
	if (a > b) swap(a, b);
	mxx = mx[a][0], mxy = mx[a][1];
	mnx = mx[a][2], mny = mx[a][3];
	rep(i, a, b+1) {
		mxx = max(mxx, pos[i][0]);
		mnx = min(mnx, pos[i][0]);
		mxy = max(mxy, pos[i][1]);
		mny = min(mny, pos[i][1]);
		mx[i+1] = {mxx, mxy, mnx, mny};
		int h = abs(mxx-mnx)+1;
		int w = abs(mxy-mny)+1;
		if (h*w == i+1) c[i] = 1;
		else c[i] = 0;
	}
	rep(i, a, b+1) {
		st->query(1, 0, n*m-1, i, c[i]);
	}
	return st->tree[1];
}

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