Submission #282259

#	Time	Username	Problem	Language	Result	Execution time	Memory
282259		arnold518	Interval Collection (CCO20_day2problem2)	C++14	25 / 25	3602 ms	386084 KiB

Main

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e6;
const ll INF = 1e15;

int Q;
multiset<ll, greater<ll>> L[MAXN+10], LL;
multiset<ll> R[MAXN+10], RR;

struct Node
{
	ll maxl, minr, val;
	Node() : maxl(-INF), minr(INF), val(INF) {}
};

Node operator + (const Node &p, const Node &q)
{
	Node ret;
	ret.maxl=max(p.maxl, q.maxl);
	ret.minr=min(p.minr, q.minr);
	ret.val=min({p.val, q.val, q.minr-p.maxl});
	return ret;
}

Node tree[MAXN*4+10];

void update(int node, int tl, int tr, int pos)
{
	if(tl==tr)
	{
		tree[node].maxl=*L[tl].begin();
		tree[node].minr=*R[tl].begin();
		tree[node].val=INF;
		return;
	}

	int mid=tl+tr>>1;
	if(pos<=mid) update(node*2, tl, mid, pos);
	else update(node*2+1, mid+1, tr, pos);

	tree[node]=tree[node*2]+tree[node*2+1];
	//printf("%d %d : %lld %lld %lld\n", tl, tr, tree[node].maxl, tree[node].minr, tree[node].val);
}

int main()
{
	scanf("%d", &Q);
	for(int i=1; i<=MAXN; i++)
	{
		L[i].insert(-INF);
		R[i].insert(INF);
	}

	for(int i=1; i<=Q; i++)
	{
		int l, r;
		char c;

		scanf(" %c%d%d", &c, &l, &r);

		if(c=='A')
		{
			L[r-1].insert(l);
			R[l].insert(r);
			LL.insert(l);
			RR.insert(r);
		}
		else
		{
			L[r-1].erase(L[r-1].find(l));
			R[l].erase(R[l].find(r));
			LL.erase(LL.find(l));
			RR.erase(RR.find(r));
		}

		update(1, 1, MAXN, l);
		update(1, 1, MAXN, r-1);

		if(*LL.begin()<=*RR.begin()) printf("%lld\n", *R[*LL.begin()].begin()-*L[*RR.begin()-1].begin());
		else printf("%lld\n", tree[1].val);
	}

}

Compilation message (stderr)

Main.cpp: In function 'void update(int, int, int, int)':
Main.cpp:42:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |  int mid=tl+tr>>1;
      |          ~~^~~
Main.cpp: In function 'int main()':
Main.cpp:52:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   52 |  scanf("%d", &Q);
      |  ~~~~~^~~~~~~~~~
Main.cpp:64:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   64 |   scanf(" %c%d%d", &c, &l, &r);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 3 / 3
• Subtask 2: 8 / 8
• Subtask 3: 7 / 7
• Subtask 4: 4 / 4
• Subtask 5: 3 / 3