Submission #145260

#	Time	Username	Problem	Language	Result	Execution time	Memory
145260		kdh9949	Seats (IOI18_seats)	C++17	0 / 100	4067 ms	67080 KiB

seats

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

const int N = 1000005;

namespace S4{
	int n, x[N], y[N], mx[N], Mx[N], my[N], My[N], r;

	void cal(int a[], int m[], int M[], int s, int e){
		for(int i = s; i <= e; i++){
			m[i] = min(m[i - 1], a[i]);
			M[i] = max(M[i - 1], a[i]);
		}
	}

	void ch(int s, int e, int x){
		for(int i = s; i <= e; i++)
			if(1LL * (Mx[i] - mx[i] + 1) * (My[i] - my[i] + 1) == i) r += x;
	}

	void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
		n = H * W;
		for(int i = 0; i < n; i++){
			x[i + 1] = R[i];
			y[i + 1] = C[i];
		}
		mx[0] = my[0] = N;
		cal(x, mx, Mx, 1, n);
		cal(y, my, My, 1, n);
		ch(1, n, 1);
	}

	int swap_seats(int a, int b){ a++; b++;
		if(a > b) swap(a, b);
		swap(x[a], x[b]);
		swap(y[a], y[b]);
		ch(a, b - 1, -1);
		cal(x, mx, Mx, a, b - 1);
		cal(y, my, My, a, b - 1);
		ch(a, b - 1, 1);
		return r;
	}
}

namespace S3{
	int n, x[N], y[N];
	const int SZ = 1048576;
	struct Seg{
		int m[2*SZ], M[2*SZ];
		void i(){
			fill(m, m + 2*SZ, N);
			fill(M, M + 2*SZ, -N);
		}
		void u(int x, int y){
			x += SZ;
			m[x] = M[x] = y;
			for(x /= 2; x; x /= 2){
				m[x] = min(m[2*x], m[2*x+1]);
				M[x] = max(M[2*x], M[2*x+1]);
			}
		}
		int f(int t, int k){
			int x = 1;
			for(; x < SZ; ){
				if(t == 0 && m[2*x] <= k) x = 2*x;
				if(t == 1 && M[2*x] >= k) x = 2*x;
				else x = 2*x+1;
			}
			return x - SZ;
		}
		int ff(int s, int e){
			return min(f(0, s - 1), f(1, e + 1));
		}
	} X, Y;

	void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
		n = H * W;
		X.i();
		Y.i();
		for(int i = 0; i < n; i++){
			x[i + 1] = R[i];
			y[i + 1] = C[i];
			X.u(i + 1, R[i]);
			Y.u(i + 1, C[i]);
		}
	}

	int f(int sx, int ex, int sy, int ey){
		int t = min(X.ff(sx, ex), Y.ff(sy, ey));
		if(t > n) return 1;
		return (t == (ex - sx + 1) * (ey - sy + 1) + 1) +
			   f(min(sx, x[t]), max(ex, x[t]), min(sy, y[t]), max(ey, y[t]));
	}

	int swap_seats(int a, int b){ a++; b++;
		swap(x[a], x[b]);
		swap(y[a], y[b]);
		X.u(a, x[a]); X.u(b, x[b]);
		Y.u(a, y[a]); Y.u(b, y[b]);
		return f(x[1], x[1], y[1], y[1]);
	}
}

int ST;

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
	ST = (H <= 1000 && W <= 1000 ? 3 : 4);
	if(ST == 3) S3::give_initial_chart(H, W, R, C);
	else S4::give_initial_chart(H, W, R, C);
}

int swap_seats(int a, int b){
	if(ST == 3) return S3::swap_seats(a, b);
	return S4::swap_seats(a, b);
}

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