Submission #1053627

#	Time	Username	Problem	Language	Result	Execution time	Memory
1053627		ReLice	Seats (IOI18_seats)	C++17	100 / 100	539 ms	91984 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
#define ll int
#define pb push_back
#define vll vector<ll>
using namespace std;
const ll N = 1e6+5;
vll r, c;
vll p(N);
ll h, w, n;

struct ST{
	struct node{
		ll mn, cnt, sum;
		
		node(ll mn = 0, ll cnt = 1, ll sum = 0) : mn(mn), cnt(cnt), sum(sum) {}
		
		node operator + (node a){
			node res = node();
			
			res.mn = min(mn, a.mn + sum);
			res.cnt = (mn == res.mn) * cnt + (a.mn + sum == res.mn) * a.cnt;
			res.sum = sum + a.sum;
			
			return res;
		}
	};
	
	node t[N*4];
	
	void upd(ll pos, ll val, ll v, ll tl, ll tr){
		if(tl > pos || tr < pos) return;
		if(tl==tr){
			t[v] = node(val, 1, val);
			return;
		}ll tm=(tl+tr)/2;
		
		upd(pos, val, v * 2, tl, tm);
		upd(pos, val, v * 2 + 1, tm + 1, tr);
		
		t[v] = t[v * 2] + t[v * 2 + 1];
	}
	
	void upd(ll pos, ll val){
		upd(pos, val, 1, 0, n - 1);
	}
	
	ll ans() { return t[1].cnt ; }
	
} t;

ll id(ll x, ll y) {return x * w + y;}

bool ok(ll x, ll y) { return x>=0 && x<h && y>=0 && y<w; }

bool ok(ll x) { return x>=0 && x<n;}

ll f(ll num){
	if(!ok(num)) return -1;
	
	ll x = num / w;
	ll y = num % w;
	
	ll res = 0;
	
	for(auto i : {-1, 0}){
		for(auto j : {-1, 0}){
			ll bl=0;
			
			for(auto a : {0, 1}){
				for(auto b : {0, 1}){
					ll nx = x + i + a;
					ll ny = y + j + b;
					
					if(ok(nx, ny)){
						bl += (p[id(nx, ny)] < p[num]);
					}
				}
			} 
			
			if(bl % 2) res--;
			else res++;
		}
	}
	
	return res;
}

void upd(ll x, ll y){
	if(!ok(x, y)) return;
	
	ll a = id(x, y);
	
	t.upd(p[a], f(a));
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
	r = R, c = C;
	h = H, w = W;
	n = h * w;
	
	for(ll i=0;i<h;i++){
		for(ll j=0;j<w;j++){
			ll x = id(i, j);
			
			p[id(r[x], c[x])] = x;
		}
	}
	
	for(ll i=0;i<n;i++){
		upd(r[i], c[i]);
	}
}
int swap_seats(int a, int b) {
	swap(p[id(r[a], c[a])], p[id(r[b], c[b])]);
	swap(r[a], r[b]);
	swap(c[a], c[b]);
	
	for(auto i : {-1, 0, 1}){
		for(auto j : {-1, 0, 1}){
			upd(r[a] + i, c[a] + j);
			upd(r[b] + i, c[b] + j);
		}
	}
	
	
	
	return t.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