Submission #267071

#	Time	Username	Problem	Language	Result	Execution time	Memory
267071		ChrisT	Interval Collection (CCO20_day2problem2)	C++17	25 / 25	3731 ms	294796 KiB

Main

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using pli = pair<ll,int>;
using ld = long double;
#define all(x) (x).begin(),(x).end()
const int MN = 5e5 + 5, MOD = 1e9 + 7, BASE = 131;
pii inter[MN];
map<int,vector<int>> ou[MN<<1];
struct Seg {
	int t,t2,l,r,push;
};
int ans[MN]; pii isect[MN];
void cdq (int l, int r, vector<Seg> &lsrt, vector<Seg> &rsrt, int push, pii inter) {
	int mid = (l+r)/2;
	vector<Seg> lq,rq,llq,rrq;
	int pp = 0, sz = rsrt.size(), mxl = -1e9;
	for (Seg &s : lsrt) {
		while (pp<sz&&rsrt[pp].r<=s.l) {
			if (rsrt[pp].t <= l && r <= rsrt[pp].t2) mxl = max(mxl,rsrt[pp].l);
			++pp;
		}
		if (s.t <= l && r <= s.t2) {
			inter.first = max(inter.first,s.l); inter.second = min(inter.second,s.r);
			push = min(push,s.r - mxl);
			push = min(push,s.push);
		} else {
			s.push = min(s.push,s.r - mxl);
			if (s.t <= mid) lq.push_back(s);
			if (s.t2 > mid) rq.push_back(s);
		}
	}
	pp = sz - 1; int mnr = 1e9;
	for (int idx = sz-1;~idx;idx--) {
		Seg &s = rsrt[idx];
		while (pp && lsrt[pp].l >= s.r) {
			if (lsrt[pp].t <= l && r <= lsrt[pp].t2) mnr = min(mnr,lsrt[pp].r);
			--pp;
		}
		if (s.t <= l && r <= s.t2) {
			push = min(push,mnr-s.l);
			push = min(push,s.push);
		} else {
			s.push = min(s.push,mnr-s.l);
			if (s.t <= mid) llq.push_back(s);
			if (s.t2 > mid) rrq.push_back(s);
		}
	}
	reverse(all(llq)); reverse(all(rrq));
	if (l == r) ans[l] = push, isect[l] = inter; 
	else cdq(l,mid,lq,llq,push,inter), cdq(mid+1,r,rq,rrq,push,inter);
}
multiset<int> rs[MN<<1], ls[MN<<1];
struct Event {
	int l,r,add;
};
int main () {
	int q;
	scanf ("%d",&q);
	vector<Seg> segs; vector<Event> events;
	for (int i = 1; i <= q; i++) {
		char c; int l,r;
		scanf (" %c %d %d",&c,&l,&r);
		events.push_back({l,r,c=='A'});
		if (c == 'A') ou[l][r].push_back(i);
		else {
			segs.push_back({ou[l][r].back(),i-1,l,r,MOD});
			ou[l][r].pop_back();
		}
	}
	for (int l = 1; l < (MN<<1); l++) {
		for (auto &au : ou[l]) {
			for (auto &t : au.second) {
				segs.push_back({t,q,l,au.first,MOD});
			}
		}
	}
	sort(all(segs),[](const Seg &a, const Seg &b){return a.l<b.l;});
	vector<Seg> rsrt(all(segs));
	sort(all(rsrt),[](const Seg &a, const Seg &b){return a.r<b.r;});
	cdq(1,q,segs,rsrt,1e9,pii{-1e9,1e9});
	for (int i = 1; i <= q; i++) {
		Event &cur = events[i-1];
		if (cur.add) ls[cur.r].insert(cur.l), rs[cur.l].insert(cur.r);
		else ls[cur.r].erase(ls[cur.r].find(cur.l)), rs[cur.l].erase(rs[cur.l].find(cur.r));
		if (ans[i] > 2e6) {
			assert(isect[i].second > isect[i].first);
			ans[i] = *rs[isect[i].first].begin() - *ls[isect[i].second].rbegin();
		}
		printf ("%d\n",ans[i]);
	} 
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:61:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   61 |  scanf ("%d",&q);
      |  ~~~~~~^~~~~~~~~
Main.cpp:65:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   65 |   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