oj.uz

Submission #282078

# Submission time Handle Problem Language Result Execution time Memory
282078 2020-08-24T00:03:50 Z amoo_safar Harvest (JOI20_harvest) C++17
0 / 100
 33 ms 16880 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'

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;
				}
			}
		}
	}
}

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

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 14720 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 16880 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 14720 KB Output isn't correct
2 Halted 0 ms 0 KB -