Submission #1045723

#	Time	Username	Problem	Language	Result	Execution time	Memory
1045723		Alihan_8	Seats (IOI18_seats)	C++17	5 / 100	4096 ms	86580 KiB

seats

#include "seats.h"

#include <bits/stdc++.h>

using namespace std;

#define ar array

template <class F, class S>
bool chmin(F &u, const S &v){
	bool flag = false;
	
	if ( u > v ){
		u = v; flag |= true;
	}
	
	return flag;
}

template <class F, class S>
bool chmax(F &u, const S &v){
	bool flag = false;
	
	if ( u < v ){
		u = v; flag |= true;
	}
	
	return flag;
}

const int inf = 1e9;

vector <int> R, C;

int h, w;

auto uni(auto a, auto b){
	for ( auto j: {0, 1, 2, 3} ){
		if ( j & 1 ){
			a[j] = max(a[j], b[j]);
		} else a[j] = min(a[j], b[j]);
	}
	
	return a;
}

int f(auto v){
	return (v[1] - v[0] + 1) * (v[3] - v[2] + 1);
}

map <int,ar<int,4>> mp;

struct SegTree{
	vector <ar<int,4>> T;
	
	SegTree(){}
	
	int n;
	
	void modify(int n_){
		n = n_;
		
		T.resize(n * 4 + 5, {inf, -inf, inf, -inf}); // minR, maxR, minC, maxC
	}
	
	void upd(int v, int l, int r, int p, ar <int,2> x){
		if ( l == r ){
			T[v] = {x[0], x[0], x[1], x[1]};
			
			return; 
		}
		
		int m = (l + r) / 2;
		
		if ( p <= m ){
			upd(v * 2, l, m, p, x);
		} else upd(v * 2 + 1, m + 1, r, p, x);
		
		for ( auto j: {0, 1, 2, 3} ){
			if ( j & 1 ){
				T[v][j] = max(T[v * 2][j], T[v * 2 + 1][j]);
			} else{
				T[v][j] = min(T[v * 2][j], T[v * 2 + 1][j]);
			}
		}
	}
	
	void upd(int p, ar <int,2> v){
		upd(1, 0, n - 1, p, v);
	}
	
	auto get(int v, int l, int r, int tl, int tr){
		ar <int,4> ret = {inf, -inf, inf, -inf};
		
		if ( l > tr or r < tl ) return ret;
		
		if ( tl <= l && tr >= r ) return T[v];
		
		int m = (l + r) / 2;
		
		return uni(get(v * 2, l, m, tl, tr), get(v * 2 + 1, m + 1, r, tl, tr));
	}
	
	auto get(int l, int r){
		if ( !mp.count(r) ){
			mp[r] = get(1, 0, n - 1, l, r);
		}
		
		return mp[r];
	}
	
	int qry(int v, int l, int r, int rq, ar <int,4> cur){
		if ( l == r ){
			return l;
		}
		
		int m = (l + r) / 2;
		
		if ( f(uni(T[v * 2], cur)) <= rq ){
			return qry(v * 2 + 1, m + 1, r, rq, uni(T[v * 2], cur));
		}
		
		return qry(v * 2, l, m, rq, cur);
	}
	
	int qry(ar <int,4> cur){
		ar <int,4> tmp = {inf, -inf, inf, -inf};
		
		return qry(1, 0, n - 1, f(cur), tmp);
	}
};	

SegTree seg;

void give_initial_chart(int H, int W, std::vector<int> R_, std::vector<int> C_) {
	h = H, w = W, R = R_, C = C_;
	
	seg.modify(h * w);
	
	for ( int k = 0; k < h * w; k++ ){
		seg.upd(k, {R[k], C[k]});
	}
}

int swap_seats(int a, int b) {
	if ( a > b ) swap(a, b);
	
	swap(R[a], R[b]);
	swap(C[a], C[b]);
	
	seg.upd(a, {R[a], C[a]});
	seg.upd(b, {R[b], C[b]});
	
	int ans = 0, k = 0, rng = 0;
	
	while ( k < h * w ){
		auto cur = seg.get(0, k);
		
		int r = seg.qry(cur);
		
		if ( seg.get(0, r) != cur ) r--;
		
		if ( f(cur) == r + 1 ){
			ans += 1;
		}
		
		k = r + 1;
		
		rng += 1;
	}
	
	assert(rng <= h + w);
	mp.clear();
	
	return ans;
}

Compilation message (stderr)

seats.cpp:37:10: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   37 | auto uni(auto a, auto b){
      |          ^~~~
seats.cpp:37:18: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   37 | auto uni(auto a, auto b){
      |                  ^~~~
seats.cpp:47:7: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   47 | int f(auto v){
      |       ^~~~

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