30分求助
  • 板块P3751 相遇问题
  • 楼主wuzr
  • 当前回复0
  • 已保存回复0
  • 发布时间2022/1/25 21:06
  • 上次更新2023/10/28 10:57:27
查看原帖
30分求助
400151
wuzr楼主2022/1/25 21:06
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,a,b) for(ll i=a;i<=b;i++)
#define per(i,a,b) for(ll i=a;i>=b;i--)
#define repg(i,a) for(ll i=0;i<son[a].size();i++)
#define min(x,y) (x<y?x:y)
#define max(x,y) (x>y?x:y)
#define mp make_pair
#define P pair<double,int>
ll n, m;
vector<int>q1[100005];
vector<int>q2[100005];
int main() {
	cin >> n >> m;
	rep(i, 1, n) {
		ll k;
		cin >> k;
		ll sh = 0;
		rep(j, 1, k) {
			ll x;
			cin >> x;
			q1[i].push_back(x);
			if (j != 1) q2[i].push_back(q2[i][j - 2] + abs(sh - x));
			else q2[i].push_back(0);
			sh = x;
		}
	}
	rep(i, 1, m) {
		ll x, y, sum = 0;
		cin >> x >> y;
		if (q1[x].size() > q1[y].size()) swap(x, y);
		ll nowx = q1[x][0], nowy = q1[y][0];
		for (unsigned ll j = 0; j + 1 < q1[x].size() && j + 1 < q1[y].size(); j++) {
			ll ti = q2[x][j + 1];
			ll p = lower_bound(q2[y].begin(), q2[y].end(), ti) - q2[y].begin();
			ll cha = q2[y][p] - ti;
			ll mux = q1[x][j + 1], muy = q1[y][p];
			if (q1[y][p] < q1[y][p + 1]) muy += cha;
			else muy -= cha;
			if (nowx < nowy && mux > muy) sum++;
			else if (nowx > nowy && mux < muy) sum++;
			nowx = mux, nowy = muy;
		}
		cout << sum << endl;
	}
	return 0;
}
2022/1/25 21:06
加载中...