oj.uz

Submission #216734

# Submission time Handle Problem Language Result Execution time Memory
216734 2020-03-27T23:51:43 Z ainta Harvest (JOI20_harvest) C++17
100 / 100
 828 ms 128592 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 14848 KB Output is correct
2 Correct 23 ms 14976 KB Output is correct
3 Correct 19 ms 15744 KB Output is correct
4 Correct 21 ms 16000 KB Output is correct
5 Correct 20 ms 16128 KB Output is correct
6 Correct 20 ms 16128 KB Output is correct
7 Correct 24 ms 16128 KB Output is correct
8 Correct 20 ms 15872 KB Output is correct
9 Correct 20 ms 15872 KB Output is correct
10 Correct 20 ms 15872 KB Output is correct
11 Correct 22 ms 15872 KB Output is correct
12 Correct 21 ms 16128 KB Output is correct
13 Correct 46 ms 16120 KB Output is correct
14 Correct 23 ms 15616 KB Output is correct
15 Correct 21 ms 16000 KB Output is correct
16 Correct 20 ms 16000 KB Output is correct
17 Correct 21 ms 16000 KB Output is correct
18 Correct 20 ms 16000 KB Output is correct
19 Correct 21 ms 16000 KB Output is correct
20 Correct 23 ms 16000 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 27928 KB Output is correct
2 Correct 304 ms 44268 KB Output is correct
3 Correct 232 ms 36728 KB Output is correct
4 Correct 236 ms 37728 KB Output is correct
5 Correct 293 ms 58476 KB Output is correct
6 Correct 286 ms 58536 KB Output is correct
7 Correct 249 ms 41636 KB Output is correct
8 Correct 231 ms 41696 KB Output is correct
9 Correct 340 ms 59484 KB Output is correct
10 Correct 229 ms 58052 KB Output is correct
11 Correct 483 ms 58356 KB Output is correct
12 Correct 462 ms 58484 KB Output is correct
13 Correct 455 ms 58468 KB Output is correct
14 Correct 292 ms 57028 KB Output is correct
15 Correct 330 ms 52728 KB Output is correct
16 Correct 282 ms 52076 KB Output is correct
17 Correct 258 ms 51824 KB Output is correct
18 Correct 207 ms 33140 KB Output is correct
19 Correct 181 ms 33040 KB Output is correct
20 Correct 230 ms 45160 KB Output is correct

Subtask #3
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 14848 KB Output is correct
2 Correct 23 ms 14976 KB Output is correct
3 Correct 19 ms 15744 KB Output is correct
4 Correct 21 ms 16000 KB Output is correct
5 Correct 20 ms 16128 KB Output is correct
6 Correct 20 ms 16128 KB Output is correct
7 Correct 24 ms 16128 KB Output is correct
8 Correct 20 ms 15872 KB Output is correct
9 Correct 20 ms 15872 KB Output is correct
10 Correct 20 ms 15872 KB Output is correct
11 Correct 22 ms 15872 KB Output is correct
12 Correct 21 ms 16128 KB Output is correct
13 Correct 46 ms 16120 KB Output is correct
14 Correct 23 ms 15616 KB Output is correct
15 Correct 21 ms 16000 KB Output is correct
16 Correct 20 ms 16000 KB Output is correct
17 Correct 21 ms 16000 KB Output is correct
18 Correct 20 ms 16000 KB Output is correct
19 Correct 21 ms 16000 KB Output is correct
20 Correct 23 ms 16000 KB Output is correct
21 Correct 186 ms 27928 KB Output is correct
22 Correct 304 ms 44268 KB Output is correct
23 Correct 232 ms 36728 KB Output is correct
24 Correct 236 ms 37728 KB Output is correct
25 Correct 293 ms 58476 KB Output is correct
26 Correct 286 ms 58536 KB Output is correct
27 Correct 249 ms 41636 KB Output is correct
28 Correct 231 ms 41696 KB Output is correct
29 Correct 340 ms 59484 KB Output is correct
30 Correct 229 ms 58052 KB Output is correct
31 Correct 483 ms 58356 KB Output is correct
32 Correct 462 ms 58484 KB Output is correct
33 Correct 455 ms 58468 KB Output is correct
34 Correct 292 ms 57028 KB Output is correct
35 Correct 330 ms 52728 KB Output is correct
36 Correct 282 ms 52076 KB Output is correct
37 Correct 258 ms 51824 KB Output is correct
38 Correct 207 ms 33140 KB Output is correct
39 Correct 181 ms 33040 KB Output is correct
40 Correct 230 ms 45160 KB Output is correct
41 Correct 741 ms 114024 KB Output is correct
42 Correct 331 ms 40868 KB Output is correct
43 Correct 176 ms 34396 KB Output is correct
44 Correct 565 ms 104100 KB Output is correct
45 Correct 626 ms 127052 KB Output is correct
46 Correct 635 ms 128072 KB Output is correct
47 Correct 652 ms 128592 KB Output is correct
48 Correct 634 ms 126740 KB Output is correct
49 Correct 610 ms 127172 KB Output is correct
50 Correct 588 ms 112988 KB Output is correct
51 Correct 557 ms 112220 KB Output is correct
52 Correct 824 ms 128096 KB Output is correct
53 Correct 733 ms 127468 KB Output is correct
54 Correct 828 ms 127768 KB Output is correct
55 Correct 722 ms 127972 KB Output is correct
56 Correct 707 ms 120972 KB Output is correct
57 Correct 702 ms 121792 KB Output is correct
58 Correct 717 ms 122592 KB Output is correct
59 Correct 672 ms 120016 KB Output is correct
60 Correct 640 ms 120544 KB Output is correct
61 Correct 643 ms 120544 KB Output is correct
62 Correct 628 ms 89740 KB Output is correct
63 Correct 506 ms 100616 KB Output is correct
64 Correct 498 ms 100748 KB Output is correct
65 Correct 499 ms 100896 KB Output is correct
66 Correct 494 ms 100712 KB Output is correct
67 Correct 480 ms 100680 KB Output is correct
68 Correct 473 ms 99944 KB Output is correct
69 Correct 658 ms 116312 KB Output is correct
70 Correct 630 ms 113036 KB Output is correct
71 Correct 657 ms 113884 KB Output is correct
72 Correct 672 ms 113756 KB Output is correct