oj.uz

Submission #290502

# Submission time Handle Problem Language Result Execution time Memory
290502 2020-09-03T22:40:54 Z luciocf Segments (IZhO18_segments) C++14
23 / 100
 269 ms 9976 KB 
#include <bits/stdc++.h>

#define ff first
#define ss second

using namespace std;

typedef pair<int, int> pii;

const int maxn = 2e5+10;
const int maxv = 2e9+10;

struct Node
{
    int v, w, sz;
    Node *l, *r;

    Node(int vv)
    {
        v = vv, sz = 1, w = rand();
        l = r = NULL;
    }
};

typedef Node*& Node_t;

Node *root[2];

struct Treap
{
	int sz(Node *t) {return (t ? t->sz : 0);}

	void op(Node *t)
	{
	    if (t) t->sz = sz(t->l) + sz(t->r) + 1;
	}

	void split(Node *t, Node_t l, Node_t r, int v)
	{
	    if (!t) return void(l=r=NULL);

	    if (t->v > v) split(t->l, l, t->l, v), r = t;
	    else split(t->r, t->r, r, v), l = t;

	    op(t);
	}

	void merge(Node_t t, Node *l, Node *r)
	{
	    if (!l || !r) t = (l ? l : r);
	    else if (l->w > r->w) merge(l->r, l->r, r), t = l;
	    else merge(r->l, l, r->l), t = r;

	    op(t);
	}

	void insert(Node_t t, int v)
	{
		Node *aux = new Node(v);
		Node *t1, *t2;

		split(t, t1, t2, v);
		merge(t1, t1, aux);
		merge(t, t1, t2);

		op(t);
	}

	void erase(Node_t t, int v)
	{
	    if (t->v == v) merge(t, t->l, t->r);
	    else erase((v > t->v ? t->r : t->l), v);

	    op(t);
	}

	int get_menor(Node *t, int v)
	{
		if (!t) return 0;

		if (t->v >= v) return get_menor(t->l, v);
		return sz(t->l)+1+get_menor(t->r, v);
	}

	int get_maior(Node *t, int v)
	{
		if (!t) return 0;

		if (t->v <= v) return get_maior(t->r, v);
		return sz(t->r)+1+get_maior(t->l, v);
	}
} T;

pii range[maxn];

int intersect(pii a, pii b)
{
	if (a.ff > b.ss || a.ss < b.ff) return 0;

	if (a.ff >= b.ff && a.ss <= b.ss) return a.ss-a.ff+1;

	if (a.ff >= b.ff) return b.ss-a.ff+1;

	return a.ss-b.ff+1;
}

int q, t;

void solve_1(void)
{
	int lastans = 0;
	int ind = 0;

	multiset<pii> st;

	while (q--)
	{	
		int op;
		scanf("%d", &op);

		if (op == 1)
		{
			int l, r;
			scanf("%d %d", &l, &r);

			l = (l ^ (t*lastans));
			r = (r ^ (t*lastans));
			if (l > r) swap(l, r);

			range[++ind] = {l, r};

			st.insert(range[ind]);
		}
		else if (op == 2)
		{
			int x;
			scanf("%d", &x);

			st.erase(st.find(range[x]));
		}
		else
		{
			int l, r, k;
			scanf("%d %d %d", &l, &r, &k);

			l = (l ^ (t*lastans));
			r = (r ^ (t*lastans));
			if (l > r) swap(l, r);

			lastans = 0;

			for (auto pp: st)
				if (intersect(pp, {l, r}) >= k)
					lastans++;

			printf("%d\n", lastans);
		}
	}
}

int main(void)
{
	scanf("%d %d", &q, &t);

	if (q <= 5000)
	{
		solve_1();
		return 0;
	}

	int lastans = 0;
	int ind = 0, qtd_ativo = 0;

	root[0] = root[1] = NULL;

	while (q--)
	{	
		int op;
		scanf("%d", &op);

		if (op == 1)
		{
			int l, r;
			scanf("%d %d", &l, &r);

			l = (l ^ (t*lastans));
			r = (r ^ (t*lastans));
			if (l > r) swap(l, r);

			range[++ind] = {l, r};
			++qtd_ativo;

			T.insert(root[0], l);
			T.insert(root[1], r);
		}
		else if (op == 2)
		{
			int x;
			scanf("%d", &x);

			--qtd_ativo;

			T.erase(root[0], range[x].ff);
			T.erase(root[1], range[x].ss);
		}
		else
		{
			int l, r, k;
			scanf("%d %d %d", &l, &r, &k);

			l = (l ^ (t*lastans));
			r = (r ^ (t*lastans));
			if (l > r) swap(l, r);

			lastans = qtd_ativo - T.get_menor(root[1], l) - T.get_maior(root[0], r);
			printf("%d\n", lastans);
		}
	}
}

Compilation message

segments.cpp: In function 'void solve_1()':
segments.cpp:119:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  119 |   scanf("%d", &op);
      |   ~~~~~^~~~~~~~~~~
segments.cpp:124:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  124 |    scanf("%d %d", &l, &r);
      |    ~~~~~^~~~~~~~~~~~~~~~~
segments.cpp:137:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  137 |    scanf("%d", &x);
      |    ~~~~~^~~~~~~~~~
segments.cpp:144:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  144 |    scanf("%d %d %d", &l, &r, &k);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
segments.cpp: In function 'int main()':
segments.cpp:163:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  163 |  scanf("%d %d", &q, &t);
      |  ~~~~~^~~~~~~~~~~~~~~~~
segments.cpp:179:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  179 |   scanf("%d", &op);
      |   ~~~~~^~~~~~~~~~~
segments.cpp:184:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  184 |    scanf("%d %d", &l, &r);
      |    ~~~~~^~~~~~~~~~~~~~~~~
segments.cpp:199:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  199 |    scanf("%d", &x);
      |    ~~~~~^~~~~~~~~~
segments.cpp:209:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  209 |    scanf("%d %d %d", &l, &r, &k);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 72 ms 512 KB Output is correct
6 Correct 83 ms 632 KB Output is correct
7 Correct 18 ms 384 KB Output is correct
8 Correct 38 ms 512 KB Output is correct
9 Correct 40 ms 512 KB Output is correct
10 Correct 19 ms 512 KB Output is correct
11 Correct 110 ms 536 KB Output is correct
12 Correct 109 ms 504 KB Output is correct
13 Correct 22 ms 672 KB Output is correct
14 Correct 38 ms 512 KB Output is correct
15 Correct 4 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 29 ms 384 KB Output is correct
18 Correct 27 ms 512 KB Output is correct
19 Correct 31 ms 384 KB Output is correct
20 Correct 33 ms 512 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 195 ms 5752 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 3808 KB Output is correct
2 Correct 85 ms 3832 KB Output is correct
3 Correct 99 ms 3836 KB Output is correct
4 Correct 81 ms 3960 KB Output is correct
5 Correct 227 ms 7800 KB Output is correct
6 Correct 210 ms 6688 KB Output is correct
7 Correct 221 ms 7152 KB Output is correct
8 Correct 269 ms 9976 KB Output is correct
9 Correct 267 ms 9848 KB Output is correct
10 Correct 233 ms 8184 KB Output is correct
11 Correct 122 ms 4088 KB Output is correct
12 Correct 243 ms 8312 KB Output is correct
13 Correct 228 ms 7676 KB Output is correct
14 Correct 176 ms 5752 KB Output is correct
15 Correct 169 ms 5496 KB Output is correct
16 Correct 164 ms 4984 KB Output is correct
17 Correct 220 ms 5752 KB Output is correct
18 Correct 186 ms 5752 KB Output is correct
19 Correct 188 ms 5752 KB Output is correct
20 Correct 183 ms 5752 KB Output is correct
21 Correct 130 ms 4216 KB Output is correct
22 Correct 196 ms 6264 KB Output is correct
23 Correct 208 ms 7032 KB Output is correct
24 Correct 193 ms 6392 KB Output is correct
25 Correct 90 ms 3960 KB Output is correct
26 Correct 81 ms 3832 KB Output is correct
27 Correct 90 ms 3832 KB Output is correct
28 Correct 84 ms 3832 KB Output is correct
29 Correct 225 ms 7416 KB Output is correct
30 Correct 232 ms 7416 KB Output is correct
31 Correct 262 ms 9876 KB Output is correct
32 Correct 246 ms 8316 KB Output is correct
33 Correct 217 ms 7792 KB Output is correct
34 Correct 170 ms 5624 KB Output is correct
35 Correct 203 ms 7024 KB Output is correct
36 Correct 235 ms 8184 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 85 ms 3832 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 72 ms 512 KB Output is correct
6 Correct 83 ms 632 KB Output is correct
7 Correct 18 ms 384 KB Output is correct
8 Correct 38 ms 512 KB Output is correct
9 Correct 40 ms 512 KB Output is correct
10 Correct 19 ms 512 KB Output is correct
11 Correct 110 ms 536 KB Output is correct
12 Correct 109 ms 504 KB Output is correct
13 Correct 22 ms 672 KB Output is correct
14 Correct 38 ms 512 KB Output is correct
15 Correct 4 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 29 ms 384 KB Output is correct
18 Correct 27 ms 512 KB Output is correct
19 Correct 31 ms 384 KB Output is correct
20 Correct 33 ms 512 KB Output is correct
21 Incorrect 195 ms 5752 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 72 ms 512 KB Output is correct
6 Correct 83 ms 632 KB Output is correct
7 Correct 18 ms 384 KB Output is correct
8 Correct 38 ms 512 KB Output is correct
9 Correct 40 ms 512 KB Output is correct
10 Correct 19 ms 512 KB Output is correct
11 Correct 110 ms 536 KB Output is correct
12 Correct 109 ms 504 KB Output is correct
13 Correct 22 ms 672 KB Output is correct
14 Correct 38 ms 512 KB Output is correct
15 Correct 4 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 29 ms 384 KB Output is correct
18 Correct 27 ms 512 KB Output is correct
19 Correct 31 ms 384 KB Output is correct
20 Correct 33 ms 512 KB Output is correct
21 Incorrect 195 ms 5752 KB Output isn't correct
22 Halted 0 ms 0 KB -