Submission #1115073

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115073		Paz15	Seats (IOI18_seats)	C++17	100 / 100	2274 ms	134984 KiB

seats

//fast
#include<bits/stdc++.h>
#include "seats.h"
using namespace std;
typedef long long ll;
typedef long double ld;

#define rep(n) for(int i = 0 ; i<n ; i++)
#define all(x) x.begin(),x.end()
#define pb push_back

int n,m;
vector<vector<int>> chart;
vector<int> wier;
vector<int> kol;
const int base = (1<<20);
int ile[base*2];
int sum[base*2][2];
int mini[base*2][2];

void print(){
	cout << "   " << ile[1] << '\n';
	cout << "  " << ile[2] << ' ' << ile[3] << " \n";
	cout << ile[4] << ' ' << ile[5] << ' ' << ile[6] << ' ' << ile[7] << '\n';
	cout << "   " << mini[1][0] << '\n';
	cout << "  " << mini[2][0] << ' ' << mini[3][0] << " \n";
	cout << mini[4][0] << ' ' << mini[5][0] << ' ' <<  mini[6][0] << ' ' << mini[7][0] << '\n';
	cout << "   " << mini[1][1] << '\n';
	cout << "  " << mini[2][1] << ' ' << mini[3][1] << " \n";
	cout << mini[4][1] << ' ' << mini[5][1] << ' ' <<  mini[6][1] << ' ' << mini[7][1] << '\n';
	cout << "   " << sum[1][0] << '\n';
	cout << "  " << sum[2][0] << ' ' << sum[3][0] << " \n";
	cout << sum[4][0] << ' ' << sum[5][0] << ' ' <<  sum[6][0] << ' ' << sum[7][0] << '\n';
	cout << "   " << sum[1][1] << '\n';
	cout << "  " << sum[2][1] << ' ' << sum[3][1] << " \n";
	cout << sum[4][1] << ' ' << sum[5][1] << ' ' <<  sum[6][1] << ' ' << sum[7][1] << '\n';
}

void dodaj(int l, int r, int p, int k, int w, int c, bool xd){
	if (r<p || k<l) return;
	if (p<=l && r<=k){
		mini[w][xd]+=c;
		sum[w][xd]+=c;
		return;
	}
	dodaj(l,(l+r)/2,p,k,w*2,c,xd);
	dodaj((l+r)/2+1,r,p,k,w*2+1,c,xd);
	if (mini[w*2][0]<mini[w*2+1][0]){
		mini[w][0] = mini[w*2][0];
		mini[w][1] = mini[w*2][1];
		ile[w] = ile[w*2];
	}else if (mini[w*2][0]>mini[w*2+1][0]){
		mini[w][0] = mini[w*2+1][0];
		mini[w][1] = mini[w*2+1][1];
		ile[w] = ile[w*2+1];
	}else{
		if (mini[w*2][1]<mini[w*2+1][1]){
			mini[w][0] = mini[w*2][0];
			mini[w][1] = mini[w*2][1];
			ile[w] = ile[w*2];
		}else if (mini[w*2][1]>mini[w*2+1][1]){
			mini[w][0] = mini[w*2+1][0];
			mini[w][1] = mini[w*2+1][1];
			ile[w] = ile[w*2+1];
		}else{
			mini[w][0] = mini[w*2][0];
			mini[w][1] = mini[w*2][1];
			ile[w] = ile[w*2+1]+ile[w*2];
		}
	}
	mini[w][0]+=sum[w][0];
	mini[w][1]+=sum[w][1];
}

void smallsort(vector<int> &v){
	if (v[1]<v[0]) swap(v[0],v[1]);
	if (v[3]<v[2]) swap(v[2],v[3]);
	if (v[2]<v[0]) swap(v[0],v[2]);
	if (v[2]<v[1]) swap(v[1],v[2]);
	if (v[3]<v[1]) swap(v[1],v[3]);
	if (v[3]<v[2]) swap(v[2],v[3]);
}

void give_initial_chart(int h, int w, vector<int> r, vector<int> c){
	for (int i = base ; i<base*2 ; i++) ile[i] = 1;
	for (int i = 19 ; i>=0 ; i--){
		for (int j = (1<<i) ; j<(1<<(i+1)) ; j++){
			ile[j] = ile[j*2]+ile[j*2+1];
		}
	}
	n = h;
	m = w;
	wier = r;
	kol = c;
	chart.resize(n+2);
	rep(h+2){
		chart[i].resize(m+2);
	}
	for (int i = 0 ; i<n*m ; i++){
		chart[r[i]+1][c[i]+1] = i;
		wier[i]++;
		kol[i]++;
	}
	for (int i = 0 ; i<m+2 ; i++){
		chart[0][i] = base;
		chart[n+1][i] = base;
	}
	for (int i = 0 ; i<n+2 ; i++){
		chart[i][0] = base;
		chart[i][m+1] = base;
	}
	for (int i = 0 ; i<=n ; i++){
		for (int j = 0 ; j<=m ; j++){
			vector<int> v = {chart[i][j],chart[i+1][j],chart[i][j+1],chart[i+1][j+1]};
			smallsort(v);
			dodaj(0,base-1,v[0],v[1]-1,1,1,0);
			if (v[2]>(n*m)) continue;
			dodaj(0,base-1,v[2],v[3]-1,1,1,1);
		}
	}
}

int swap_seats(int a, int b){
	for (int i = wier[a]-1 ; i<=wier[a] ; i++){
		for (int j = kol[a]-1 ; j<=kol[a] ; j++){
			vector<int> v = {chart[i][j],chart[i+1][j],chart[i][j+1],chart[i+1][j+1]};
			smallsort(v);
			dodaj(0,base-1,v[0],v[1]-1,1,-1,0);
			if (v[2]>(n*m)) continue;
			dodaj(0,base-1,v[2],v[3]-1,1,-1,1);
		}
	}
	for (int i = wier[b]-1 ; i<=wier[b] ; i++){
		for (int j = kol[b]-1 ; j<=kol[b] ; j++){
			vector<int> v = {chart[i][j],chart[i+1][j],chart[i][j+1],chart[i+1][j+1]};
			smallsort(v);
			dodaj(0,base-1,v[0],v[1]-1,1,-1,0);
			if (v[2]>(n*m)) continue;
			dodaj(0,base-1,v[2],v[3]-1,1,-1,1);
		}
	}
	swap(chart[wier[a]][kol[a]],chart[wier[b]][kol[b]]);
	swap(wier[a],wier[b]);
	swap(kol[a],kol[b]);
	for (int i = wier[a]-1 ; i<=wier[a] ; i++){
		for (int j = kol[a]-1 ; j<=kol[a] ; j++){
			vector<int> v = {chart[i][j],chart[i+1][j],chart[i][j+1],chart[i+1][j+1]};
			smallsort(v);
			dodaj(0,base-1,v[0],v[1]-1,1,1,0);
			if (v[2]>(n*m)) continue;
			dodaj(0,base-1,v[2],v[3]-1,1,1,1);
		}
	}
	for (int i = wier[b]-1 ; i<=wier[b] ; i++){
		for (int j = kol[b]-1 ; j<=kol[b] ; j++){
			vector<int> v = {chart[i][j],chart[i+1][j],chart[i][j+1],chart[i+1][j+1]};
			smallsort(v);
			dodaj(0,base-1,v[0],v[1]-1,1,1,0);
			if (v[2]>(n*m)) continue;
			dodaj(0,base-1,v[2],v[3]-1,1,1,1);
		}
	}
	return (n*m)-base+ile[1];
}

/*int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int h,w,q;
	cin >> h >> w >> q;
	vector<int> r(h*w);
	vector<int> c(h*w);
	rep(h*w){
		cin >> r[i] >> c[i];
	}
	give_initial_chart(h,w,r,c);
	rep(q){
		int a,b;
		cin >> a >> b;
		cout << swap_seats(a,b) << '\n';
	}
}*/

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