Submission #799329

#	Time	Username	Problem	Language	Result	Execution time	Memory
799329		prvocislo	Seats (IOI18_seats)	C++17	100 / 100	3347 ms	135652 KiB

seats

#include "seats.h"
#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <vector>
typedef long long ll;
typedef long double ld;
using namespace std;

const int maxn = 1 << 20;
vector<int> add(maxn * 2), il(maxn * 2), ir(maxn * 2);
vector<pair<int, int> > st(maxn * 2); // minimum v tomto vrchole a pocet tych minim
pair<int, int> merge(pair<int, int> a, pair<int, int> b)
{
	if (a.first == b.first) return make_pair(a.first, a.second + b.second);
	return min(a, b);
}
void upd(int li, int ri, int d, int vr = 1)
{
	if (li > ri || ri < il[vr] || ir[vr] < li) return;
	if (li <= il[vr] && ir[vr] <= ri)
	{
		st[vr].first += d, add[vr] += d;
		return;
	}
	upd(li, ri, d, (vr << 1)), upd(li, ri, d, (vr << 1) | 1);
	st[vr] = merge(st[vr << 1], st[(vr << 1) | 1]);
	st[vr].first += add[vr];
}
int nr, nc;
vector<int> r, c;
vector<vector<int> > num;
void do2x2(int i, int j, int d) // spracuje stvorec [i, i+1], [j, j+1]
{
	vector<int> v;
	for (int ri = i; ri <= i + 1; ri++) for (int cj = j; cj <= j + 1; cj++)
	{
		if (ri >= 0 && cj >= 0 && ri < nr && cj < nc) v.push_back(num[ri][cj]);
		else v.push_back(nr * nc);
	}
	sort(v.begin(), v.end());
	upd(v[0], v[1] - 1, d), upd(v[2], v[3] - 1, d);
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) 
{
	for (int i = maxn; i < maxn * 2; i++)
	{
		il[i] = ir[i] = i - maxn;
		if (i - maxn < H * W) st[i] = { 0, 1 };
		else st[i] = { 1000'000'000, 1 };
	}
	for (int i = maxn - 1; i > 0; i--) il[i] = il[i << 1], ir[i] = ir[(i << 1) | 1], st[i] = merge(st[i << 1], st[(i << 1) | 1]);
	nr = H, nc = W;
	r = R, c = C;
	num.assign(nr, vector<int>(nc, 0));
	for (int i = 0; i < nr * nc; i++) num[r[i]][c[i]] = i;
	for (int i = -1; i < nr; i++) for (int j = -1; j < nc; j++) do2x2(i, j, 1);
}

int swap_seats(int a, int b) 
{
	set<pair<int, int> > s;
	for (int i = r[a] - 1; i <= r[a]; i++) for (int j = c[a] - 1; j <= c[a]; j++) s.insert({ i, j });
	for (int i = r[b] - 1; i <= r[b]; i++) for (int j = c[b] - 1; j <= c[b]; j++) s.insert({ i, j });

	for (pair<int, int> i : s) do2x2(i.first, i.second, -1);
	swap(num[r[a]][c[a]], num[r[b]][c[b]]);
	swap(r[a], r[b]);
	swap(c[a], c[b]);
	for (pair<int, int> i : s) do2x2(i.first, i.second, 1);
	
	if (st[1].first == 4) return st[1].second;
	return 0;
}

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