Submission #559226

#	Time	Username	Problem	Language	Result	Execution time	Memory
559226		keta_tsimakuridze	Seats (IOI18_seats)	C++14	70 / 100	4025 ms	190564 KiB

seats

#include "seats.h"
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 2;
#define f first
#define s second
#define pii pair<int,int> 
#define Pii pair<pair<int,int>, int> 
#define mp make_pair
vector<vector<int> > a, f;
int n,h, w, T;
Pii tree[4 * N];
int dx[] = {0, 0, 0, -1, 1};
int dy[] = {0, -1, 1, 0, 0};
pair<int,int> lazy[4 * N], pos[N];
void add(pii &a, pii b) {
	a.f += b.f;
	a.s += b.s;
}
void push(int u,int l,int r) {
	add(tree[u].f, lazy[u]);
	if(l != r) {
		add(lazy[2 * u],lazy[u]);
		add(lazy[2 * u + 1], lazy[u]);
	}
	lazy[u] = {0, 0};
}
void upd(int u, int st, int en, int l,int r, pii v) {
	push(u, l, r);
	if(l > en || r < st) return;
	if(st <= l && r <= en) {
		lazy[u] = v;
		push(u, l, r);
		return;
	}
	int mid = (l + r) / 2;
	upd(2 * u, st, en, l, mid, v); upd(2 * u + 1, st, en, mid + 1, r, v);
	if(tree[2 * u].f != tree[2 * u + 1].f) tree[u] = min(tree[2 * u], tree[2 * u + 1]);
	else tree[u].f = tree[2 * u + 1].f, tree[u].s = tree[2 * u + 1].s + tree[2 * u].s;
}
void build(int u, int l,int r) {
	tree[u].s = r - l + 1;
	if(l == r) return;
	
	build(2 * u, l, (l + r) / 2); build(2 * u + 1, (l + r)/2 + 1, r);
}
void add(int i, int j, int t) {
	if(i > h || j > w || i <= 0 || j <= 0 || f[i][j] == T) return;
	f[i][j] = T;
	int m = max(max(a[i + 1][j], a[i - 1][j]), max(a[i][j + 1], a[i][j - 1]));
	m = max(a[i - 1][j], a[i][j +  1]); upd(1, m ,a[i][j] - 1, 1, n,  mp(0, t));
	m = max(a[i + 1][j], a[i][j + 1]); upd(1, m, a[i][j] - 1, 1, n, mp(0, t));
	m = max(a[i - 1][j], a[i][j - 1]); upd(1, m, a[i][j] - 1, 1, n, mp(0, t));
	m = max(a[i - 1][j], a[i][j + 1]); upd(1, m, a[i][j] - 1, 1, n, mp(0, t));
	
	
	m = min(a[i - 1][j], a[i][j +  1]); upd(1, a[i][j], m - 1, 1, n,  mp(t,0));
	m = min(a[i + 1][j], a[i][j + 1]); upd(1, a[i][j], m - 1, 1, n, mp(t,0));
	m = min(a[i - 1][j], a[i][j - 1]); upd(1, a[i][j], m - 1, 1, n, mp(t,0));
	m = min(a[i - 1][j], a[i][j + 1]); upd(1, a[i][j], m - 1, 1, n, mp(t,0));
 
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
	n = H * W; h = H, w = W;
	a.resize(H + 2, vector<int> (W + 2)); f.resize(H + 2, vector<int> (W + 2));
	build(1, 1, n);
	for(int i = 0; i <= H; i++) {
		a[i][0] = a[i][W + 1] = n + 1;
	}
	for(int i = 0; i <= W; i++) {
		a[0][i] = a[H + 1][i] = n + 1;
	}	
	for(int i = 0; i < H * W; i++) {
		++R[i]; ++C[i];
		a[R[i]][C[i]] = i + 1;
		pos[i + 1] = {R[i], C[i]};
	}
	++T;
	for(int i = 1; i <= H; i++) {
		for(int j = 1; j <= W; j++) { 
			add(i, j, 1);
		} 
	} 
}
 
int swap_seats(int c, int b) {
	
	++c; ++b;
	++T; 
	for(int k = 0; k < 5; k++) {
		add(pos[c].f + dx[k], pos[c].s + dy[k], -1);
		add(pos[b].f + dx[k], pos[b].s + dy[k], -1);		
	}
 
	swap(a[pos[b].f][pos[b].s], a[pos[c].f][pos[c].s]);
	swap(pos[c], pos[b]); 
	pair<pair<int,int>, int> p = tree[1];
	++T;
	for(int k = 0; k < 5; k++) {
		add(pos[c].f + dx[k], pos[c].s + dy[k], 1);
		add(pos[b].f + dx[k], pos[b].s + dy[k], 1);		
	}
	p = tree[1];
	assert(p.f.f >= 4);
	if(p.f.s != 0 || p.f.f != 4) return 0;
	return p.s;
}
/*
namespace {
 
int read_int() {
  int x;
  if (scanf("%d", &x) != 1) {
    fprintf(stderr, "Error while reading input\n");
    exit(1);
  }
  return x;
}
 
}  // namespace
 
int main() {
  int H = read_int();
  int W = read_int();
  int Q = read_int();
  std::vector<int> R(H * W), C(H * W);
  for (int i = 0; i < H * W; ++i) {
    R[i] = read_int();
    C[i] = read_int();
  }
  std::vector<int> A(Q), B(Q);
  for (int j = 0; j < Q; ++j) {
    A[j] = read_int();
    B[j] = read_int();
  }
 
  give_initial_chart(H, W, R, C);
  for (int j = 0; j < Q; ++j) {
    int answer = swap_seats(A[j], B[j]);
    printf("%d\n", answer);
  }
  return 0;
}*/

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