Submission #423124

#	Time	Username	Problem	Language	Result	Execution time	Memory
423124		jtnydv25	Seats (IOI18_seats)	C++17	100 / 100	2999 ms	149276 KiB

seats

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

#define ll long long
#define pii pair<int, int>
#define all(c) ((c).begin()), ((c).end())
#define sz(x) ((int)(x).size())

#ifdef LOCAL
#include <print.h>
#else
#define trace(...)
#define endl '\n'
#endif

// min, min_count segtree
struct Data{
	int mn, mncnt;
	Data() : mn(0), mncnt(1){}
	Data(int mn, int mncnt) : mn(mn), mncnt(mncnt){}
};
Data merge(const Data & A, const Data & B){
	Data ret;
	ret.mn = min(A.mn, B.mn);
	ret.mncnt = (A.mn == ret.mn ? A.mncnt : 0) + (B.mn == ret.mn ? B.mncnt : 0);
	return ret;
}

struct segtree{
	vector<Data> tree;
	vector<int> lazy;
	int n;
	segtree(){}
	segtree(vector<int> vals) : n(vals.size()){
		tree.resize(4 * n);
		lazy.resize(4 * n);
		function<void(int, int, int)> make = [&](int s, int e, int ind){
			if(s == e){
				tree[ind] = Data(vals[s], 1);
				return;
			}
			int mid = (s + e) >> 1;
			make(s, mid, 2 * ind);
			make(mid + 1, e, 2 * ind + 1);
			tree[ind] = merge(tree[2 * ind], tree[2 * ind + 1]);
		};
		make(0, n - 1, 1);
	}
	void push(int s, int e, int ind){
		int l = lazy[ind];
		if(l == 0) return;
		tree[ind].mn += l;
		if(s != e){
			lazy[2 * ind] += l;
			lazy[2 * ind + 1] += l;
		}
		lazy[ind] = 0;
	}
	void add(int L, int R, int v, int s, int e, int ind){
		push(s, e, ind);
		if(L > e || s > R) return;
		if(s >= L && e <= R){
			lazy[ind] += v;
			push(s, e, ind);
			return;
		}
		int mid = (s + e) >> 1;
		add(L, R, v, s, mid, 2 * ind);
		add(L, R, v, mid + 1, e, 2 * ind + 1);
		tree[ind] = merge(tree[2 * ind], tree[2 * ind + 1]);
	}
	void add(int L, int R, int v){
		R = min(R, n - 1);
		if(L > R) return;
		add(L, R, v, 0, n - 1, 1);
	}
};

int H, W;
vector<int> R, C;
vector<vector<int>> when;
segtree st;
vector<int> init;
void add_contribution(int i, int j, int k, bool flag = 0){
	vector<int> times;
	for(int _i : {i, i + 1}) for(int _j : {j, j + 1}){
		times.push_back(when[_i][_j]);
	}
	sort(all(times));
	for(int i : {0, 2}){
		if(!flag) st.add(times[i], times[i + 1] - 1, k);
		else if(times[i] < times[i + 1]){
			init[times[i]]++;
			if(times[i + 1] < H * W) init[times[i + 1]]--;
		}
	}
}
void give_initial_chart(int h, int w, vector<int> r, vector<int> c){
	H = h; W = w;
	R = r; C = c;
	when.assign(H + 2, vector<int>(W + 2, H * W));
	init.resize(H * W);
	for(int i = 0; i < H * W; i++){
		R[i]++; C[i]++;
		when[R[i]][C[i]] = i;
	}
	for(int i = 0; i <= H; i++){
		for(int j = 0; j <= W; j++){
			add_contribution(i, j, 1, true);
		}
	}
	for(int i = 1; i < H * W; i++) init[i] += init[i - 1];
	st = segtree(init);
}

int swap_seats(int a, int b) {
	set<pair<int, int>> changes;
	int u = R[a], v = C[a];
	for(int i : {u - 1, u})
		for(int j : {v - 1, v})
			changes.insert({i, j});
	u = R[b], v = C[b];

	for(int i : {u - 1, u})
		for(int j : {v - 1, v})
			changes.insert({i, j});
	for(auto it : changes) add_contribution(it.first, it.second, -1);
	when[R[b]][C[b]] = a;
	when[R[a]][C[a]] = b;
	swap(R[a], R[b]);
	swap(C[a], C[b]);
	for(auto it : changes) add_contribution(it.first, it.second, 1);
	Data D = st.tree[1];
	assert(D.mn == 4);
	return D.mncnt;
}

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