Submission #1215393

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215393		JooDdae	Seats (IOI18_seats)	C++20	100 / 100	2943 ms	127996 KiB

seats

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

#define mid ((l+r) >> 1)

const int dx[4] = {0, 0, -1, -1}, dy[4] = {0, -1, 0, -1}, S[4] = {1, -1, (int)1e9, (int)-1e9};

array<ll, 2> t[4004004];
ll lz[4004004];

int n, h, w, x[1001001], y[1001001], cb, cw;
vector<vector<int>> mp;

void lazy_update(int node, int l, int r) {
	if(!lz[node]) return;
	t[node][0] += lz[node];
	if(l != r) lz[node*2] += lz[node], lz[node*2+1] += lz[node];
	lz[node] = 0;
}

void update(int nl, int nr, int val, int node = 1, int l = 0, int r = n-1) {
	lazy_update(node, l, r);
	if(nr < l || r < nl) return;
	if(nl <= l && r <= nr) {
		lz[node] += val;
		lazy_update(node, l, r);
		return;
	}
	update(nl, nr, val, node*2, l, mid), update(nl, nr, val, node*2+1, mid+1, r);
	if(t[node*2][0] == t[node*2+1][0]) t[node] = t[node*2], t[node][1] += t[node*2+1][1];
	else t[node] = min(t[node*2], t[node*2+1]);
}

void build(int node = 1, int l = 0, int r = n-1) {
	t[node][1] = r-l+1;
	if(l == r) return;
	build(node*2, l, mid), build(node*2+1, mid+1, r);
}

void query(int x, int y, int k) {
	int p[4] = {mp[x][y], mp[x+1][y], mp[x][y+1], mp[x+1][y+1]};
	for(int i=0;i<4;i++) for(int j=i+1;j<4;j++) if(p[i] > p[j]) swap(p[i], p[j]);
	for(int i=0;i<4;i++) update(p[i], n-1, S[i]*k);
}

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
	n = H*W, h = H, w = W;
	for(int i=0;i<n;i++) x[i] = R[i]+1, y[i] = C[i]+1;
	mp.resize(h+2, vector<int>(w+2, n));
	build();
	for(int i=0;i<n;i++) mp[x[i]][y[i]] = i;
	for(int i=0;i<=h;i++) for(int j=0;j<=w;j++) query(i, j, 1);
}

int swap_seats(int a, int b) {
	for(int i=0;i<4;i++) query(x[a]+dx[i], y[a]+dy[i], -1);
	for(int i=0;i<4;i++) query(x[b]+dx[i], y[b]+dy[i], -1);
	swap(x[a], x[b]), swap(y[a], y[b]);
	swap(mp[x[a]][y[a]], mp[x[b]][y[b]]);
	for(int i=0;i<4;i++) query(x[a]+dx[i], y[a]+dy[i], 1);
	for(int i=0;i<4;i++) query(x[b]+dx[i], y[b]+dy[i], 1);
	return t[1][1];
}

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