越调越TLE求调
查看原帖
越调越TLE求调
589961
steambird楼主2024/10/11 20:12
#include <bits/stdc++.h>
using namespace std;

inline int maxi(int a, int b) {
	return a > b ? a : b;
}

int T,n,m,h,farthest_x;
constexpr int N = 1e5+4, INF = 1e9+3e8;
constexpr int MININF = -INF;
struct coord {
	int x,y;
	bool adds;
	coord() {
		
	}
	coord(int x, int y, bool adds) : x(x), y(y), adds(adds) {
		
	}
};
coord mirror[N], coin[N];
unordered_map<int, vector<int> > climbings, descendings;
unordered_map<int, vector<int> > climbing_mirror, descending_mirror;
unordered_map<int, vector<int> > refs;
// Use x-y for climbing, x+y for descending
//int dp[N];
set<pair<int, int> > mirrors, coins;
map<pair<int, int>, int> dp;
map<coord, int> memory;
// I guess SQRT-Divide-and-conquer is needed? (In order to preprocess all continuous "V"-shape lines)
bool operator < (const coord &a, const coord &b) {
	if (a.x == b.x && a.y == b.y) return (a.adds ? '1' : '0') < (b.adds ? '1' : 0);
	if (a.x == b.x) return a.y < b.y;
	return a.x < b.x;
}
// Predict position at time cost approx. O(1). Returning (x,y).
coord predict_position(int x, int y, bool direction, int distance) {
//	cerr << "Evaluate " << x << "," << y << ":" << direction << " jumping for " << distance << endl;
	if (direction) {
		int htop = (h-y);
		if (htop >= distance) return coord(x-distance, y+distance, direction);
		distance -= htop;
		int gsize = distance / h, gfeat = distance % h;
		if (gsize&1) {
			// Still 1
			return coord(x-distance-htop, gfeat, true);
		} else {
			// Direction 0
			return coord(x-distance-htop, h-gfeat, false);
		}
	} else {
		if (y >= distance) return coord(x-distance, y-distance, direction);
		distance -= y;
		int gsize = distance / h, gfeat = distance % h;
		if (gsize&1) {
			return coord(x-distance-y, h-gfeat, false);
		} else {
			return coord(x-distance-y, gfeat, true);
		}
	}
} 
inline int fetch_xs(int x, int y) {
	auto& finder_in = refs[(x+y)%(h<<1)];
	auto finder = lower_bound(finder_in.begin(), finder_in.end(), x);
	int xs = 0;
	if (finder != finder_in.begin()) {
		finder--;
		xs = (*finder);
	}
	auto& finder_in2 = refs[(x-y)%(h<<1)];
	auto finder2 = lower_bound(finder_in2.begin(), finder_in2.end(), x);
	if (finder2 != finder_in2.begin()) {
		finder2--;
		xs = maxi(xs, (*finder2));
	}
	return xs;
}
// Returning source & total coin on the way
// Originally descending (will be climbing) - direction = 1
//						--will be descending - direction = 0
int predict(int x, int y, bool direction) {
	if (x < 0 || y < 0) return -INF;
	if (x == 0) {
		if (y != 0) return -INF;
		else return 0;
	}
	coord cs = coord(x, y, direction);
	auto cdp = make_pair(x, y);
	if (dp.count(cdp)) {
//		cerr << x << "," << y << " is a mirror, answer is " << dp[cdp] << endl;
		return memory[cs] = dp[cdp];
	}
	auto mf = memory.find(cs);
//	cerr << "Seeking " << x << "," << y << " with direction " << direction << endl;
	if (mf != memory.end()) {
//		cerr << "Existing value " << x << "," << y << ":" << direction << " = " << mf->second << endl;
		return mf->second;
	}

	int xs = fetch_xs(x, y);
	coord expect = predict_position(x, y, direction, x-xs);
//	cerr << "Found jumping mode from " << x << "," << y << ":" << direction << " to " << expect.x << "," << expect.y << ":" << expect.adds << endl;
//	int my = (coins.count(make_pair(x, y)) ? 1 : 0);
	int recs = predict(expect.x, expect.y, expect.adds);
	int my = coins.count(cdp) ? 1 : 0;
//	cerr << x << "," << y << " is a coin/not a mirror, so answer there is " << recs << " + " << my << "\n";
	return memory[cs] = recs + my;//make_pair( recs.first, recs.second + 1 );
//	cerr << "Seeking " << x << "," << y << " with direction " << direction << ", ret: " << recs.second << ", mine: " << my << endl;
	

}
inline void subgroup() {
	climbings.clear();
	descendings.clear();
	climbing_mirror.clear();
	descending_mirror.clear();
	refs.clear();
	memory.clear();
//	mirrors.clear();
	coins.clear();
	
	farthest_x = 0;
	dp.clear();
	cin>>h>>n;
//	cerr << "h = " << h << ", n = " << n << endl;
	for (int i = 1; i <= n; i++) {
		cin>>mirror[i].x>>mirror[i].y;
//		cerr << "Input " << mirror[i].x << "," << mirror[i].y << endl;
	}
	cin>>m;
	for (int i = 1; i <= m; i++) cin>>coin[i].x>>coin[i].y;
	sort(mirror+1,mirror+n+1);
//	farthest_x = mirror[n].x;
	for (int i = 1; i <= n; i++) {
//		mirrors.insert(make_pair(mirror[i].x, mirror[i].y));
		climbing_mirror[mirror[i].x-mirror[i].y].push_back(mirror[i].x);
		descending_mirror[mirror[i].x+mirror[i].y].push_back(mirror[i].x);
		refs[(mirror[i].x-mirror[i].y)%(h<<1)].push_back(mirror[i].x);
		refs[(mirror[i].x+mirror[i].y)%(h<<1)].push_back(mirror[i].x);
	}
	sort(coin+1,coin+m+1);
	farthest_x = maxi(farthest_x, coin[m].x);
	for (int i = 1; i <= m; i++) {
		coins.insert(make_pair(coin[i].x, coin[i].y));
		climbings[coin[i].x-coin[i].y].push_back(coin[i].x);
		descendings[coin[i].x+coin[i].y].push_back(coin[i].x);
		refs[(coin[i].x-coin[i].y)%(h<<1)].push_back(coin[i].x);
		refs[(coin[i].x+coin[i].y)%(h<<1)].push_back(coin[i].x);
	}
	for (auto &i : refs) sort(i.second.begin(),i.second.end());
	dp[make_pair(0, 0)] = 0;
	int final = 0;
	for (int i = 1; i <= n; i++) {
		int clb = predict(mirror[i].x, mirror[i].y, true);
//		cerr << "--- Finish seeking originally-descending " << mirror[i].x << "," << mirror[i].y << " returning " << clb.first.first << "," << clb.first.second << " + " << clb.second << endl;
//		cerr << "--- Originally-descending: " << clb << endl;
		int des = predict(mirror[i].x, mirror[i].y, false);
//		cerr << "--- Originally-climbing: " << des << endl;
//		cerr << "--- Finish seeking originally-climbing " << mirror[i].x << "," << mirror[i].y << " returning " << des.first.first << "," << des.first.second << " + " << des.second << endl;
		int ans = maxi(clb, des);
		dp[make_pair(mirror[i].x, mirror[i].y)] = ans;
		final = maxi(final, ans);
//		cerr << "=== Evaluated " << mirror[i].x << "," << mirror[i].y << " = " << ans << endl;
	}
	for (int i = 1; i <= m; i++) {
		int clb = predict(coin[i].x, coin[i].y, true);
//		cerr << "--- Finish seeking originally-descending " << coin[i].x << "," << coin[i].y << " returning " << clb.first.first << "," << clb.first.second << " + " << clb.second << endl;
		int des = predict(coin[i].x, coin[i].y, false);
//		cerr << "--- Finish seeking originally-climbing " << coin[i].x << "," << coin[i].y << " returning " << des.first.first << "," << des.first.second << " + " << des.second << endl;
		final = maxi(final, maxi(clb, des));
	}
//	cerr<<"=====Output=====\n";
	cout<<final<<'\n';
//	cerr<<"=====End=====\n";
}

int main() {
#ifdef ONLINE_JUDGE
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
#endif
	
	cin>>T;
	for (int gs = 0; gs < T; gs++) {
		subgroup();
	}
	
	return 0;
}
2024/10/11 20:12
加载中...