Submission #155248

#	Time	Username	Problem	Language	Result	Execution time	Memory
155248		rama_pang	Seats (IOI18_seats)	C++14	0 / 100	399 ms	72048 KiB

seats

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

struct bit {
	vector<int> tree;
	void init(int n) {
		tree.assign(n + 1, 0);
	}
	void upd(int n, int x) {
		for (int i = n + 1; i < tree.size(); i += i & -i) tree[i] += x;
	}
	int ask(int n, int res = 0) {
		for (int i = n + 1; i > 0; i -= i & -i) res += tree[i];
		return res;
	}
} solver;

int H, W;
vector<int> R, C;
vector<int> special_grid;
vector<pair<int, int>> updates;
vector<vector<int>> grid;
void give_initial_chart(int h, int w, vector<int> r, vector<int> c) {
	H = h, W = w;
	R = r, C = c;
	special_grid.resize(H * W);
	solver.init(H * W);
	grid.assign(H, vector<int>(W, -1));
	for (int i = 0; i < H * W; i++) {
		if (i > 0) special_grid[i] = special_grid[i - 1];
		grid[R[i]][C[i]] = i;
		if (C[i] == 0 || grid[R[i]][C[i] - 1] == -1) special_grid[i]++;
		if (C[i] > 0 && grid[R[i]][C[i] - 1] != -1) special_grid[i]--;
		if (C[i] == W - 1 || grid[R[i]][C[i] + 1] == -1) special_grid[i]++;
		if (C[i] < W - 1 && grid[R[i]][C[i] + 1] != -1) special_grid[i]--;
	}
	for (int i = 0; i < H * W; i++) {
		if (special_grid[i] == 2) solver.upd(i, 1);
	}
}

int swap_seats(int a, int b) {
	int leftA, rightA, leftB, rightB, A, B;
	leftA = (C[a] > 0)? grid[R[a]][C[a] - 1] : 1e8;
	rightA = (C[a] < W - 1)? grid[R[a]][C[a] + 1] : 1e8;
	leftB = (C[b] > 0)? grid[R[b]][C[b] - 1] : 1e8;
	rightB = (C[b] < W - 1)? grid[R[b]][C[b] + 1] : 1e8;
	A = grid[R[a]][C[a]];
	B = grid[R[b]][C[b]];

	int updA = 0, updLA = 0, updRA = 0, updB = 0, updLB = 0, updRB = 0;

	if (leftA > A) 	updLA++;
	if (rightA > A) updRA++;
	if (leftA > B) 	updLA--;
	if (rightA > B) updRA--;
	
	if (leftB > B) 	updLB++;
	if (rightB > B) updRB++;
	if (leftB > A) 	updLB--;
	if (rightB > A) updRB--;
	
	if (A > leftA)	updA++;
	if (A > rightA)	updA++;
	if (A > leftB)	updA--;
	if (A > rightB)	updA--;
	
	if (B > leftB)	updB++;
	if (B > rightB)	updB++;
	if (B > leftA)	updB--;
	if (B > rightA)	updB--;
	
	if (special_grid[leftA] == 2 && special_grid[leftA] + updLA != 2) {
		solver.upd(leftA, -1);
	} else if (special_grid[leftA] != 2 && special_grid[leftA] + updLA == 2) {
		solver.upd(leftA, +1);
	}
	special_grid[leftA] += updLA;
	
	if (special_grid[rightA] == 2 && special_grid[rightA] + updRA != 2) {
		solver.upd(rightA, -1);
	} else if (special_grid[rightA] != 2 && special_grid[rightA] + updRA == 2) {
		solver.upd(rightA, +1);
	}
	special_grid[rightA] += updRA;
	
	if (special_grid[leftB] == 2 && special_grid[leftB] + updLB != 2) {
		solver.upd(leftB, -1);
	} else if (special_grid[leftB] != 2 && special_grid[leftB] + updLB == 2) {
		solver.upd(leftB, +1);
	}
	special_grid[leftB] += updLB;
	
	if (special_grid[rightB] == 2 && special_grid[rightB] + updRB != 2) {
		solver.upd(rightB, -1);
	} else if (special_grid[rightB] != 2 && special_grid[rightB] + updRB == 2) {
		solver.upd(rightB, +1);
	}
	special_grid[rightB] += updRB;
	
	swap(R[a], R[b]);
	swap(C[a], C[b]);
	return solver.ask(H * W);
}

Compilation message (stderr)

seats.cpp: In member function 'void bit::upd(int, int)':
seats.cpp:11:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = n + 1; i < tree.size(); i += i & -i) tree[i] += x;
                       ~~^~~~~~~~~~~~~

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