oj.uz

Submission #80627

# Submission time Handle Problem Language Result Execution time Memory
80627 2018-10-21T19:34:13 Z qkxwsm Seats (IOI18_seats) C++14
31 / 100
 3798 ms 263168 KB 
#include "seats.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/rope>

using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;

random_device(rd);
mt19937 rng(rd());
const long long FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();

struct custom_hash
{
	template<class T>
	unsigned long long operator()(T v) const
	{
		unsigned long long x = v;
		x += FIXED_RANDOM; x += 11400714819323198485ull;
		x = (x ^ (x >> 30)) * 13787848793156543929ull;
		x = (x ^ (x >> 27)) * 10723151780598845931ull;
		return x ^ (x >> 31);
	}
};

template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T, class U> using hash_table = gp_hash_table<T, U, custom_hash>;

template<class T>
void ckmin(T &a, T b)
{
	a = min(a, b);
}
template<class T>
void ckmax(T &a, T b)
{
	a = max(a, b);
}
long long expo(long long a, long long e, long long mod)
{
	return ((e == 0) ? 1 : ((expo(a * a % mod, e >> 1, mod)) * ((e & 1) ? a : 1) % mod));
}
template<class T, class U>
T nmod(T &x, U mod)
{
	if (x >= mod) x -= mod;
}
template<class T>
T gcd(T a, T b)
{
	return (b ? gcd(b, a % b) : a);
}
template<class T>
T randomize(T mod)
{
	return (uniform_int_distribution<T>(0, mod - 1))(rng);
}

#define y0 ___y0
#define y1 ___y1
#define MP make_pair
#define MT make_tuple
#define PB push_back
#define PF push_front
#define fi first
#define se second
#define debug(x) cerr << #x << " = " << x << endl;
#define sz(x) ((int) (x.size()))

const long double PI = 4.0 * atan(1.0);
const long double EPS = 1e-9;

#define MAGIC 347
#define SINF 10007
#define CO 1000007
#define INF 1000000007
#define BIG 1000000931
#define LARGE 1696969696967ll
#define GIANT 2564008813937411ll
#define LLINF 2696969696969696969ll

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pdd;
typedef pair<pii, pii> ppp;
typedef pair<pii, int> ppi;

int N, M, K;
vector<pii> coor;
vector<vector<int> > grid;

pii operator + (const pii &a, const pii &b)
{
	return {{a.fi + b.fi}, {a.se + b.se}};
}

struct segtree
{
	vector<pii> lazy;
	vector<ppi> stor;
	ppi comb(ppi a, ppi b)
	{
		ppi res = {{0, 0}, 0};
		if (a.fi <= b.fi)
		{
			res.fi = a.fi;
			res.se += a.se;
		}
		if (b.fi <= a.fi)
		{
			res.fi = b.fi;
			res.se += b.se;
		}
		return res;
	}
	void build(int w, int L, int R)
	{
		stor[w] = {{0, 0}, 1};
		lazy[w] = {0, 0};
		if (L == R) return;
		int mid = (L + R) >> 1;
		build(w << 1, L, mid);
		build(w << 1 | 1, mid + 1, R);
		stor[w] = comb(stor[w << 1], stor[w << 1 | 1]);
	}
	void push(int w, int L, int R)
	{
		stor[w].fi = stor[w].fi + lazy[w];
		if (L != R)
		{
			lazy[w << 1] = lazy[w << 1] + lazy[w];
			lazy[w << 1 | 1] = lazy[w << 1 | 1] + lazy[w];
		}
		lazy[w] = {0, 0};
	}
	void update(int w, int L, int R, int a, int b, pii v)
	{
		push(w, L, R);
		if (b < L || R < a) return;
		if (a <= L && R <= b)
		{
			lazy[w] = lazy[w] + v;
			push(w, L, R);
			return;
		}
		int mid = (L + R) >> 1;
		update(w << 1, L, mid, a, b, v);
		update(w << 1 | 1, mid + 1, R, a, b, v);
		stor[w] = comb(stor[w << 1], stor[w << 1 | 1]);
	}
	void upd(int l, int r, pii p)
	{
		ckmin(r, K - 1);
		ckmax(l, 0);
		if (l > r) return;
		update(1, 0, K - 1, l, r, p);
	}
};

segtree seg;

array<int, 4> sort4(int a, int b, int c, int d)
{
	array<int, 4> arra = {a, b, c, d};
	sort(arra.begin(), arra.end());
	return arra;
}

void give_initial_chart(int h, int w, vector<int> R, vector<int> C)
{
	N = h + 2;
	M = w + 2;
	K = w * h;
	grid.resize(N);
	coor.resize(N * M);
	seg.lazy.resize(4 * K);
	seg.stor.resize(4 * K);
	int cc = K;
	for (int i = 0; i < N; i++)
	{
		grid[i].resize(M);
	}
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			if (i == 0 || i == N - 1 || j == 0 || j == M - 1)
			{
				grid[i][j] = cc; cc++;
			}
		}
	}
	for (int i = 0; i < K; i++)
	{
		R[i]++; C[i]++;
		coor[i] = {R[i], C[i]};
		grid[R[i]][C[i]] = i;
	}
	seg.build(1, 0, K - 1);
	for (int i = 0; i < N - 1; i++)
	{
		for (int j = 0; j < M - 1; j++)
		{
			array<int, 4> p = sort4(grid[i][j], grid[i + 1][j], grid[i][j + 1], grid[i + 1][j + 1]);
			seg.upd(p[2], p[3] - 1, {1, 0});
			seg.upd(p[0], p[1] - 1, {0, 1});
		}
	}
}
int swap_seats(int a, int b)
{
	pii p0 = coor[a], p1 = coor[b];
	for (int i = -1; i <= 0; i++)
	{
		for (int j = -1; j <= 0; j++)
		{
			int x = p0.fi + i, y = p0.se + j;
			array<int, 4> p = sort4(grid[x][y], grid[x + 1][y], grid[x][y + 1], grid[x + 1][y + 1]);
			seg.upd(p[2], p[3] - 1, {-1, 0});
			seg.upd(p[0], p[1] - 1, {0, -1});
		}
	}
	for (int i = -1; i <= 0; i++)
	{
		for (int j = -1; j <= 0; j++)
		{
			int x = p1.fi + i, y = p1.se + j;
			array<int, 4> p = sort4(grid[x][y], grid[x + 1][y], grid[x][y + 1], grid[x + 1][y + 1]);
			seg.upd(p[2], p[3] - 1, {-1, 0});
			seg.upd(p[0], p[1] - 1, {0, -1});
		}
	}
	swap(coor[a], coor[b]);
	swap(grid[p0.fi][p0.se], grid[p1.fi][p1.se]);
	for (int i = -1; i <= 0; i++)
	{
		for (int j = -1; j <= 0; j++)
		{
			int x = p0.fi + i, y = p0.se + j;
			array<int, 4> p = sort4(grid[x][y], grid[x + 1][y], grid[x][y + 1], grid[x + 1][y + 1]);
			seg.upd(p[2], p[3] - 1, {1, 0});
			seg.upd(p[0], p[1] - 1, {0, 1});
		}
	}
	for (int i = -1; i <= 0; i++)
	{
		for (int j = -1; j <= 0; j++)
		{
			int x = p1.fi + i, y = p1.se + j;
			array<int, 4> p = sort4(grid[x][y], grid[x + 1][y], grid[x][y + 1], grid[x + 1][y + 1]);
			seg.upd(p[2], p[3] - 1, {1, 0});
			seg.upd(p[0], p[1] - 1, {0, 1});
		}
	}
	seg.push(1, 0, K - 1);
	return seg.stor[1].se;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 504 KB Output is correct
2 Correct 34 ms 508 KB Output is correct
3 Correct 54 ms 600 KB Output is correct
4 Correct 48 ms 788 KB Output is correct
5 Correct 26 ms 788 KB Output is correct
6 Correct 46 ms 788 KB Output is correct
7 Correct 49 ms 788 KB Output is correct
8 Correct 49 ms 788 KB Output is correct
9 Correct 45 ms 788 KB Output is correct
10 Correct 47 ms 788 KB Output is correct
11 Correct 44 ms 788 KB Output is correct
12 Correct 30 ms 788 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 504 KB Output is correct
2 Correct 34 ms 508 KB Output is correct
3 Correct 54 ms 600 KB Output is correct
4 Correct 48 ms 788 KB Output is correct
5 Correct 26 ms 788 KB Output is correct
6 Correct 46 ms 788 KB Output is correct
7 Correct 49 ms 788 KB Output is correct
8 Correct 49 ms 788 KB Output is correct
9 Correct 45 ms 788 KB Output is correct
10 Correct 47 ms 788 KB Output is correct
11 Correct 44 ms 788 KB Output is correct
12 Correct 30 ms 788 KB Output is correct
13 Correct 123 ms 1796 KB Output is correct
14 Correct 163 ms 1896 KB Output is correct
15 Correct 73 ms 1956 KB Output is correct
16 Correct 91 ms 2464 KB Output is correct
17 Correct 99 ms 2464 KB Output is correct
18 Correct 95 ms 2464 KB Output is correct
19 Correct 91 ms 2464 KB Output is correct
20 Correct 78 ms 2464 KB Output is correct
21 Correct 59 ms 2464 KB Output is correct
22 Correct 60 ms 2464 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3537 ms 106596 KB Output is correct
2 Correct 1756 ms 122424 KB Output is correct
3 Correct 1638 ms 138520 KB Output is correct
4 Correct 1381 ms 154300 KB Output is correct
5 Correct 1536 ms 170468 KB Output is correct
6 Correct 1409 ms 186412 KB Output is correct
7 Correct 1530 ms 202268 KB Output is correct
8 Correct 1565 ms 218220 KB Output is correct
9 Correct 1620 ms 234332 KB Output is correct
10 Correct 1636 ms 250204 KB Output is correct

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 250204 KB Output is correct
2 Correct 264 ms 250204 KB Output is correct
3 Correct 1492 ms 250244 KB Output is correct
4 Runtime error 3798 ms 263168 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
5 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Runtime error 66 ms 263168 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 504 KB Output is correct
2 Correct 34 ms 508 KB Output is correct
3 Correct 54 ms 600 KB Output is correct
4 Correct 48 ms 788 KB Output is correct
5 Correct 26 ms 788 KB Output is correct
6 Correct 46 ms 788 KB Output is correct
7 Correct 49 ms 788 KB Output is correct
8 Correct 49 ms 788 KB Output is correct
9 Correct 45 ms 788 KB Output is correct
10 Correct 47 ms 788 KB Output is correct
11 Correct 44 ms 788 KB Output is correct
12 Correct 30 ms 788 KB Output is correct
13 Correct 123 ms 1796 KB Output is correct
14 Correct 163 ms 1896 KB Output is correct
15 Correct 73 ms 1956 KB Output is correct
16 Correct 91 ms 2464 KB Output is correct
17 Correct 99 ms 2464 KB Output is correct
18 Correct 95 ms 2464 KB Output is correct
19 Correct 91 ms 2464 KB Output is correct
20 Correct 78 ms 2464 KB Output is correct
21 Correct 59 ms 2464 KB Output is correct
22 Correct 60 ms 2464 KB Output is correct
23 Correct 3537 ms 106596 KB Output is correct
24 Correct 1756 ms 122424 KB Output is correct
25 Correct 1638 ms 138520 KB Output is correct
26 Correct 1381 ms 154300 KB Output is correct
27 Correct 1536 ms 170468 KB Output is correct
28 Correct 1409 ms 186412 KB Output is correct
29 Correct 1530 ms 202268 KB Output is correct
30 Correct 1565 ms 218220 KB Output is correct
31 Correct 1620 ms 234332 KB Output is correct
32 Correct 1636 ms 250204 KB Output is correct
33 Correct 158 ms 250204 KB Output is correct
34 Correct 264 ms 250204 KB Output is correct
35 Correct 1492 ms 250244 KB Output is correct
36 Runtime error 3798 ms 263168 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
37 Halted 0 ms 0 KB -