Submission #328597

#	Time	Username	Problem	Language	Result	Execution time	Memory
328597		figter001	Seats (IOI18_seats)	C++17	64 / 100	1879 ms	262148 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

vector<vector<int>> loc,at,d;
vector<pair<int,int>> dir = {{0,0},{0,1},{1,0},{1,1}};
vector<vector<int>> X = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,0},{0,1},{1,-1},{1,0},{1,1}};
struct node{
	node *l,*r;
	int lazy,mn,cnt;
	node(){
		l = r = NULL;
		mn = 1e9;
		lazy = 0;
		cnt = 1;
	}

	void pro(){
		mn += lazy;
		if(l != NULL)l->lazy += lazy;
		if(r != NULL)r->lazy += lazy;
		lazy = 0;
	}

	void marge(){
		if(l->mn < r->mn){
			mn = l->mn;
			cnt = l->cnt;
		}else if(r->mn < l->mn){
			mn = r->mn;
			cnt = r->cnt;
		}else if(l->mn == r->mn){
			mn = l->mn;
			cnt = l->cnt + r->cnt;
		}
	}
};

int n;
node *head;

void update(int at,int val,node *&n = head,int s = 1,int e = ::n){
	if(n == NULL)n = new node();
	if(s > at || e < at)return;
	if(s == e){
		n->mn = val;
		n->cnt = 1;
		return;
	}
	update(at , val , n->l , s , (s+e)/2);
	update(at , val , n->r , (s+e)/2+1 , e);
	n->marge();
	// cerr << ' ' << s << ' ' << e << ' ' << n->mn << ' ' << n->cnt << ' ' << val << '\n';
}

void update_range(int l,int r,int val,node *&n = head,int s = 1,int e = ::n){
	n->pro();
	if(s > r || e < l || l > r)return;
	if(s >= l && e <= r){
		n->lazy += val;
		n->pro();
		return;
	}
	update_range(l , r , val , n->l , s , (s+e)/2);
	update_range(l , r , val , n->r , (s+e)/2+1 , e);
	n->marge();
	// cerr << ' ' << s << ' ' << e << ' ' << n->mn << ' ' << n->cnt << ' ' << val << '\n';
}

pair<int,int> get(int l,int r,node *& n = head,int s = 1,int e = ::n){
	n->pro();
	if(n == NULL)return {1e9,0};
	if(s > r || e < l || l > r)return {1e9,0};
	if(s >= l && e <= r)return {n->mn,n->cnt};
	pair<int,int> a = get(l , r , n->l , s , (s+e) / 2);
	pair<int,int> b = get(l , r , n->r , (s+e)/2+1 , e);
	if(a.first < b.first)return a;
	else if(a.first > b.first)return b;
	else{
		return {a.first , a.second + b.second};
	}
}

int h,w;

bool good(int i,int j){
	if(i < 0 || j < 0 || i >= h || j >= w)return false;
	return true;
}

int getd(int i,int j,int x){
	if(!good(i,j) || loc[i][j] > x)return 0;
	return 1;
}

int getv(int a){
	return d[a][3] - d[a][4] + d[a][1] - d[a][2];
}

void add(int l,int r,int v){
	update_range(l,r,v);
}

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
	h = H;w = W;
	n = H*W;
	at = vector<vector<int>>(n);
	d.resize(n,vector<int>(5));
	loc.resize(H,vector<int>(W));
	head = new node();
	for(int i=0;i<n;i++){
		at[i] = {R[i] , C[i]};
		loc[R[i]][C[i]] = i;
	}
	int sum = 0;
	for(int i=0;i<n;i++){

		for(int j=0;j<4;j++){
			int x = at[i][0] + dir[j].first;
			int y = at[i][1] + dir[j].second;
			int w = getd(x-1,y-1,i) + getd(x-1,y,i) + getd(x,y-1,i) + getd(x,y,i);
			d[i][w]++;
		}
		sum += getv(i);
		// cerr << sum << '\n';
		// cerr << i << " : ";
		// for(int j=1;j<=4;j++){
		// 	cerr << d[i][j] << ' ';
		// }
		// cerr << '\n';
		update(i + 1 , sum);
	}
	// cerr << head->mn << ' ' << head->cnt << '\n';
	// cerr << '\n';
	return;
}

int swap_seats(int a, int b) {
	int len = n;
	swap(at[a] , at[b]);
	swap(loc[at[a][0]][at[a][1]] , loc[at[b][0]][at[b][1]]);
	int A = a,B = b;
	// cerr << "MN : " << get(1,len).first << ' ' << get(1,len).second << '\n';
	for(vector<int> i : X){
		// cerr << a << ' ' << b << '\n';
		int ai = at[A][0] + i[0];
		int aj = at[A][1] + i[1];
		if(good(ai,aj)){
			int a = loc[ai][aj];
			add(a+1 , len , -getv(a));
			// cerr << "A : " << a << '\n';
			// cerr << getv(a) << ' ';
			d[a] = {0,0,0,0,0};
			for(int j=0;j<4;j++){
				int x = ai + dir[j].first;
				int y = aj + dir[j].second;
				int w = getd(x-1,y-1,a) + getd(x-1,y,a) + getd(x,y-1,a) + getd(x,y,a);
				d[a][w]++;
			}
			add(a+1 , len , getv(a));
			// cerr << getv(a) << '\n';
			// for(int j=1;j<=4;j++)
			// 	cerr << d[a][j] << ' ';
			// cerr << '\n';
		}
		int bi = at[B][0] + i[0];
		int bj = at[B][1] + i[1];
		if(good(bi,bj)){
			int b = loc[bi][bj];
			add(b+1 , len , -getv(b));
			// cerr << "B : " << b << '\n';
			// cerr << getv(b) << ' ';
			d[b] = {0,0,0,0,0};
			for(int j=0;j<4;j++){
				int x = bi + dir[j].first;
				int y = bj + dir[j].second;
				int w = getd(x-1,y-1,b) + getd(x-1,y,b) + getd(x,y-1,b) + getd(x,y,b);
				d[b][w]++;
			}
			add(b+1 , len , getv(b));
			// cerr << getv(b) << '\n';
			// for(int j=1;j<=4;j++)
			// 	cerr << d[b][j] << ' ';
			// cerr << '\n';
		}
		// cerr << "WTF : " << get(1,len-1).first << ' ' << get(1,len-1).second << '\n';
		// cerr << "mn : " << get(1,len).first << ' ' << get(1,len).second << '\n';
	}
	// cerr << head->mn << ' ' << head->cnt << '\n';
	// cerr << get(len,len).first << '\n';
	return get(1,len).second;
}

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