제출 #80317

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
80317		qkxwsm	자리 배치 (IOI18_seats)	C++14	5 / 100	4053 ms	62172 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

struct chash
{
	int operator()(int x) const
	{
		x ^= (x >> 20) ^ (x >> 12);
		return x ^ (x >> 7) ^ (x >> 4);
	}
	int operator()(long long x) const
	{
		return x ^ (x >> 32);
	}
};

template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T, typename U> using hashtable = gp_hash_table<T, U, chash>;

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);
}
template<class T, class U>
T normalize(T x, U mod = 1000000007)
{
	return (((x % mod) + mod) % mod);
}
static long long randomizell(long long mod)
{
	return ((1ll << 45) * rand() + (1ll << 30) * rand() + (1ll << 15) * rand() + rand()) % mod;
}
static int randomize(int mod)
{
	return ((1ll << 15) * rand() + rand()) % mod;
}

#define y0 ___y0
#define y1 ___y1
#define MP make_pair
#define MT make_tuple
#define PB push_back
#define PF push_front
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define debug(x) cerr << #x << " = " << x << endl;

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

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

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

int N, M;
pii pos[MAXN * MAXN * 3];

struct segtree
{
	int los[3 * MAXN * MAXN], his[3 * MAXN * MAXN];
	void update(int w, int L, int R, int a, int v)
	{
		if (a < L || R < a)
		{
			return;
		}
		if (L == R)
		{
			los[w] = v;
			his[w] = v;
			return;
		}
		int mid = (L + R) >> 1;
		update(w << 1, L, mid, a, v);
		update(w << 1 | 1, mid + 1, R, a, v);
		los[w] = min(los[w << 1], los[w << 1 | 1]);
		his[w] = max(his[w << 1], his[w << 1 | 1]);
	}
	pii query(int w, int L, int R, int a, int b)
	{
		if (b < L || R < a)
		{
			return {INF, -INF};
		}
		if (a <= L && R <= b)
		{
			return {los[w], his[w]};
		}
		int mid = (L + R) >> 1;
		pii lt = query(w << 1, L, mid, a, b), rt = query(w << 1 | 1, mid + 1, R, a, b);
		return {min(lt.fi, rt.fi), max(lt.se, rt.se)};
	}
	int bound(int w, int L, int R, pii p, int x)
	{
		//find the first i such that query(0, i) has diff >= x
		if (L == R)
		{
			// cerr << "first time you geq " << x << " is " << L << endl;
			return L;
		}
		int mid = (L + R) >> 1;
		pii c = {min(los[w << 1], p.fi), max(his[w << 1], p.se)};
		// cerr << p.fi << ' ' << p.se << ' ' << c.fi << ' ' << c.se << ' ' << mid << ' ' << x << endl;
		if (c.se - c.fi + 1 >= x)
		{
			return bound(w << 1, L, mid, p, x);
		}
		else
		{
			return bound(w << 1 | 1, mid + 1, R, c, x);
		}
	}
};

segtree xs, ys;

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C)
{
	N = H;
	M = W;
	for (int i = 0; i < N * M; i++)
	{
		pos[i] = {R[i], C[i]};
		xs.update(1, 0, N * M - 1, i, R[i]);
		ys.update(1, 0, N * M - 1, i, C[i]);
	}
}

int solve()
{
	int res = 0;
	// for (int i = 0; i < N * M; i++)
	// {
	// 	pii p = xs.query(1, 0, N * M - 1, 0, i);
	// 	cerr << p.se - p.fi + 1 << ' ';
	// }
	// cerr << endl;
	for (int i = 1; i <= N; i++)
	{
		//last guy that is <= x
		int L = xs.bound(1, 0, N * M - 1, {INF, -INF}, i), R = (i != N ? xs.bound(1, 0, N * M - 1, {INF, -INF}, i + 1) - 1 : N * M - 1);
		pii p = xs.query(1, 0, N * M - 1, 0, L);
		// assert(L > R || p.se - p.fi + 1 == i);
		//L..R, and -1 mod i
		for (int j = (L + 1 + i - 1) / i * i - 1; j <= R; j += i)
		{
			// cerr << "try " << j << endl;
			pii y = ys.query(1, 0, N * M - 1, 0, j);
			int dy = (y.se - y.fi + 1);
			// cerr << dy << endl;
			if (dy * i == (j + 1))
			{
				res++;
				// cerr << "yay " << j << endl;
			}
		}
	}
	return res;
}
int swap_seats(int a, int b)
{
	pii p1 = pos[a], p2 = pos[b];
	swap(pos[a], pos[b]);
	xs.update(1, 0, N * M - 1, a, pos[a].fi);
	ys.update(1, 0, N * M - 1, a, pos[a].se);
	xs.update(1, 0, N * M - 1, b, pos[b].fi);
	ys.update(1, 0, N * M - 1, b, pos[b].se);
	// for (int i = 0; i < N * M; i++)
	// {
	// 	cerr << "point " << i << " at " << xs.query(1, 0, N * M - 1, i, i).fi << ' ' << ys.query(1, 0, N * M - 1, i, i).se << endl;
	// }
	return solve();
}

컴파일 시 표준 에러 (stderr) 메시지

seats.cpp: In function 'int solve()':
seats.cpp:167:7: warning: variable 'p' set but not used [-Wunused-but-set-variable]
   pii p = xs.query(1, 0, N * M - 1, 0, L);
       ^
seats.cpp: In function 'int swap_seats(int, int)':
seats.cpp:187:6: warning: variable 'p1' set but not used [-Wunused-but-set-variable]
  pii p1 = pos[a], p2 = pos[b];
      ^~
seats.cpp:187:19: warning: variable 'p2' set but not used [-Wunused-but-set-variable]
  pii p1 = pos[a], p2 = pos[b];
                   ^~
seats.cpp: At global scope:
seats.cpp:44:12: warning: 'int randomize(int)' defined but not used [-Wunused-function]
 static int randomize(int mod)
            ^~~~~~~~~
seats.cpp:40:18: warning: 'long long int randomizell(long long int)' defined but not used [-Wunused-function]
 static long long randomizell(long long mod)
                  ^~~~~~~~~~~

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