Submission #93527

#	Time	Username	Problem	Language	Result	Execution time	Memory
93527		psmao	Seats (IOI18_seats)	C++14	100 / 100	2320 ms	198264 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
using namespace std;

#define fo(i,s,t) for(int i = s; i <= t; ++ i)
#define fd(i,s,t) for(int i = s; i >= t; -- i)
#define bf(i,s) for(int i = head[s]; i; i = e[i].next)
#define mp make_pair
#define fi first
#define se second
#define pii pair<int,int>
#define pb push_back
#define VI vector<int>
#define sf scanf
#define pf printf
#define fp freopen
#define SZ(x) ((int)(x).size())
#ifdef MPS
#define D(x...) printf(x)
#else
#define D(x...)
#endif
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
const int inf = 1<<30;
const ll INF = 1ll<<60;
const db Inf = 1e20;
const db eps = 1e-9;

const int maxn = 1000050;
const int dx[] = {0,0,1,1};
const int dy[] = {1,0,0,1};

struct node{int l, r, cnt; pii v, tag;}t[maxn<<2];
int one[maxn], tri[maxn];
int h, w, r[maxn], c[maxn];
vector<vector<int> > A;
VI sur;

void build(int l, int r, int k)
{
	t[k].l = l; t[k].r = r;
	if(l == r)
	{
		t[k].v.fi = one[l];
		t[k].v.se = tri[l];
		t[k].tag = mp(0, 0);
		t[k].cnt = 1;
		return;
	}
	int mid = l + r >> 1;
	build(l, mid, k<<1);
	build(mid+1, r, k<<1|1);
	t[k].v = min(t[k<<1].v, t[k<<1|1].v); t[k].cnt = 0;
	if(t[k<<1].v == t[k].v) t[k].cnt += t[k<<1].cnt;
	if(t[k<<1|1].v == t[k].v) t[k].cnt += t[k<<1|1].cnt;
}
void pd(int k)
{
	t[k<<1].tag.fi += t[k].tag.fi;
	t[k<<1].tag.se += t[k].tag.se;
	t[k<<1].v.fi += t[k].tag.fi;
	t[k<<1].v.se += t[k].tag.se;
	t[k<<1|1].tag.fi += t[k].tag.fi;
	t[k<<1|1].tag.se += t[k].tag.se;
	t[k<<1|1].v.fi += t[k].tag.fi;
	t[k<<1|1].v.se += t[k].tag.se;
	t[k].tag = mp(0, 0);	
}
void modify(int l, int r, pii x, int k)
{
	if(l > r) return;
	if(l <= t[k].l && t[k].r <= r)
	{
		t[k].v.fi += x.fi;
		t[k].v.se += x.se;
		t[k].tag.fi += x.fi;
		t[k].tag.se += x.se;
		return;
	}
	pd(k);
	int mid = t[k].l + t[k].r >> 1;
	if(r <= mid) modify(l, r, x, k<<1);
	else if(l > mid) modify(l, r, x, k<<1|1);
	else modify(l, mid, x, k<<1), modify(mid+1, r, x, k<<1|1);
	t[k].v = min(t[k<<1].v, t[k<<1|1].v); t[k].cnt = 0;
	if(t[k<<1].v == t[k].v) t[k].cnt += t[k<<1].cnt;
	if(t[k<<1|1].v == t[k].v) t[k].cnt += t[k<<1|1].cnt;
}	
void getx(int x, int y)
{
	sur.clear();
	fo(k,0,3) sur.pb(A[x+dx[k]][y+dy[k]]);
	sort(sur.begin(), sur.end());
}
void update(int x, int y, int w)
{
	getx(x, y);
	modify(sur[0], sur[1]-1, mp(w, 0), 1);
	modify(sur[2], sur[3]-1, mp(0, w), 1);
}
void upd(int x, int y, int val)
{
	update(x, y-1, -1);
	update(x-1, y, -1);
	update(x, y, -1);
	update(x-1, y-1, -1);
	A[x][y] = val;
	update(x, y-1, 1);
	update(x-1, y, 1);
	update(x, y, 1);
	update(x-1, y-1, 1);	
}
int ask()
{
	return (t[1].v.fi == 4 && t[1].v.se == 0) ? t[1].cnt : 0;
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) 
{
	int n = R.size();
	h = H; w = W;
	fo(i,0,H+1) 
	{
		vector<int> cur;
		fo(j,0,W+1) cur.pb(H*W+1);
		A.pb(cur);
		cur.clear();
	}
	fo(i,0,n-1) 
	{
		r[i+1] = R[i] + 1; 
		c[i+1] = C[i] + 1;
		A[r[i+1]][c[i+1]] = i+1;
	}
	fo(i,0,H) fo(j,0,W)
	{
		getx(i, j);
		++ one[sur[0]]; -- one[sur[1]];
		++ tri[sur[2]]; -- tri[sur[3]];
	}
	fo(i,1,H*W) one[i] += one[i-1], tri[i] += tri[i-1];
	build(1, H*W, 1); 
}
int swap_seats(int a, int b) 
{
	++ a; ++ b;
	int x = A[r[a]][c[a]], x2 = A[r[b]][c[b]];
	swap(r[a], r[b]);
	swap(c[a], c[b]);
	upd(r[a], c[a], x);
	upd(r[b], c[b], x2);
	return ask();
}

Compilation message (stderr)

seats.cpp: In function 'void build(int, int, int)':
seats.cpp:52:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l + r >> 1;
            ~~^~~
seats.cpp: In function 'void modify(int, int, std::pair<int, int>, int)':
seats.cpp:83:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = t[k].l + t[k].r >> 1;
            ~~~~~~~^~~~~~~~

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