Submission #103268

#	Time	Username	Problem	Language	Result	Execution time	Memory
103268		aviroop123	Seats (IOI18_seats)	C++14	44 / 100	4106 ms	201884 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[4 * N][5];
int tot;
int lz[4 * N];
pii pos[N];
void build(int nd,int s,int e){
	tr[nd][0].fi = 0, tr[nd][0].se = e - s + 1;
	fr(i, 1, 4){
		tr[nd][i].fi = 1e9, tr[nd][i].se = 0;
	}
	if(s == e) return;
	int m = (s + e) >> 1;
	build(nd << 1, s, m);
	build(nd << 1 | 1, m + 1, e);
}
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 push_down(int nd,int s,int e){
	if(!lz[nd]) return;
	fr(i, 0, 4){
		tr[nd][i].fi += lz[nd];
	}
	if(s != e){
		lz[nd << 1] += lz[nd];
		lz[nd << 1 | 1] += lz[nd];
	}
	lz[nd] = 0;
}
map<pii,int> queries;
void upd(int nd,int s,int e,int l,int r,int val){
	push_down(nd, s, e);
	if(s > e || s > r || e < l) return;
	if(l <= s && e <= r){
		lz[nd] += val;
		push_down(nd, s, e);
		return;
	}
	int m = (s + e) >> 1;
	upd(nd << 1, s, m, l, r, val);
	upd(nd << 1 | 1, m + 1, e, l, r, val);
	int pt1 = 0, pt2 = 0;
	int pt = 0;
	int nd1 = nd << 1, nd2 = nd1 | 1;
	while(pt1 < 5 && pt2 < 5 && pt < 5){
		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++;
		}
	}
	while(pt1 < 5 && pt < 5){
		tr[nd][pt++] = tr[nd1][pt1++];
	}
	while(pt2 < 5 && pt < 5){
		tr[nd][pt++] = tr[nd2][pt2++];
	}
}
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++;
	vector<pii> lol;
	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]){ // for 1 wala
		queries[{lol[0].fi, min(lol[1].fi - 1, tot)}] += val;
	}
	if(lol[0].se == lol[1].se && lol[1].se <= tot)
		queries[{lol[1].fi, min(lol[2].fi - 1, tot)}] += 5 * val;
	if(lol[2].fi <= tot) // for 3 wale 
		queries[{lol[2].fi, min(lol[3].fi - 1, tot)}] += 5 * val;
}
void give_initial_chart(int h,int w,vector<int> r,vector<int> c){
	tot = h * w - 1;
	build(1, 0, tot);
	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);
		}
	}
	for(auto it : queries){
		if(it.se){
			upd(1, 0, tot, it.fi.fi, it.fi.se, it.se);
		}
	}
	queries.clear();
}
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);
	}
	for(auto it : queries){
		if(it.se){
			upd(1, 0, tot, it.fi.fi, it.fi.se, it.se);
		}
	}
	queries.clear();
	int ans = 0;
	push_down(1, 0, tot);
	fr(i, 0, 4){
		if(tr[1][i].fi == 1){
			ans = tr[1][i].se;
			break;
		}
	}
	return ans;
}

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