Submission #707627

#	Time	Username	Problem	Language	Result	Execution time	Memory
707627		AdamGS	Seats (IOI18_seats)	C++17	100 / 100	3385 ms	122808 KiB

seats

#include "seats.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int N=1<<20;
int lst[N], dodaj[2*N], dx[]={1, 0, -1, 0, 0}, dy[]={0, 1, 0, -1, 0}, MA;
pair<int,int>tr[2*N], gdzie[N];
vector<vector<int>>T;
void licz(int v) {
	if(tr[2*v].st<tr[2*v+1].st) tr[v]=tr[2*v];
	else if(tr[2*v].st>tr[2*v+1].st) tr[v]=tr[2*v+1];
	else tr[v]={tr[2*v].st, tr[2*v].nd+tr[2*v+1].nd};
}
void spl(int v) {
	tr[2*v].st+=dodaj[v];
	tr[2*v+1].st+=dodaj[v];
	dodaj[2*v]+=dodaj[v];
	dodaj[2*v+1]+=dodaj[v];
	dodaj[v]=0;
}
void upd(int v, int l, int r, int a, int b, int x) {
	if(b<l || a>r) return;
	if(a<=l && r<=b) {
		tr[v].st+=x;
		dodaj[v]+=x;
		return;
	}
	if(dodaj[v]) spl(v);
	int mid=(l+r)/2;
	upd(2*v, l, mid, a, b, x);
	upd(2*v+1, mid+1, r, a, b, x);
	licz(v);
}
void cnt(int x, int y, int k) {
	if(T[x][y]==MA) return;
	if(lst[T[x][y]]==k) return;
	lst[T[x][y]]=k;
	rep(i, 4) {
		int a=min(T[x+dx[i]][y+dy[i]], T[x+dx[(i+1)%4]][y+dy[(i+1)%4]])-1;
		int b=max(T[x+dx[i]][y+dy[i]], T[x+dx[(i+1)%4]][y+dy[(i+1)%4]]);
		if(T[x][y]<=a) upd(1, 0, N-1, T[x][y], a, k);
		if(b<T[x][y]) upd(1, 0, N-1, b, T[x][y]-1, 10*k);
	}
}
void give_initial_chart(int H, int W, vector<int>R, vector<int>C) {
	MA=H*W;
	rep(i, H+2) {
		vector<int>P(W+2, H*W);
		T.pb(P);
	}
	rep(i, H*W) {
		T[R[i]+1][C[i]+1]=i;
		gdzie[i]={R[i]+1, C[i]+1};
	}
	rep(i, N) tr[N+i]={N, 0};
	rep(i, H*W) tr[N+i]={0, 1};
	for(int i=N-1; i; --i) licz(i);
	rep(i, H) rep(j, W) cnt(i+1, j+1, 1);
}
int swap_seats(int a, int b) {
	rep(i, 5) {
		int x=gdzie[a].st+dx[i], y=gdzie[a].nd+dy[i];
		cnt(x, y, -1);
		x=gdzie[b].st+dx[i]; y=gdzie[b].nd+dy[i];
		cnt(x, y, -1);
	}
	swap(T[gdzie[a].st][gdzie[a].nd], T[gdzie[b].st][gdzie[b].nd]);
	swap(gdzie[a], gdzie[b]);
	rep(i, 5) {
		int x=gdzie[a].st+dx[i], y=gdzie[a].nd+dy[i];
		cnt(x, y, 1);
		x=gdzie[b].st+dx[i]; y=gdzie[b].nd+dy[i];
		cnt(x, y, 1);
	}
	return tr[1].nd;
}

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