求问
查看原帖
求问
1268478
Depressed_楼主2024/9/15 20:41

RT,这份代码为什么会 TLE?感觉与正解差不多啊。

#include <bits/stdc++.h>

#define FstIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define pb push_back
#define mem(a, v) memset(a, v, sizeof a)
#define pii pair<ll, ll>

using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
 
const ll N = 4e5 + 5, M = 5e2 + 5; 
const ll mod = 1e9 + 7, mod2 = 998244353;
const ld eps = 1e-6;

ll h, w, q;

// R[N], C[N];

// upper : > val
// lower : >= val

signed main()
{
//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);

	FstIO; 
	
	cin >> h >> w >> q;
	vector <set <ll> > R(h + 1), C(w + 1);
	for (ll i = 1; i <= h; ++ i )
	{
		for (ll j = 1; j <= w; ++ j )
		{
			R[i].insert(j);
			C[j].insert(i);
		}
	}
	for (ll _ = 1; _ <= q; ++ _ )
	{
		ll x, y; cin >> x >> y;
		if (R[x].count(y))
		{
			R[x].erase(y);
			C[y].erase(x);
			continue;
		}
		if (R[x].size())
		{
			auto p = upper_bound(R[x].begin(), R[x].end(), y);
//			cout << *p << ' ';
			if (R[x].count(*p)) R[x].erase(*p), C[*p].erase(x);
		}
		if (R[x].size())
		{
			auto p = upper_bound(R[x].begin(), R[x].end(), y);
			-- p;
//			cout << *p << ' ';
			if (R[x].count(*p)) R[x].erase(*p), C[*p].erase(x);
		}
		if (C[y].size())
		{
			auto q = upper_bound(C[y].begin(), C[y].end(), x);
//			cout << *q << ' ';
			if (C[y].count(*q)) C[y].erase(*q), R[*q].erase(y);
		}
		if (C[y].size())
		{
			auto q = upper_bound(C[y].begin(), C[y].end(), x);
			-- q;
//			cout << *q << ' ';
			if (C[y].count(*q)) C[y].erase(*q), R[*q].erase(y);
		}
//		cout << '\n';
		
		
		
	}
	ll s = 0;
	for (ll i = 1; i <= h; ++ i ) s += R[i].size();
	cout << s << '\n';
	
	return 0;
	
	cout.flush();
}
2024/9/15 20:41
加载中...