Submission #415573

#	Time	Username	Problem	Language	Result	Execution time	Memory
415573		LastRonin	Seats (IOI18_seats)	C++14	100 / 100	3065 ms	239888 KiB

seats

#include <bits/stdc++.h>
#include "seats.h"
#define ll long long
#define pb push_back
#define si short int
#define f first
#define s second
#define pill pair<ll, ll>
#define mp make_pair
using namespace std;
const ll N = 4e6 + 1;
const ll big = 1e9;
 
int n;
int h, w;
int R[N],C[N];
int z[N];
int ans[N];
vector<pair<pill, ll>> q[N];

struct seg {
	pair<int,int> t[N];
	int u[N];
	void push(int v, int l, int r) {
		t[v].f += u[v];
		if(l != r)u[v * 2] += u[v], u[v * 2 + 1] += u[v];
		u[v] = 0;
	}
	void build(ll v = 1, ll tl = 1, ll tr = n) {
		if(tl == tr) {
			t[v] = mp(ans[tl], 1);
			return;
		}
		ll m = (tl + tr) >> 1ll;
		build(v * 2, tl, m);
		build(v * 2 + 1, m + 1, tr);
		t[v] = min(t[v * 2], t[v * 2 + 1]);
		if(t[v * 2].f == t[v * 2 + 1].f)
			t[v].s = t[v * 2 + 1].s + t[v * 2].s;
	}
	void upd(ll l, ll r, ll z, ll v = 1, ll tl = 1, ll tr = n) {
		push(v, tl, tr);
		if(l > tr || tl > r)return;
		if(l <= tl && tr <= r)
			return (void)(u[v] += z, push(v, tl, tr));
		ll m = (tl + tr) >> 1ll;
		upd(l, r, z, v * 2, tl, m);
		upd(l, r, z, v * 2 + 1, m + 1, tr);
		t[v] = min(t[v * 2 + 1], t[v * 2]);
		if(t[v * 2 + 1].f == t[v * 2].f)
			t[v].s = t[v * 2 + 1].s + t[v * 2].s;
	}
}  rt;



int get(int x, int y) {
	if(x == 0 || y == 0 || x == h + 1 || y == w)
		return big;
	return z[(x - 1) * w + (y - 1)];
}

void calcfor(ll x, ll y) {
	vector<int> z;
	z.pb(get(x, y)), z.pb(get(x - 1, y - 1));
	z.pb(get(x, y - 1)), z.pb(get(x - 1, y));	
	sort(z.begin(), z.end());
	q[(x - 1) * w + (y - 1)].pb(mp(mp(z[0], min(n, z[1] - 1)), 1));
	if(z[2] != big)
		q[(x - 1) * w + (y - 1)].pb(mp(mp(z[2], min(n, z[3] - 1)), 1222));	
}
 
void give_initial_chart(int H, int W, vector<int> r, vector<int> c) {
    h = H, w = W + 1;
    n = H * W;
    for(int i = 0; i < r.size(); i++)
		R[i] = r[i], C[i] = c[i], R[i]++, C[i]++, z[(R[i] - 1) * w + (C[i] - 1)] = i + 1;
	for(int i = 1; i <= H + 1; i++) {	
		for(int j = 1; j <= w; j++) {
			calcfor(i, j);
			for(auto u : q[(i - 1) * w + (j - 1)])
				ans[u.f.f] += u.s, ans[u.f.s + 1] -= u.s;			
		}
    }
    for(int i = 1; i <= n; i++)
    	ans[i] += ans[i - 1];

	rt.build();		
}
 
int swap_seats(int a, int b) {	
	vector<pill> x;
	x.pb(mp(R[a], C[a])), x.pb(mp(R[b], C[b]));
	x.pb(mp(R[a] + 1, C[a])), x.pb(mp(R[b] + 1, C[b]));
	x.pb(mp(R[a] + 1, C[a] + 1)), x.pb(mp(R[b] + 1, C[b] + 1));
	x.pb(mp(R[a], C[a] + 1)), x.pb(mp(R[b], C[b] + 1));
	sort(x.begin(), x.end());
	x.erase(unique(x.begin(), x.end()), x.end());
	for(auto u : x) {
		for(auto v : q[(u.f - 1) * w + (u.s - 1)])
			rt.upd(v.f.f, v.f.s, -v.s);
		q[(u.f - 1) * w + (u.s - 1)].clear();
	}
	swap(z[(R[a] - 1) * w + (C[a] - 1)], z[(R[b] - 1) * w + (C[b] - 1)]);
	swap(R[a], R[b]), swap(C[a], C[b]);
	for(auto u : x) {
		calcfor(u.f, u.s);
		for(auto v : q[(u.f - 1) * w + (u.s - 1)])
			rt.upd(v.f.f, v.f.s, v.s);
	}	
	rt.push(1, 1, n);
	return rt.t[1].s;
}
/*
int main() {
	int n, m, q;
	cin >> n >> m >> q;
	vector<int> rr, cc;
	for(int i = 1, a, b; i <= n*m; i++)
		cin >> a >> b, rr.pb(a), cc.pb(b);
	give_initial_chart(n, m, rr, cc);
	while(q--) {
		ll a, b;
		cin >> a >> b;
		cout << swap_seats(a, b) << "\n";
	}
} */
   

Compilation message (stderr)

seats.cpp: In function 'void give_initial_chart(int, int, std::vector<int>, std::vector<int>)':
seats.cpp:76:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |     for(int i = 0; i < r.size(); i++)
      |                    ~~^~~~~~~~~~
seats.cpp:85:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   85 |     for(int i = 1; i <= n; i++)
      |     ^~~
seats.cpp:88:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   88 |  rt.build();
      |  ^~

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