Submission #596995

#	Time	Username	Problem	Language	Result	Execution time	Memory
596995		Lucpp	Seats (IOI18_seats)	C++17	100 / 100	1364 ms	111032 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;

struct Seg{
	vector<pair<int, int>> seg;
	vector<int> lazy;
	int cap;
	pair<int, int> combine(pair<int, int> a, pair<int, int> b){
		if(a > b) swap(a, b);
		if(a.first == b.first) a.second += b.second;
		return a;
	}
	void init(vector<int> v){
		int n = (int)v.size();
		for(int i = 1; i < n; i++) v[i] += v[i-1];
		for(cap = 1; cap < n; cap*=2);
		seg.resize(2*cap, {INF, 1});
		lazy.resize(2*cap, 0);
		for(int i = 0; i < n; i++) seg[i+cap].first = v[i];
		for(int i = cap-1; i >= 1; i--) seg[i] = combine(seg[2*i], seg[2*i+1]);
	}
	void apply(int v, int i){
		seg[i].first += v;
		lazy[i] += v;
	}
	void push(int i){
		apply(lazy[i], 2*i);
		apply(lazy[i], 2*i+1);
		lazy[i] = 0;
	}
	void upd(int l, int r, int v, int a, int b, int i){
		if(l <= a && b <= r) apply(v, i);
		else if(b < l || r < a) return;
		else{
			push(i);
			int m = (a+b)/2;
			upd(l, r, v, a, m, 2*i);
			upd(l, r, v, m+1, b, 2*i+1);
			seg[i] = combine(seg[2*i], seg[2*i+1]);
		}
	}
	void upd(int l, int r, int v){upd(l, r, v, 1, cap, 1);}
};

int n, W, H;
vector<int> r, c;

vector<int> dx = {1, -1, 0, 0}, dy = {0, 0, 1, -1};
vector<vector<int>> num;
vector<int> adj;
Seg seg;

int calc(int x, int y){
	int res = 0;
	for(int i = -1; i < 1; i++){
		for(int j = -1; j < 1; j++){
			int cnt = 0;
			for(int a = 0; a < 2; a++){
				for(int b = 0; b < 2; b++){
					int nx = x+i+a;
					int ny = y+j+b;
					if(num[nx][ny] <= num[x][y]) cnt++;
				}
			}
			if(cnt == 1) res++;
			if(cnt == 2) res--;
			if(cnt == 3) res++;
			if(cnt == 4) res--;
		}
	}
	return res;
}

void upd(int x, int y){
	if(x == 0 || x == H+1 || y == 0 || y == W+1) return;
	int res = calc(x, y);
	seg.upd(num[x][y]+1, n+1, res-adj[num[x][y]]);
	adj[num[x][y]] = res;
}

void give_initial_chart(int h, int w, vector<int> R, vector<int> C) {
	H = h, W = w;
	n = H*W;
	r = R;
	c = C;
	num.assign(H+2, vector<int>(W+2, INF));
	adj.resize(n);
	for(int i = 0; i < n; i++) num[r[i]+1][c[i]+1] = i;
	for(int i = 0; i < n; i++){
		int x = r[i]+1, y = c[i]+1;
		adj[i] = calc(x, y);
	}
	seg.init(adj);
}

int qry = 0;

int swap_seats(int a, int b) {
	qry++;
	if(a > b) swap(a, b);
	swap(r[a], r[b]);
	swap(c[a], c[b]);
	swap(num[r[a]+1][c[a]+1], num[r[b]+1][c[b]+1]);
	for(int i = -1; i <= 1; i++){
		for(int j = -1; j <= 1; j++){
			upd(r[a]+1+i, c[a]+1+j);
			upd(r[b]+1+i, c[b]+1+j);
		}
	}
	int ans = seg.seg[1].second;
	return ans;
}

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