Submission #101390

#	Time	Username	Problem	Language	Result	Execution time	Memory
101390		Noam527	Seats (IOI18_seats)	C++17	100 / 100	3181 ms	123272 KiB

seats

#include <bits/stdc++.h>
#define CHECK cout << "ok" << endl
#define finish(x) return cout << x << endl, 0
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7;
const ll inf = 1e18;
const int OO = 0;
const int OOO = 0;
using namespace std;

struct segtree {
	int n;
	vector<int> mn, cnt, tag;
	segtree() {}
	segtree(const vector<int> &a) {
		n = a.size();
		while (n != (n & -n)) n += (n & -n);
		mn.resize(2 * n, 0);
		tag.resize(2 * n, 0);
		cnt.resize(2 * n, 1);
		for (int i = 0; i < a.size(); i++)
			mn[i + n - 1] = a[i];
		for (int i = n - 2; i >= 0; i--) fix(i);
	}
	void push(int x) {
		mn[x] += tag[x];
		if (x < n - 1) {
			tag[2 * x + 1] += tag[x];
			tag[2 * x + 2] += tag[x];
		}
		tag[x] = 0;
	}
	void fix(int x) {
		push(2 * x + 1), push(2 * x + 2);
		mn[x] = min(mn[2 * x + 1], mn[2 * x + 2]);
		if (mn[2 * x + 1] < mn[2 * x + 2])
			cnt[x] = cnt[2 * x + 1];
		else if (mn[2 * x + 1] > mn[2 * x + 2])
			cnt[x] = cnt[2 * x + 2];
		else
			cnt[x] = cnt[2 * x + 1] + cnt[2 * x + 2];
	}
	void upd(int l, int r, int add) {
		if (l > r) return;
		upd(l, r, add, 0, 0, n - 1);
	}
	void upd(int l, int r, int add, int node, int nl, int nr) {
		if (r < nl || nr < l) return;
		if (l <= nl && nr <= r) {
			tag[node] += add;
			return;
		}
		push(node);
		int mid = (nl + nr) / 2;
		upd(l, r, add, 2 * node + 1, nl, mid);
		upd(l, r, add, 2 * node + 2, mid + 1, nr);
		fix(node);
	}
	int query(int l, int r) {
		return query(l, r, 0, 0, n - 1).second;
	}
	pair<int, int> query(int l, int r, int node, int nl, int nr) {
		if (r < nl || nr < l) return{ md, 0 };
		push(node);
		if (l <= nl && nr <= r) {
			return{ mn[node], cnt[node] };
		}
		int mid = (nl + nr) / 2;
		pair<int, int> p1 = query(l, r, 2 * node + 1, nl, mid);
		pair<int, int> p2 = query(l, r, 2 * node + 2, mid + 1, nr);
		if (p1.first == p2.first) return{ p1.first, p1.second + p2.second };
		return min(p1, p2);
	}
	void print() {
		for (int i = 0; i < 2 * n - 1; i++) push(i);
		for (int i = n - 1; i < 2 * n - 1; i++) cout << mn[i] << " "; cout << '\n';
	}
};

int n, m, en;
vector<int> r, c;
vector<vector<int>> A;
segtree S;
vector<int> pre;

void upd(int i, int j, int add) {
	static const int dx[4] = { 0,-1,0,-1 };
	static const int dy[4] = { 0,0,-1,-1 };
	vector<int> T;
	for (int k = 0; k < 4; k++)
		if (0 <= i + dx[k] && i + dx[k] < n && 0 <= j + dy[k] && j + dy[k] < m)
			T.push_back(A[i + dx[k]][j + dy[k]]);
	sort(T.begin(), T.end());
	if (T.size() & 1) T.push_back(en);
	for (int k = 0; k < T.size(); k += 2) {
		if (OO) {
			cout << "cell (" << i << ", " << j << ") adds range [" << T[k] << ", " << T[k + 1] - 1 << "]\n";
		}
		S.upd(T[k], T[k + 1] - 1, add);
	}
}
void slowupd(int i, int j, int add) {
	static const int dx[4] = { 0,-1,0,-1 };
	static const int dy[4] = { 0,0,-1,-1 };
	vector<int> T;
	for (int k = 0; k < 4; k++)
		if (0 <= i + dx[k] && i + dx[k] < n && 0 <= j + dy[k] && j + dy[k] < m)
			T.push_back(A[i + dx[k]][j + dy[k]]);
	sort(T.begin(), T.end());
	if (T.size() & 1) T.push_back(en);
	for (int k = 0; k < T.size(); k += 2) {
		if (OO) {
			cout << "cell (" << i << ", " << j << ") adds range [" << T[k] << ", " << T[k + 1] - 1 << "]\n";
		}
		pre[T[k]] += add;
		if (T[k + 1] < en) pre[T[k + 1]] -= add;
	}
}

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
	n = H;
	m = W;
	en = n * m;
	r = R;
	c = C;

	A.resize(n, vector<int>(m));
	for (int i = 0; i < n * m; i++)
		A[r[i]][c[i]] = i;
	pre.resize(n * m, 0);
	for (int i = 0; i <= n; i++) for (int j = 0; j <= m; j++)
		slowupd(i, j, 1);
	for (int i = 1; i < en; i++) pre[i] += pre[i - 1];
	S = segtree(pre);
	if (OO) {
		cout << "the tree\n";
		S.print();
	}
}

int swap_seats(int a, int b) {
	upd(r[a], c[a], -1);
	upd(r[a], c[a] + 1, -1);
	upd(r[a] + 1, c[a], -1);
	upd(r[a] + 1, c[a] + 1, -1);

	upd(r[b], c[b], -1);
	upd(r[b], c[b] + 1, -1);
	upd(r[b] + 1, c[b], -1);
	upd(r[b] + 1, c[b] + 1, -1);

	swap(A[r[a]][c[a]], A[r[b]][c[b]]);
	swap(r[a], r[b]), swap(c[a], c[b]);

	upd(r[a], c[a], 1);
	upd(r[a], c[a] + 1, 1);
	upd(r[a] + 1, c[a], 1);
	upd(r[a] + 1, c[a] + 1, 1);

	upd(r[b], c[b], 1);
	upd(r[b], c[b] + 1, 1);
	upd(r[b] + 1, c[b], 1);
	upd(r[b] + 1, c[b] + 1, 1);

	if (OO) {
		cout << "the tree\n";
		S.print();
	}
	return S.query(0, n * m - 1);
}
/*
int main() {
	int nn, mm, qq;
	cin >> nn >> mm >> qq;
	vector<int> rr(nn*mm), cc(nn*mm);
	for (auto &i : rr) cin >> i;
	for (auto &i : cc) cin >> i;
	give_initial_chart(nn, mm, rr, cc);
	while (qq--) {
		int a, b;
		cin >> a >> b;
		cout << swap_seats(a, b) << '\n';
	}
}
*/

Compilation message (stderr)

seats.cpp: In constructor 'segtree::segtree(const std::vector<int>&)':
seats.cpp:22:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < a.size(); i++)
                   ~~^~~~~~~~~~
seats.cpp: In member function 'void segtree::print()':
seats.cpp:77:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for (int i = n - 1; i < 2 * n - 1; i++) cout << mn[i] << " "; cout << '\n';
   ^~~
seats.cpp:77:65: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for (int i = n - 1; i < 2 * n - 1; i++) cout << mn[i] << " "; cout << '\n';
                                                                 ^~~~
seats.cpp: In function 'void upd(int, int, int)':
seats.cpp:96:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int k = 0; k < T.size(); k += 2) {
                  ~~^~~~~~~~~~
seats.cpp: In function 'void slowupd(int, int, int)':
seats.cpp:112:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int k = 0; k < T.size(); k += 2) {
                  ~~^~~~~~~~~~

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