Submission #1141550

#	Time	Username	Problem	Language	Result	Execution time	Memory
1141550		Issa	Seats (IOI18_seats)	C++20	100 / 100	2490 ms	103208 KiB

seats

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define ent "\n"

const int maxn = 1e6 + 100;
const ll INF = (ll)1e18 + 100;
const int inf = 1e9 + 100;
const ll MOD = 998244353;
const int maxl = 20;
const ll P = 31;

int n, m, q;
int x[maxn];
int y[maxn];
vector<int> f[maxn];
int d[maxn * 4];
int c[maxn * 4];
int t[maxn * 4];

void build(int v = 1, int tl = 1, int tr = n * m){
    d[v] = 0; c[v] = tr - tl + 1;
    if(tl < tr){
        int mid = (tl + tr) >> 1;
        build(v<<1, tl, mid);
        build(v<<1|1, mid+1, tr);
    }
} void pre(int v, int x){
    d[v] += x;
    t[v] += x;
} void push(int v, int tl, int tr){
    if(tl == tr) return;
    pre(v<<1, t[v]);
    pre(v<<1|1, t[v]);
    t[v] = 0;
} void upd(int l, int r, int x, int v = 1, int tl = 1, int tr = n * m){
    if(tl > r || tr < l) return;
    if(l <= tl && tr <= r) pre(v, x);
    else{
    	push(v, tl, tr);
    	int mid = (tl + tr) >> 1;
    	upd(l, r, x, v<<1, tl, mid);
    	upd(l, r, x, v<<1|1, mid+1, tr);
    	if(d[v<<1] == d[v<<1|1]){
    		d[v] = d[v<<1];
    		c[v] = c[v<<1] + c[v<<1|1];
    	} else{
    		d[v] = min(d[v<<1], d[v<<1|1]);
    		if(d[v<<1] == d[v]) c[v] = c[v<<1];
    		else c[v] = c[v<<1|1];
    	}
    }
} void out(int v = 1, int tl = 1, int tr = n * m){
	push(v, tl, tr);
	if(tl == tr) cout << d[v] << ' ';
	else{
		int mid = (tl + tr) >> 1;
		out(v<<1, tl, mid);
		out(v<<1|1, mid+1, tr);
	}
}

vector<int> v;
void calc(int i, int j, int x){
	v = {f[i][j], f[i+1][j], f[i][j+1], f[i+1][j+1]};
	sort(v.begin(), v.end());
	upd(v[0], v[1] - 1, x);
	upd(v[2], v[3] - 1, x);
} void updCell(int i, int j, int c){
	for(int x = i-1; x <= i; x++){
		for(int y = j-1; y <= j; y++){
			calc(x, y, c);
		}
	}
}

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C){
	n = H, m = W;
	for(int i = 0; i <= n + 1; i++){
        f[i] = vector<int>(m + 2, inf);
    } for(int i = 0; i < n * m; i++){
    	R[i]++; C[i]++;
    	x[i+1] = R[i]; y[i+1] = C[i];
    	f[R[i]][C[i]] = i + 1;
    } build();
    for(int i = 0; i <= n; i++){
    	for(int j = 0; j <= m; j++){
    		calc(i, j, 1);
    	}
    }
}
int swap_seats(int a, int b){
	a++; b++;
	updCell(x[a], y[a], -1);
	f[x[a]][y[a]] = b;
	updCell(x[a], y[a], 1);
	updCell(x[b], y[b], -1);
	f[x[b]][y[b]] = a;
	updCell(x[b], y[b], 1);
	swap(x[a], x[b]); swap(y[a], y[b]);
	return (d[1] == 4) * c[1];
}

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