Submission #216734

#	Time	Username	Problem	Language	Result	Execution time	Memory
216734		ainta	Harvest (JOI20_harvest)	C++17	100 / 100	828 ms	128592 KiB

harvest

#include<cstdio>
#include<algorithm>
#include<vector>
#define N_ 201000
#define pli pair<long long, int>
using namespace std;
int n, m, QC, Nxt[N_], Deg[N_], Q[N_];
long long L, CC, A[N_], B[N_], NL[N_];
vector<long long>G[N_];
struct Query {
	int num;
	long long t;
};
vector<Query>QQ[N_];
struct Edge {
	int e;
	long long d;
};
vector<Edge>E[N_];
int Num[N_], Ed[N_], cnt;
long long Res[N_];
vector<long long>TT;


struct RMQ {
	vector<pli>w;
	vector<int>rr;
	int n;
	vector<vector<long long>>IT;
	void Make(int nd, int b, int e) {
		for (int i = b; i <= e; i++)IT[nd].push_back(rr[i]);
		sort(IT[nd].begin(), IT[nd].end());
		if (b == e)return;
		int m = (b + e) >> 1;
		Make(nd * 2, b, m);
		Make(nd * 2 + 1, m + 1, e);
	}
	void build(vector<long long>&inp) {
		n = inp.size();
		w.resize(n);
		rr.resize(n);
		for (int i = 0; i < n; i++)w[i] = { inp[i],i };
		sort(w.begin(), w.end());
		for (int i = 0; i < n; i++)rr[w[i].second] = i;
		int sz = 1;
		while (sz < n)sz *= 2;
		IT.resize(sz * 2);
		for (int i = 0; i < sz * 2; i++)IT[i].clear();
		Make(1, 0, n - 1);
	}
	int Gap(int nd, int b, int e, int s, int l, int g) {
		if (s > l)return 0;
		if (s <= b && e <= l) return lower_bound(IT[nd].begin(), IT[nd].end(), g) - IT[nd].begin();
		int m = (b + e) >> 1, r=0;
		if (s <= m)r += Gap(nd * 2, b, m, s, l, g);
		if (l > m)r += Gap(nd * 2 + 1, m + 1, e, s, l, g);
		return r;
	}
	int Get(int b, int e, long long t) {
		int pv = lower_bound(w.begin(), w.end(), pli(t + 1,0 )) - w.begin();
		return Gap(1, 0, n - 1, b, e, pv);
	}
}PT;

long long Dep[N_];
vector<int>TV;
void DFS(int a, long long d) {
	Num[a] = TT.size();
	TV.push_back(a);
	Dep[a] = d;
	for (auto &t : G[a]) {
		TT.push_back(t + d);
	}
	for (auto &t : E[a]) {
		DFS(t.e, d + t.d);
	}
	Ed[a] = TT.size();
}
long long SS[N_];
long long Calc(long long T, long long tot) {
	int pv = lower_bound(TT.begin(), TT.end(), T + 1)-TT.begin();
	if (pv == 0)return 0ll;
	long long res = pv;
	res += (T / tot)*pv - SS[pv - 1];
	res -= pv - PT.Get(0, pv - 1, T%tot);
	return res;
}
void Do(int a) {
	vector<int>V;
	int t = a;
	long long tot = 0;
	while (1) {
		tot += NL[t];
		Deg[t] = 0;
		V.push_back(t);
		t = Nxt[t];
		if (t == a)break;
	}
	int sz = V.size();
	int i;
	for (i = 1; i < sz; i++) {
		E[V[i]].push_back({ V[i - 1],NL[V[i - 1]] });
	}
	TT.clear();
	TV.clear();
	int rt = V[sz - 1];
	DFS(rt, 0);
	if (TT.empty())return;
	PT.build(TT);
	for (auto &v : TV) {
		for (auto &q : QQ[v]) {
			Res[q.num] += PT.Get(Num[v], Ed[v] - 1, q.t + Dep[v]);
		}
	}

	t = rt;
	long long ss = 0;
	sort(TT.begin(), TT.end());
	vector<long long>TMod;
	for (i = 0; i < TT.size(); i++) {
		TMod.push_back(TT[i] % tot);
		SS[i] = TT[i] / tot;
		if (i)SS[i] += SS[i - 1];
	}
	PT.build(TMod);
	while (1) {
		ss += NL[t];
		t = Nxt[t];
		for (auto &z : QQ[t]) {
			Res[z.num] += Calc(z.t - ss, tot);
		}
		if (t == rt)break;
	}
}
int main() {
	//freopen("input.txt", "r", stdin);
	int i;
	scanf("%d%d%lld%lld", &n, &m, &L, &CC);
	for (i = 1; i <= n; i++) {
		scanf("%lld", &A[i]);
	}
	for (i = 1; i <= n; i++) {
		long long x = (A[i] - CC + CC*L)%L;
		int pv = lower_bound(A + 1, A + n + 1, x + 1) - A;
		pv--;
		if (pv == 0)pv = n;
		Nxt[i] = pv;
		NL[i] = A[i] - A[pv];
		if (NL[i] < CC) NL[i] += (CC - NL[i] + L - 1) / L * L;
		Deg[Nxt[i]]++;
	}
	for (i = 1; i <= m; i++) {
		scanf("%lld", &B[i]);
		int pv = lower_bound(A + 1, A + n + 1, B[i] + 1) - A;
		pv--;
		if (pv == 0)pv = n;
		long long t = B[i] - A[pv];
		if (t < 0)t += L;
		G[pv].push_back(t);
	}
	int head = 0, tail = 0;
	for (i = 1; i <= n; i++)if (!Deg[i])Q[++tail] = i;
	while (head < tail) {
		int x = Q[++head];
		Deg[Nxt[x]]--;
		E[Nxt[x]].push_back({ x,NL[x] });
		if (!Deg[Nxt[x]])Q[++tail] = Nxt[x];
	}
	scanf("%d", &QC);
	for (i = 1; i <= QC; i++) {
		int a;
		long long t;
		scanf("%d%lld", &a, &t);
		QQ[a].push_back({ i,t });
	}
	for (i = 1; i <= n; i++) {
		if (Deg[i]) {
			Do(i);
		}
	}
	for (i = 1; i <= QC; i++)printf("%lld\n", Res[i]);
}

Compilation message (stderr)

harvest.cpp: In function 'void Do(int)':
harvest.cpp:120:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (i = 0; i < TT.size(); i++) {
              ~~^~~~~~~~~~~
harvest.cpp: In function 'int main()':
harvest.cpp:138:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%lld%lld", &n, &m, &L, &CC);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
harvest.cpp:140:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &A[i]);
   ~~~~~^~~~~~~~~~~~~~~
harvest.cpp:153:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &B[i]);
   ~~~~~^~~~~~~~~~~~~~~
harvest.cpp:169:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &QC);
  ~~~~~^~~~~~~~~~~
harvest.cpp:173:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%lld", &a, &t);
   ~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 20 / 20
• Subtask 3: 75 / 75