Submission #290502

#	Time	Username	Problem	Language	Result	Execution time	Memory
290502		luciocf	Segments (IZhO18_segments)	C++14	23 / 100	269 ms	9976 KiB

segments

#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 (stderr)

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 / 7
• Subtask 2: 0 / 15
• Subtask 3: 16 / 16
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20
• Subtask 6: 0 / 25