Submission #800065

#	Time	Username	Problem	Language	Result	Execution time	Memory
800065		flappybird	수확 (JOI20_harvest)	C++17	0 / 100	117 ms	85668 KiB

harvest

#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<int, int> pii;
#define MAX 505050
#define MAXS 20
#define INF 1000000000000000001
#define bb ' '
#define ln '\n'
#define Ln '\n'
#define MOD 1000000007
const int DEBUG = 0;
const int DEBUG2 = 0;
const int NAIVE = 0;
struct fenwick {
	int N;
	vector<int> tree;
	fenwick(int N = 0) :N(N) { tree.resize(N + 1); }
	void upd(int i, int x) { if (DEBUG2) cout << 'u' << i << bb << x << ln; while (i <= N) { tree[i] += x, i += i & -i; } }
	int get(int i) { int ans = 0; while (i) { ans += tree[i], i -= i & -i; } return ans; }
	int get(int l, int r) { if (DEBUG2) cout << 'd' << l << bb << r << ln; return get(r) - get(l - 1); }
};
int N, M, Q;
ll L, C;
ll A[MAX];
ll B[MAX];
int nxt[MAX]; // next staff
ll cst[MAX]; // distance to nxt[i]
int ccnt; // cycle count
vector<int> cyc[MAX]; // cycles (last element is root)
int topv[MAX]; // cycle number (only root)
int croot[MAX]; // root of cycle
int gp[MAX]; // component number (all vertex)
int 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];
int vis[MAX];
vector<int> adj[MAX]; // tree
ll dep[MAX];
pii range[MAX];
int cnt;
int treein[MAX]; // first staff
ll appledep[MAX]; // apple depth
int applenum[MAX]; // subtree apple number
ll ans[MAX]; // query answer
ll T[MAX]; // query T
int V[MAX]; // query V
ll qdep[MAX];
void dfs(int 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);
	int 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();
	}
	int 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++) {
		int 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;
		int v = i;
		vector<int> 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];
					int 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++) {
		int 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<int> 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(), [&](int i, int j) {return qdep[i] > qdep[j]; });
	fenwick fen(N);
	for (i = 1; i <= M; i++) av.push_back(i);
	sort(av.begin(), av.end(), [&](int i, int j) {return appledep[i] > appledep[j]; });
	int 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);
		assert(ans[q] >= 0);
	}
	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());
		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++) {
		int v = V[i];
		ll t = T[i];
		int cn = gp[v];
		if (sttime[cn].empty()) continue;
		if (!iscyc[v]) continue;
		t -= cdis[v];
		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];
			int ind = upper_bound(rsttime[cn].begin(), rsttime[cn].end(), t) - rsttime[cn].begin();
			ans[i] += ind;
			int 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 (stderr)

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

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