Submission #1128616

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128616		Rainmaker2627	Port Facility (JOI17_port_facility)	C++20	0 / 100	0 ms	320 KiB

port_facility

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

int exp(int a, int b, int mod) {
	int x=1;
	while (b) {
		if (b%2) x=(x*a)%mod;
		a=(a*a)%mod; b/=2;
	} return x;
}

struct node {
	int j, b=1;
	node *nxt=nullptr, *prev=nullptr;
	void init(int _j) { j=_j; }
};

signed main() {
	// cin.tie(0)->sync_with_stdio(false);

	int n;
	cin >> n;
	vector<pair<int, int>> s;
	vector<int> a(n), b(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i] >> b[i];
		s.push_back({a[i], i+1});
		s.push_back({b[i], -i-1});
	} sort(s.begin(), s.end());

	vector<node> c(n);
	vector<int> p(n+1);
	for (auto i = 0, v = 0; i < 2*n; ++i) {
		auto [t, j] = s[i];
		if (j>0) {
			p[j]=v;
			c[v].init(j);
			auto &t=c[v++];
			if (v>1) {
				t.prev=&c[v-2];
				while (t.prev->prev && !t.prev->b) t.prev=t.prev->prev;
			} if (t.prev) { t.prev->nxt=&t; }
		} else {
			auto &t=c[p[j=-j]];
			cout << t.j << ':';
			auto m=t.nxt;
			while (m) {
				cout << m->j << ' ';
				if (m->j==t.j) return 0;
				m=m->nxt;
			} t.b=0;
			if (t.prev) t.prev->nxt=t.nxt;
			if (t.nxt) t.nxt->prev=t.prev;
			cout << '\n';
		}
	}

	// cout << exp(2, uf.cc, 1e9+7) << '\n';
	return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 12
• Subtask 3: 0 / 56
• Subtask 4: 0 / 22