Submission #145375

#	Time	Username	Problem	Language	Result	Execution time	Memory
145375		kdh9949	Seats (IOI18_seats)	C++17	20 / 100	2522 ms	80684 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;
				else 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 == 1LL * (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]);
	}
}

namespace S5{
	int n, x[N], c[N];
	const int SZ = 1048576;
	struct Seg{
		int d[2*SZ], l[2*SZ], c[2*SZ];
		void spr(int x){
			d[2*x] += l[x];
			d[2*x+1] += l[x];
			l[x] = 0;
		}
		void mrg(int x){
			d[x] = max(d[2*x], d[2*x+1]);
			c[x] = 0;
			if(d[x] == d[2*x]) c[x] += c[2*x];
			if(d[x] == d[2*x+1]) c[x] += c[2*x+1];
		}
		void i(int n){
			for(int i = SZ; i < SZ + n; i++){
				d[i] = SZ - i;
				c[i] = 1;
			}
			for(int i = SZ - 1; i; i--) mrg(i);
		}
		void u(int s, int e, int v, int x = 1, int p = 1, int q = SZ){
			if(e < p || q < s) return;
			if(s <= p && q <= e){
				d[x] += v;
				l[x] += v;
				return;
			}
			spr(x);
			u(s, e, v, 2*x, p, p+q>>1);
			u(s, e, v, 2*x+1, p+q+2>>1, q);
			mrg(x);
		}
	} S;

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

	void ch(int x, int v){
		if(x > 1) S.u(max(c[x - 1], c[x]), n, -1);
		if(x < n) S.u(max(c[x], c[x + 1]), n, -1);
		c[x] = v;
		if(x > 1) S.u(max(c[x - 1], c[x]), n, 1);
		if(x < n) S.u(max(c[x], c[x + 1]), n, 1);
	}

	int swap_seats(int a, int b){ a++; b++;
		swap(x[a], x[b]);
		ch(x[a], a);
		ch(x[b], b);
		return S.c[1];
	}
}

int ST;

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

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

Compilation message (stderr)

seats.cpp: In member function 'void S5::Seg::u(int, int, int, int, int, int)':
seats.cpp:136:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    u(s, e, v, 2*x, p, p+q>>1);
                       ~^~
seats.cpp:137:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    u(s, e, v, 2*x+1, p+q+2>>1, q);
                      ~~~^~

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