Submission #1046488

#	Time	Username	Problem	Language	Result	Execution time	Memory
1046488		Alihan_8	Seats (IOI18_seats)	C++17	33 / 100	342 ms	127428 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;

const int N = 1e6 + 1;

vector <int> R, C, p;

int h, w;

struct SegTree{
	struct Info{
		int mn, cnt, s;
		
		Info(int mn = 0, int cnt = 1, int s = 0) : mn(mn), cnt(cnt), s(s) {}
	};
	
	Info T[N * 4];
	
	void merge(Info &rt, const Info &lf, const Info &rg){
		rt = Info();
		
		rt.mn = min(lf.mn, rg.mn + lf.s);
		rt.cnt = (lf.mn == rt.mn) * lf.cnt + (rt.mn == rg.mn + lf.s) * rg.cnt;
		rt.s = lf.s + rg.s;
	}
	
	void upd(int v, int l, int r, int p, int x){
		if ( l == r ){
			T[v] = Info(x, 1, x);
		
			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);
		
		merge(T[v], T[v * 2], T[v * 2 + 1]);
	}
	
	void upd(int p, int x){
		upd(1, 0, w - 1, p, x);
	}
	
	int get(int v, int l, int r, int p){
		if ( l == r ) return T[v].mn;
		
		int m = (l + r) / 2;
		
		return p <= m ? get(v * 2, l, m, p) : get(v * 2 + 1, m + 1, r, p);
	}
	
	int get(int p){ return get(1, 0, w - 1, p); } 
	
	int qry(){ return T[1].cnt; } 
} seg;

int f(int u){
	if ( u < 0 || u >= w ) return -3;
	
	int cnt = !u * -2, x = C[u];
	
	cnt += (x == 0 || p[x - 1] > u) ? 1 : -1;
	cnt += (x == w - 1 || p[x + 1] > u) ? 1 : -1;
	
	return cnt;
}

void upd(int j){
	if ( j < 0 || j >= w ) return;
	
	seg.upd(p[j], f(p[j]));
}

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

int swap_seats(int a, int b) {
	swap(C[a], C[b]);
	swap(p[C[a]], p[C[b]]);
	
	assert(p[C[a]] == a);
	
	for ( auto i: {-1, 0, 1} ){
		upd(C[a] + i);
		upd(C[b] + i);
	}
	
	return seg.qry();
}

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