Submission #98049

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
98049	2019-02-20T04:19:53 Z	qkxwsm	Segments (IZhO18_segments)	C++14	7 / 100	5000 ms	10104 KB

segments

#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#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>
T randomize(T mod)
{
	return (uniform_int_distribution<T>(0, mod - 1))(rng);
}
template<class T>
void readi(T &x)
{
	x = 0;
	bool negative = false;
	char c = ' ';
	while (c < '-')
	{
		c = getchar();
	}
	if (c == '-')
	{
		negative = true;
		c = getchar();
	}
	while (c >= '0')
	{
		x = x * 10 + (c - '0');
		c = getchar();
	}
	if (negative)
	{
		x = -x;
	}
}
template<class T>
void printi(T output)
{
	if (output == 0)
	{
		putchar('0');
		return;
	}
	if (output < 0)
	{
		putchar('-');
		output = -output;
	}
	int buf[20], n = 0;
	while(output)
	{
		buf[n] = ((output % 10));
		output /= 10;
		n++;
	}
	for (n--; n >= 0; n--)
	{
		putchar(buf[n] + '0');
	}
	return;
}
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>
void 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);
}

#define y0 ___y0
#define y1 ___y1
#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define DBG(x) cerr << #x << " = " << (x) << endl
#define SZ(x) ((int) ((x).size()))
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
#define ALL(x) (x).begin(), (x).end()

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
#define MAXN 200013

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pdd;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<ld> vd;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
typedef vector<pdd> vpd;

int N, Q, T;
int ans;
pii ranges[MAXN];
multiset<pii> upds[2];

int query(int flag, int x, int y)
{
	int res = 0;
	for (pii p : upds[flag])
	{
		if (p.fi <= x && p.se <= y) res++;
	}
	return res;
}

int32_t main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	// cout << fixed << setprecision(10);
	// cerr << fixed << setprecision(10);
	// if (fopen("file.in", "r"))
	// {
	// 	freopen ("file.in", "r", stdin);
	// 	freopen ("file.out", "w", stdout);
	// }
	//0 is by indx, 1 is by size
	cin >> Q >> T;
	while(Q--)
	{
		int qid;
		cin >> qid;
		int lt, rt, k;
		if (qid == 1)
		{
			cin >> lt >> rt;
			if (T)
			{
				lt ^= ans; rt ^= ans;
			}
			if (lt > rt) swap(lt, rt);
			N++;
			ranges[N] = {lt, rt};
			upds[0].insert({lt, rt});
			upds[1].insert({lt, rt - lt + 1});
		}
		if (qid == 2)
		{
			int n;
			cin >> n;
			lt = ranges[n].fi; rt = ranges[n].se;
			upds[0].erase(upds[0].find({lt, rt}));
			upds[1].erase(upds[1].find({lt, rt - lt + 1}));
		}
		if (qid == 3)
		{
			cin >> lt >> rt >> k;
			if (T)
			{
				lt ^= ans; rt ^= ans;
			}
			if (lt > rt) swap(lt, rt);
			if (rt - lt + 1 < k)
			{
				ans = 0;
			}
			else
			{
				ans = query(0, lt - 1, 2 * INF)
				- query(0, lt - 1, lt + k - 2)
				+ query(1, rt - k + 1, 2 * INF)
				- query(1, rt - k + 1, k - 1)
				- query(1, lt - 1, 2 * INF)
				+ query(1, lt - 1, k - 1);
			}
			cout << ans << '\n';
		}
	}
	// cerr << "time elapsed = " << (clock() / (CLOCKS_PER_SEC / 1000)) << " ms" << endl;
	return 0;
}
/* READ READ READ
* int overflow, maxn too small, special cases (n=1?, two distinct?), cin.tie() interactive
* reread the problem, try small cases
* note down possible sources of error as you go
* do smth instead of nothing
*/

Subtask #1

7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	2 ms	384 KB	Output is correct
3	Correct	6 ms	384 KB	Output is correct
4	Correct	3 ms	384 KB	Output is correct
5	Correct	602 ms	824 KB	Output is correct
6	Correct	774 ms	864 KB	Output is correct
7	Correct	58 ms	472 KB	Output is correct
8	Correct	265 ms	760 KB	Output is correct
9	Correct	237 ms	640 KB	Output is correct
10	Correct	141 ms	888 KB	Output is correct
11	Correct	860 ms	784 KB	Output is correct
12	Correct	849 ms	760 KB	Output is correct
13	Correct	187 ms	888 KB	Output is correct
14	Correct	272 ms	652 KB	Output is correct
15	Correct	6 ms	384 KB	Output is correct
16	Correct	9 ms	384 KB	Output is correct
17	Correct	131 ms	544 KB	Output is correct
18	Correct	220 ms	812 KB	Output is correct
19	Correct	134 ms	512 KB	Output is correct
20	Correct	127 ms	632 KB	Output is correct

Subtask #2

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	5024 ms	6648 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #3

0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	241 ms	2660 KB	Output is correct
2	Correct	117 ms	2528 KB	Output is correct
3	Correct	586 ms	2852 KB	Output is correct
4	Correct	128 ms	2552 KB	Output is correct
5	Execution timed out	5090 ms	9464 KB	Time limit exceeded
6	Halted	0 ms	0 KB	-

Subtask #4

0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	121 ms	2800 KB	Output is correct
2	Correct	161 ms	2936 KB	Output is correct
3	Correct	128 ms	2936 KB	Output is correct
4	Correct	167 ms	2808 KB	Output is correct
5	Execution timed out	5017 ms	10104 KB	Time limit exceeded
6	Halted	0 ms	0 KB	-

Subtask #5

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	2 ms	384 KB	Output is correct
3	Correct	6 ms	384 KB	Output is correct
4	Correct	3 ms	384 KB	Output is correct
5	Correct	602 ms	824 KB	Output is correct
6	Correct	774 ms	864 KB	Output is correct
7	Correct	58 ms	472 KB	Output is correct
8	Correct	265 ms	760 KB	Output is correct
9	Correct	237 ms	640 KB	Output is correct
10	Correct	141 ms	888 KB	Output is correct
11	Correct	860 ms	784 KB	Output is correct
12	Correct	849 ms	760 KB	Output is correct
13	Correct	187 ms	888 KB	Output is correct
14	Correct	272 ms	652 KB	Output is correct
15	Correct	6 ms	384 KB	Output is correct
16	Correct	9 ms	384 KB	Output is correct
17	Correct	131 ms	544 KB	Output is correct
18	Correct	220 ms	812 KB	Output is correct
19	Correct	134 ms	512 KB	Output is correct
20	Correct	127 ms	632 KB	Output is correct
21	Execution timed out	5024 ms	6648 KB	Time limit exceeded
22	Halted	0 ms	0 KB	-

Subtask #6

0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	2 ms	384 KB	Output is correct
3	Correct	6 ms	384 KB	Output is correct
4	Correct	3 ms	384 KB	Output is correct
5	Correct	602 ms	824 KB	Output is correct
6	Correct	774 ms	864 KB	Output is correct
7	Correct	58 ms	472 KB	Output is correct
8	Correct	265 ms	760 KB	Output is correct
9	Correct	237 ms	640 KB	Output is correct
10	Correct	141 ms	888 KB	Output is correct
11	Correct	860 ms	784 KB	Output is correct
12	Correct	849 ms	760 KB	Output is correct
13	Correct	187 ms	888 KB	Output is correct
14	Correct	272 ms	652 KB	Output is correct
15	Correct	6 ms	384 KB	Output is correct
16	Correct	9 ms	384 KB	Output is correct
17	Correct	131 ms	544 KB	Output is correct
18	Correct	220 ms	812 KB	Output is correct
19	Correct	134 ms	512 KB	Output is correct
20	Correct	127 ms	632 KB	Output is correct
21	Execution timed out	5024 ms	6648 KB	Time limit exceeded
22	Halted	0 ms	0 KB	-