Submission #103341

#	Time	Username	Problem	Language	Result	Execution time	Memory
103341		aviroop123	Seats (IOI18_seats)	C++14	100 / 100	2645 ms	184568 KiB

seats

#include "bits/stdc++.h"
// #include "ext/pb_ds/assoc_container.hpp"
// #include "ext/pb_ds/tree_policy.hpp"
// using namespace __gnu_pbds;
using namespace std;
typedef long long int ll;
// #define int long long 
#define pb push_back
#define fi first
#define se second
#define fr(i, a, b) for(int i = a; i <= b; i++)
#define all(x) x.begin(), x.end()
#define IO ios :: sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define pii pair<int,int>
#define sz(x) (int)x.size()
const int mod = 1e9 + 7;
const int mod1 = 998244353;
typedef long double f80;
#ifndef LOCAL
#pragma GCC optimize ("Ofast")
#define endl '\n'
#endif
 
// template<typename T>
// using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r){
    uniform_int_distribution<int> uid(l, r);
    return uid(rng);
}
ll pwr(ll a,ll b){
	a %= mod;
    int ans = 1;
    while(b){
        if(b & 1) ans = (ans * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return ans;
}
const int N = 1e6 + 5;
pair<int,int> tr[2 * N][2];
int tot;
int d[2 * N];
pii pos[N];
int n, h;
void build1(){
	n = tot + 1;
	h = sizeof(int) * 8 - __builtin_clz(n);
	fr(i, n, 2 * n - 1){
		tr[i][0].fi = 0, tr[i][0].se = 1;
		tr[i][1].fi = 1e9, tr[i][1].se = 0;
	}
	for(int i = n - 1; i > 0; i--){
		tr[i][0].fi = 0, tr[i][0].se = tr[i << 1][0].se + tr[i << 1 | 1][0].se;
		tr[i][1].fi = 1e9, tr[i][1].se = 0;
	}
}
vector<vector<int>> m;
vector<vector<bool>> active;
int dx[4] = {0, 0, -1, -1};
int dy[4] = {0, -1, 0, -1};
int pp[4] = {1, 2, 2, 1};
void apply(int p, int value){
	tr[p][0].fi += value;
	tr[p][1].fi += value;
	if(p < n) d[p] += value;
}
void push(int p){
	for(int s = h; s > 0; --s){
	    int i = p >> s;
	    if (d[i] != 0){
	      	apply(i << 1, d[i]);
	      	apply(i << 1 | 1, d[i]);
	      	d[i] = 0;
	    }
	}
}
void build(int nd) {
  	while(nd > 1){
	  	nd >>= 1;
	  	int pt1 = 0, pt2 = 0, pt = 0;
		int nd1 = nd << 1, nd2 = nd1 | 1;
		while(pt1 < 2 && pt2 < 2 && pt < 2){
			if(tr[nd1][pt1].fi < tr[nd2][pt2].fi){
				tr[nd][pt++] = tr[nd1][pt1++];
			}
			else if(tr[nd1][pt1].fi > tr[nd2][pt2].fi){
				tr[nd][pt++] = tr[nd2][pt2++];
			}
			else{
				tr[nd][pt++] = {tr[nd1][pt1].fi, tr[nd1][pt1].se + tr[nd2][pt2].se};
				pt1++, pt2++;
			}
		}
		tr[nd][0].fi += d[nd];
		tr[nd][1].fi += d[nd];
  	}
}
void inc(int l, int r, int value){
	r++;
	l += n, r += n;
	int l0 = l, r0 = r;
	for(;l < r; l >>= 1, r >>= 1){
		if(l & 1) apply(l++, value);
		if(r & 1) apply(--r, value);
	}
	build(l0);
	build(r0 - 1);
}
vector<pii> lol;
void add_box(int x,int y,int val){
	if(!active[x][y] && val == -1) return;
	if(active[x][y] && val == 1) return;
	active[x][y] = !active[x][y];
	x++, y++;
	fr(i, 0, 3)
		lol.pb({m[x + dx[i]][y + dy[i]], pp[i]});
	sort(all(lol));
	if(lol[0].fi <= tot && lol[0].fi == m[x][y])
		inc(lol[0].fi, min(lol[1].fi - 1, tot), val);
	if(lol[0].se == lol[1].se && lol[1].fi <= tot)
		inc(lol[1].fi, min(lol[3].fi - 1, tot), 2 * val);
	else if(lol[2].fi <= tot)
		inc(lol[2].fi, min(lol[3].fi - 1, tot), 2 * val);
	lol.clear();
}
void give_initial_chart(int h,int w,vector<int> r,vector<int> c){
	tot = h * w - 1;
	build1();
	m.resize(h + 2);
	active.resize(h + 2);
	fr(i, 0, h + 1){
		m[i].resize(w + 2, 1e9);
		active[i].resize(w + 2, 0);
	}
	fr(i, 0, tot){
		pos[i] = {r[i] + 1, c[i] + 1};
		m[r[i] + 1][c[i] + 1] = i;
	}
	for(int i = 0; i <= h; i++){
		for(int j = 0; j <= w; j++){
			add_box(i, j, 1);
		}
	}
}
int swap_seats(int a,int b){
	fr(i, 0, 3){
		add_box(pos[a].fi + dx[i], pos[a].se + dy[i], -1);
		add_box(pos[b].fi + dx[i], pos[b].se + dy[i], -1);
	}
	swap(pos[a], pos[b]);
	m[pos[a].fi][pos[a].se] = a;
	m[pos[b].fi][pos[b].se] = b;
	fr(i, 0, 3){
		add_box(pos[a].fi + dx[i], pos[a].se + dy[i], 1);
		add_box(pos[b].fi + dx[i], pos[b].se + dy[i], 1);
	}
	int ans = 0;
	fr(i, 0, 1){
		if(tr[1][i].fi == 1){
			ans = tr[1][i].se;
			break;
		}
	}
	return ans;
}

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