oj.uz

Submission #282079

# Submission time Handle Problem Language Result Execution time Memory
282079 2020-08-24T00:05:29 Z amoo_safar Harvest (JOI20_harvest) C++17
5 / 100
 5000 ms 24660 KB 
// That's How much we have in common
#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'
#define int ll

using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;

const ll Mod = 1000000007LL;
const int N = 2e5 + 10;
const ll Inf = 2242545357980376863LL;
const int inf = 2'000'000'000;
const ll Log = 30;

int n, m, C, L, Q;
int A[N], B[N];
int nx[N], w[N], fs[N], df[N];
int V[N], T[N], ans[N];

vector<int> GI[N], TR[N], QR[N];
int slv[N];
int mk[N], incyc[N], st[N], fn[N], Tm = 1;

ll dep[N], deptr[N], al[N];
vector<int> vis, cyc;
void DFS(int u, ll d = 0){
	slv[u] = 1;
	st[u] = Tm ++;
	dep[u] = d;
	vis.pb(u);
	for(auto adj : GI[u]){
		if(!slv[adj])
			DFS(adj, d + w[adj]);
	}
	fn[u] = Tm ++;
}

int fen[N];
void Add(int idx, int d){
	for(; idx < N; idx += (idx & -idx))
		fen[idx] += d;
}
int Get(int idx){
	int res = 0;
	for(; idx; idx -= (idx & -idx))
		res += fen[idx];
	return res;
}

void Solve(int rt){
	//debug(rt);
	vis.clear();
	DFS(rt, 0);

	cyc.clear();
	int nw = rt;
	do {
		cyc.pb(nw);
		incyc[nw] = 1;
		nw = nx[nw];
	} while(nw != rt);
	ll CL = 0;
	for(auto x : cyc) CL += w[x];
	for(int i = 1; i < (int) cyc.size(); i++) al[cyc[i]] = al[cyc[i - 1]] + w[cyc[i - 1]];
	//debug(CL);

	vector<pll> E;
	for(auto nd : vis){
		for(auto ap : TR[nd]){
			deptr[ap] = dep[nd] + df[ap];
			E.pb({deptr[ap], -st[nd]});
		}
		if(nd != rt){
			for(auto qr : QR[nd])
				E.pb({T[qr] + dep[nd], qr});
		}
	}
	sort(all(E));
	for(auto ev : E){
		if(ev.S < 0){
			Add(-ev.S, 1);
		} else {
			ans[ev.S] += Get(fn[V[ev.S]] - 1) - Get(st[V[ev.S]] - 1);
		}
	}
	// Clear
	for(auto ev : E)
		if(ev.S < 0)
			Add(-ev.S, -1);

	for(auto nd : vis){
		if(!incyc[nd]) continue;
		//debug(nd);
		for(auto qr : QR[nd]){
			for(auto nd2 : vis) for(auto ap : TR[nd2]){
				if(T[qr] - al[nd] >= deptr[ap]){
					ans[qr] += 1 + (T[qr] - al[nd] - deptr[ap]) / CL;
				}
			}
		}
	}
}

int32_t main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m >> L >> C;
	for(int i = 0; i < n; i++) cin >> A[i];
	A[n] = inf;
	for(int i = 0; i < m; i++) cin >> B[i];
	cin >> Q;
	for(int i = 0; i < Q; i++){ cin >> V[i] >> T[i]; V[i] --; }
	for(int i = 0; i < Q; i++) QR[V[i]].pb(i);

	for(int i = 0; i < n; i++){
		int wh = (((A[i] - C) % L) + L) % L;
		if(wh < A[0]) nx[i] = n - 1;
		else 
			nx[i] = (upper_bound(A, A + n, wh) - A) - 1;
		w[i] = C + ((wh - A[nx[i]] + L) % L);
		GI[nx[i]].pb(i);
	}
	for(int i = 0; i < m; i++){
		int wh = B[i];
		if(wh < A[0]) fs[i] = n - 1;
		else 
			fs[i] = (upper_bound(A, A + n, wh) - A) - 1;
		df[i] = (wh - A[fs[i]] + L) % L;
		TR[fs[i]].pb(i);
	}
	/*
	cerr << "! ";
	for(int i = 0; i < m; i++) cerr << df[i] << ' ';
	cerr << '\n';
	*/
	for(int i = 0; i < n; i++){
		if(slv[i]) continue;
		int nw = i;
		mk[nw] = 1;
		int src = -1;
		while(src == -1){
			nw = nx[nw];
			if(mk[nw]) src = nw;
			mk[nw] = 1;
		}
		Solve(src);
	}
	for(int i = 0; i < Q; i++) cout << ans[i] << '\n';
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 14848 KB Output is correct
2 Correct 14 ms 15360 KB Output is correct
3 Correct 113 ms 15360 KB Output is correct
4 Correct 15 ms 15520 KB Output is correct
5 Correct 14 ms 15616 KB Output is correct
6 Correct 14 ms 15616 KB Output is correct
7 Correct 14 ms 15616 KB Output is correct
8 Correct 13 ms 15424 KB Output is correct
9 Correct 13 ms 15360 KB Output is correct
10 Correct 14 ms 15488 KB Output is correct
11 Correct 13 ms 15360 KB Output is correct
12 Correct 71 ms 15760 KB Output is correct
13 Correct 85 ms 15744 KB Output is correct
14 Correct 56 ms 15608 KB Output is correct
15 Correct 14 ms 15616 KB Output is correct
16 Correct 15 ms 15616 KB Output is correct
17 Correct 14 ms 15744 KB Output is correct
18 Correct 14 ms 15488 KB Output is correct
19 Correct 14 ms 15488 KB Output is correct
20 Correct 14 ms 15520 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5030 ms 24660 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 14848 KB Output is correct
2 Correct 14 ms 15360 KB Output is correct
3 Correct 113 ms 15360 KB Output is correct
4 Correct 15 ms 15520 KB Output is correct
5 Correct 14 ms 15616 KB Output is correct
6 Correct 14 ms 15616 KB Output is correct
7 Correct 14 ms 15616 KB Output is correct
8 Correct 13 ms 15424 KB Output is correct
9 Correct 13 ms 15360 KB Output is correct
10 Correct 14 ms 15488 KB Output is correct
11 Correct 13 ms 15360 KB Output is correct
12 Correct 71 ms 15760 KB Output is correct
13 Correct 85 ms 15744 KB Output is correct
14 Correct 56 ms 15608 KB Output is correct
15 Correct 14 ms 15616 KB Output is correct
16 Correct 15 ms 15616 KB Output is correct
17 Correct 14 ms 15744 KB Output is correct
18 Correct 14 ms 15488 KB Output is correct
19 Correct 14 ms 15488 KB Output is correct
20 Correct 14 ms 15520 KB Output is correct
21 Execution timed out 5030 ms 24660 KB Time limit exceeded
22 Halted 0 ms 0 KB -