oj.uz

Submission #800006

# Submission time Handle Problem Language Result Execution time Memory
800006 2023-08-01T09:17:54 Z 박영우(#10085) Harvest (JOI20_harvest) C++17
0 / 100
 5000 ms 80908 KB 
#include <bits/stdc++.h>
#include <cassert>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<ll, ll> pii;
#define MAX 505050
#define MAXS 20
#define INF 1000000000000000001
#define bb ' '
#define ln '\n'
#define Ln '\n'
#define MOD 1000000007
const ll DEBUG = 0;
const ll DEBUG2 = 0;
const ll NAIVE = 1;
struct fenwick {
	ll N;
	vector<ll> tree;
	fenwick(ll N = 0) :N(N) { tree.resize(N + 1); }
	void upd(ll i, ll x) { if (DEBUG2) cout << 'u' << i << bb << x << ln; while (i <= N) { tree[i] += x, i += i & -i; } }
	ll get(ll i) { ll ans = 0; while (i) { ans += tree[i], i -= i & -i; } return ans; }
	ll get(ll l, ll r) { if (DEBUG2) cout << 'd' << l << bb << r << ln; return get(r) - get(l - 1); }
};
ll N, M, Q;
ll L, C;
ll A[MAX];
ll B[MAX];
ll nxt[MAX]; // next staff
ll cst[MAX]; // distance to nxt[i]
ll ccnt; // cycle count
vector<ll> cyc[MAX]; // cycles (last element is root)
ll topv[MAX]; // cycle number (only root)
ll croot[MAX]; // root of cycle
ll gp[MAX]; // component number (all vertex)
ll iscyc[MAX]; // 1 if cycle
ll cdis[MAX]; // distanct from cyc[0]
ll clen[MAX]; // length of cycle
vector<ll> sttime[MAX];
vector<ll> rsttime[MAX]; //real value
vector<ll> dv[MAX];
vector<ll> psum[MAX];
ll cycstart[MAX];
ll vis[MAX];
vector<ll> adj[MAX]; // tree
ll dep[MAX];
pii range[MAX];
ll cnt;
ll treein[MAX]; // first staff
ll appledep[MAX]; // apple depth
ll applenum[MAX]; // subtree apple number
ll ans[MAX]; // query answer
ll T[MAX]; // query T
ll V[MAX]; // query V
ll qdep[MAX];
void dfs(ll x) {
	if (topv[x]) gp[x] = topv[x];
	cnt++;
	range[x] = { cnt, cnt };
	for (auto v : adj[x]) {
		dep[v] = dep[x] + cst[v];
		gp[v] = gp[x];
		dfs(v);
		applenum[x] += applenum[v];
		range[x].second = max(range[x].second, range[v].second);
	}
}
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	ll i, j;
	if (!DEBUG) {
		cin >> N >> M >> L >> C;
		for (i = 1; i <= N; i++) cin >> A[i];
		for (i = 1; i <= M; i++) cin >> B[i];
		cin >> Q;
		for (i = 1; i <= Q; i++) cin >> V[i] >> T[i];
	}
	else {
		cin >> N >> M >> L >> C;
		for (i = 1; i <= N; i++) A[i] = i;
		for (j = 1; j <= M; j++) B[i] = N + j;
		cin >> Q;
		for (i = 1; i <= Q; i++) V[i] = i, T[i] = rand();
	}
	ll c = C % L;
	vector<ll> v;
	for (i = 1; i <= N; i++) v.push_back(A[i]);
	for (i = 1; i <= N; i++) v.push_back(A[i] + L);
	for (i = 1; i <= N; i++) {
		ll ind = upper_bound(v.begin(), v.end(), A[i] - c + L) - v.begin();
		ind--;
		ind %= N;
		if (ind < 0) ind += N;
		nxt[i] = ind + 1;
		cst[i] = A[i] - A[nxt[i]] + L;
		cst[i] %= L;
		ll d = C - cst[i];
		if (d > 0) {
			d = (d + L - 1) / L;
			d *= L;
			cst[i] += d;
		}
	}
	for (i = 1; i <= N; i++) {
		if (vis[i]) continue;
		ll v = i;
		vector<ll> path;
		while (1) {
			path.push_back(v);
			vis[v] = 1;
			if (vis[nxt[v]]) {
				if (!iscyc[nxt[v]]) {
					ccnt++;
					while (path.size()) {
						cyc[ccnt].push_back(path.back());
						if (path.back() == nxt[v]) break;
						path.pop_back();
					}
					reverse(cyc[ccnt].begin(), cyc[ccnt].end());
					for (auto v : cyc[ccnt]) iscyc[v] = 1;
					for (auto v : cyc[ccnt]) clen[ccnt] += cst[v];
					ll pv = -1;
					for (auto v : cyc[ccnt]) {
						if (~pv) cdis[v] = cdis[pv] + cst[pv];
						pv = v;
					}
					topv[cyc[ccnt].back()] = ccnt;
					croot[ccnt] = cyc[ccnt].back();
				}
				break;
			}
			v = nxt[v];
		}
	}
	for (i = 1; i <= M; i++) {
		ll ind = upper_bound(v.begin(), v.end(), B[i]) - v.begin() - 1;
		ind %= N;
		if (ind < 0) ind += N;
		ind++;
		treein[i] = ind;
		appledep[i] = B[i] - A[ind];
		if (appledep[i] < 0) appledep[i] += L;
		applenum[ind]++;
	}
	for (i = 1; i <= N; i++) if (!topv[i]) adj[nxt[i]].push_back(i);
	for (i = 1; i <= N; i++) if (topv[i]) dfs(i);
	for (i = 1; i <= M; i++) appledep[i] += dep[treein[i]];
	vector<ll> qv, av;
	for (i = 1; i <= Q; i++) qv.push_back(i), ans[i] = applenum[V[i]], qdep[i] = dep[V[i]] + T[i];
	sort(qv.begin(), qv.end(), [&](ll i, ll j) {return qdep[i] > qdep[j]; });
	fenwick fen(N);
	for (i = 1; i <= M; i++) av.push_back(i);
	sort(av.begin(), av.end(), [&](ll i, ll j) {return appledep[i] > appledep[j]; });
	ll ptr = 0;
	for (auto q : qv) {
		while (ptr < av.size() && qdep[q] < appledep[av[ptr]]) fen.upd(range[treein[av[ptr++]]].first, 1);
		ans[q] -= fen.get(range[V[q]].first, range[V[q]].second);
	}
	for (i = 1; i <= M; i++) sttime[gp[treein[i]]].push_back(appledep[i] + cst[croot[gp[treein[i]]]]);
	for (i = 1; i <= ccnt; i++) {
		if (sttime[i].empty()) continue;
		sort(sttime[i].begin(), sttime[i].end());
		cycstart[i] = sttime[i][0];
		for (auto& v : sttime[i]) v -= cycstart[i];
		rsttime[i] = sttime[i];
		for (auto& v : sttime[i]) {
			dv[i].push_back(v / clen[i]);
			v %= clen[i];
		}
		sort(dv[i].begin(), dv[i].end());
		psum[i] = dv[i];
		for (j = 1; j < dv[i].size(); j++) psum[i][j] += psum[i][j - 1];
	}
	for (i = 1; i <= Q; i++) {
		ll v = V[i];
		ll t = T[i];
		ll cn = gp[v];
		if (sttime[cn].empty()) continue;
		if (!iscyc[v]) continue;
		t -= cdis[v];
		t -= cycstart[cn];
		if (t < 0) continue;
		if (NAIVE) {
			for (auto tt : rsttime[cn]) {
				if (t >= tt) {
					t -= tt;
					ans[i] += t / clen[cn] + 1;
					t += tt;
				}
			}
		}
		else {
			ll rot = t / clen[cn];
			ans[i] += rot * sttime[cn].size();
			t -= rot * clen[cn];
			ll ind = upper_bound(rsttime[cn].begin(), rsttime[cn].end(), t) - rsttime[cn].begin();
			ans[i] += ind;
			ll rind = lower_bound(dv[cn].begin(), dv[cn].end(), rot) - dv[cn].begin();
			if (rind > 0) ans[i] -= psum[cn][rind - 1];
			ans[i] -= ((ll)dv[cn].size() - rind) * rot;
		}
	}
	for (i = 1; i <= Q; i++) cout << ans[i] << Ln;
}

Compilation message

harvest.cpp: In function 'int main()':
harvest.cpp:160:14: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  160 |   while (ptr < av.size() && qdep[q] < appledep[av[ptr]]) fen.upd(range[treein[av[ptr++]]].first, 1);
      |          ~~~~^~~~~~~~~~~
harvest.cpp:176:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  176 |   for (j = 1; j < dv[i].size(); j++) psum[i][j] += psum[i][j - 1];
      |               ~~^~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 71792 KB Output is correct
2 Correct 39 ms 72524 KB Output is correct
3 Correct 119 ms 72472 KB Output is correct
4 Correct 41 ms 72532 KB Output is correct
5 Correct 39 ms 72652 KB Output is correct
6 Correct 38 ms 72636 KB Output is correct
7 Correct 39 ms 72672 KB Output is correct
8 Correct 42 ms 72348 KB Output is correct
9 Correct 39 ms 72300 KB Output is correct
10 Correct 39 ms 72540 KB Output is correct
11 Correct 38 ms 72648 KB Output is correct
12 Correct 39 ms 72716 KB Output is correct
13 Correct 90 ms 72836 KB Output is correct
14 Correct 77 ms 72688 KB Output is correct
15 Incorrect 38 ms 72596 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

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

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 71792 KB Output is correct
2 Correct 39 ms 72524 KB Output is correct
3 Correct 119 ms 72472 KB Output is correct
4 Correct 41 ms 72532 KB Output is correct
5 Correct 39 ms 72652 KB Output is correct
6 Correct 38 ms 72636 KB Output is correct
7 Correct 39 ms 72672 KB Output is correct
8 Correct 42 ms 72348 KB Output is correct
9 Correct 39 ms 72300 KB Output is correct
10 Correct 39 ms 72540 KB Output is correct
11 Correct 38 ms 72648 KB Output is correct
12 Correct 39 ms 72716 KB Output is correct
13 Correct 90 ms 72836 KB Output is correct
14 Correct 77 ms 72688 KB Output is correct
15 Incorrect 38 ms 72596 KB Output isn't correct
16 Halted 0 ms 0 KB -