Submission #536868

#	Time	Username	Problem	Language	Result	Execution time	Memory
536868		akhan42	Tug of War (BOI15_tug)	C++17	23 / 100	21 ms	6488 KiB

tug

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

#define F first
#define S second
#define forn(i, n) for(int i = 0; i < n; ++i)
#define forbn(i, b, n) for(int i = b; i < n; ++i)
#define sz(v) (int)v.size()
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define min3(a, b, c) min(a, min(b, c))
#define lc v << 1
#define rc (v << 1) + 1

typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef long long ll;
typedef complex<double> cd;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

template <class T> inline void mineq(T &a, T b) { a = min(a, b); }
template <class T> inline void maxeq(T &a, T b) { a = max(a, b); }


const int MX = 30 * 1000 + 5;
int l[MX], r[MX], s[MX];
set<int> sp2id[2 * MX];


void solve() {
	int n, k;
	cin >> n >> k;

	forn(i, 2 * n) {
		cin >> l[i] >> r[i] >> s[i];
		l[i]--; r[i]--;
		sp2id[l[i]].insert(i);
		sp2id[r[i] + n].insert(i);
	}

	set<ii> q;

	forn(sp, 2 * n) {
		q.insert({sz(sp2id[sp]), sp});
	}

	while(!q.empty() && q.begin()->F < 2) {
		int ss = q.begin()->F, sp = q.begin()->S;
		if(ss == 0) {
			cout << "NO\n";
			return;
		}
		int i = *sp2id[sp].begin();
		int sp2 = sp == l[i] ? r[i] + n : l[i];

		q.erase({sz(sp2id[sp]), sp});
		q.erase({sz(sp2id[sp2]), sp2});

		sp2id[sp].erase(i);
		sp2id[sp2].erase(i);

		q.insert({sz(sp2id[sp2]), sp2});
	}

	cout << "YES\n";
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

//	freopen("triangles.in", "r", stdin);
//	freopen("triangles.out", "w", stdout);

	int t = 1;
//	cin >> t;
	while(t--) {
		solve();
	}
}

• Subtask 1: 0 / 18
• Subtask 2: 0 / 30
• Subtask 3: 23 / 23
• Subtask 4: 0 / 29