Submission #1046407

#	Time	Username	Problem	Language	Result	Execution time	Memory
1046407		Alihan_8	Seats (IOI18_seats)	C++17	25 / 100	4090 ms	103520 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);
}

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){
		return get(1, 0, n - 1, l, r);
	}
};	

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;
	
	while ( k < h * w ){
		auto cur = seg.get(0, k);
		
		if ( f(cur) - 1 == k ){
			ans += 1;
			k += 1;
		} else k = f(cur) - 1;
	}
	
	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: 20 / 20
• Subtask 4: 0 / 6
• Subtask 5: 0 / 33
• Subtask 6: 0 / 30