Submission #216905

#	Time	Username	Problem	Language	Result	Execution time	Memory
216905		Toadologist	Harvest (JOI20_harvest)	C++11	100 / 100	2394 ms	272572 KiB

harvest

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
#ifdef DEBUG
#define display(x) cerr << #x << " = " << (x) << endl;
#define displaya(a, st, n)\
	{cerr << #a << " = {";\
	for(int qwq = (st); qwq <= (n); ++qwq) {\
		if(qwq == (st)) cerr << ((a)[qwq]);\
		else cerr << ", " << ((a)[qwq]);\
	} cerr << "}" << endl;}
#define displayv(v) displaya(v, 0, (int)(v).size() - 1)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define display(x) ;
#define displaya(a, st, n) ;
#define displayv(v) ;
#define eprintf(...) if(0) fprintf(stderr, "...")
#endif
template<typename T> bool chmin(T &a, const T &b) { return a > b ? a = b, true : false; }
template<typename T> bool chmax(T &a, const T &b) { return a < b ? a = b, true : false; }
template<typename A, typename B>
ostream& operator << (ostream& out, const pair<A, B> &p) {
	return out << '(' << p.first << ", " << p.second << ')';
}
#ifndef LOCAL
char pool[1<<15|1],*it=pool+32768;
#define getchar() (it>=pool+32768?(pool[fread(pool,sizeof(char),\
	1<<15,stdin)]=EOF,*((it=pool)++)):*(it++))
#endif
inline LL readint() {
	LL a = 0; char c = getchar(), p = 0;
	while(isspace(c)) c = getchar();
	if(c == '-') p = 1, c = getchar();
	while(isdigit(c)) a = a*10 + c - '0', c = getchar();
	return p ? -a : a;
}

LL lowdiv(LL x, LL y) {
	assert(y > 0);
	return x / y + (x % y < 0 ? -1 : 0);
}
LL lowmod(LL x, LL y) {
	return x - lowdiv(x, y) * y;
}

const int maxN = 200000 + 5;
int n, m;
LL L, C, a[maxN], b[maxN];
vector<int> h[maxN];

int to[maxN];
vector<int> G[maxN];
LL w[maxN], len[maxN];
bool vis[maxN];
vector<int> loop[maxN];

LL p[maxN];
int id[maxN], clus[maxN];

struct Node {
	LL a, b;
	int c;
	LL coef;
	int i;
	Node() {}
	Node(LL a, LL b, int c, LL coef, int i)
		: a(a), b(b), c(c), coef(coef), i(i) {}
	friend bool operator < (const Node &x, const Node &y) {
		return x.a != y.a ? x.a < y.a
			: x.b != y.b ? x.b < y.b
			: x.c != y.c ? x.c < y.c
			: x.i < y.i;
	}
	Node una() const {
		Node res = *this;
		res.a = 0;
		return res;
	}
};
vector<Node> sz, bigs, sh, tmp;

LL asz[maxN], abigs[maxN], ash[maxN];

LL D[maxN];
void add(int p, LL x) {
	for(; p <= n; p += p & -p) D[p] += x;
}
LL sum(int p) {
	LL r = 0;
	for(; p > 0; p -= p & -p) r += D[p];
	return r;
}
void dnc(vector<Node> &a, int L, int R, LL stat[]) { // tmp size
	if(L >= R) return;
	int M = (L + R) >> 1;
	dnc(a, L, M, stat); dnc(a, M + 1, R, stat);
	
	int k = L;
	auto addL = [&](Node &p) {
		if(p.i < 0) add(p.c, p.coef);
		tmp[k++] = p;
	};
	auto addR = [&](Node &p) {
		if(p.i > 0) stat[p.i] += sum(p.c) * p.coef;
		tmp[k++] = p;
	};
	int i = L, j = M + 1;
	while(i <= M && j <= R) {
		if(a[i].una() < a[j].una()) addL(a[i++]);
		else addR(a[j++]);
	}
	while(i <= M) addL(a[i++]);
	while(j <= R) addR(a[j++]);
	for(int t = L; t <= M; ++t) if(a[t].i < 0) add(a[t].c, -a[t].coef);
	for(int t = L; t <= R; ++t) a[t] = tmp[t];
}

int dfs_clock = 0, pre[maxN], post[maxN], euler[maxN];
void dfs(int u) {
	vis[u] = true;
	euler[pre[u] = ++dfs_clock] = u;
//	eprintf("euler[%d] = %d, p = %lld\n", dfs_clock, u, p[u]);
	
	for(int t : h[u]) {
		sz.emplace_back(0, p[u] + t, pre[u], 1, -u);
		bigs.emplace_back(0, p[u] + t, pre[u], lowdiv(- p[u] - t, len[clus[u]]), -u);
		sh.emplace_back(-lowmod(- p[u] - t, len[clus[u]]), p[u] + t, pre[u], 1, -u);
	}
	
	for(int v : G[u]) if(id[v] == -1) {
		p[v] = p[u] + w[v];
		clus[v] = clus[u];
		dfs(v);
	}
	post[u] = dfs_clock;
}

void build(int u) {
	while(!vis[u]) vis[u] = true, u = to[u];
	vector<int> &loop = ::loop[u];
	loop.push_back(u); p[u] = 0;
	while(to[u] != loop[0]) {
		p[to[u]] = p[u] - w[u];
		u = to[u];
		loop.push_back(u);
	}
	u = loop[0];
	len[u] = 0;
	for(int x : loop) len[u] += w[x];
	for(int i = 0; i < (int)loop.size(); ++i) clus[loop[i]] = u, id[loop[i]] = i;
	displayv(loop);
	displaya(to, 1, n);
	displaya(id, 1, n);
	for(int x : loop) dfs(x);
}

int qu[maxN];
LL qt[maxN];

int main() {
	n = readint(); m = readint(); L = readint(); C = readint();
	for(int i = 1; i <= n; ++i) a[i] = readint();
	for(int j = 1; j <= m; ++j) b[j] = readint();
	
	for(int j = 1; j <= m; ++j) {
		if(a[1] <= b[j]) {
			int i = upper_bound(a + 1, a + n + 1, b[j]) - a;
			--i;
			h[i].push_back(b[j] - a[i]);
		} else {
			h[n].push_back(b[j] + L - a[n]);
		}
	}
	for(int i = 1; i <= n; ++i) sort(h[i].begin(), h[i].end());
	for(int i = 1; i <= n; ++i) {
		int p = a[i] - C;
		p = (p % L + L) % L;
		if(a[1] <= p)
			to[i] = upper_bound(a + 1, a + n + 1, p) - a - 1,
			w[i] = C + p - a[to[i]];
		else
			to[i] = n,
			w[i] = C + p + L - a[to[i]];
	}
	memset(vis, 0, sizeof(vis));
	memset(clus, 0, sizeof(clus));
	memset(id, -1, sizeof(id));
	for(int i = 1; i <= n; ++i) G[to[i]].push_back(i);
	for(int i = 1; i <= n; ++i) if(!vis[i]) build(i);
	
	int q = readint();
	for(int i = 1; i <= q; ++i) {
		int u = readint(); qu[i] = u;
		LL T = readint(); qt[i] = T;
		if(id[u] == -1) {
			sz.emplace_back(0, T + p[u], pre[u] - 1, -1, i);
			sz.emplace_back(0, T + p[u], post[u], +1, i);
		} else {
			vector<int> &loop = ::loop[clus[u]];
			int L = pre[loop[0]], M = post[u], R = post[loop.back()];
			assert(L <= M && M <= R);
			LL len = ::len[clus[u]];
			
			sz.emplace_back(0, T + p[u], L - 1, -1, i);
			sz.emplace_back(0, T + p[u], M, +1, i);
			sz.emplace_back(0, T + p[u] - len, M, -(m + 1), i);
			sz.emplace_back(0, T + p[u] - len, R, +(m + 1), i);
			
			bigs.emplace_back(0, T + p[u], L - 1, -1, i);
			bigs.emplace_back(0, T + p[u], M, +1, i);
			bigs.emplace_back(0, T + p[u] - len, M, -1, i);
			bigs.emplace_back(0, T + p[u] - len, R, +1, i);
			
			LL t2 = lowmod(T + p[u], len);
			sh.emplace_back(t2 - len, T + p[u], L - 1, -1, i);
			sh.emplace_back(t2 - len, T + p[u], M, +1, i);
			sh.emplace_back(t2 - 2 * len, T + p[u], L - 1, -1, i);
			sh.emplace_back(t2 - 2 * len, T + p[u], M, +1, i);
			
			sh.emplace_back(t2 - len, T + p[u] - len, M, -1, i);
			sh.emplace_back(t2 - len, T + p[u] - len, R, +1, i);
			sh.emplace_back(t2 - 2 * len, T + p[u] - len, M, -1, i);
			sh.emplace_back(t2 - 2 * len, T + p[u] - len, R, +1, i);
			
		}
	}
	
	memset(D, 0, sizeof(D));
	sort(sz.begin(), sz.end());
	sort(bigs.begin(), bigs.end());
	sort(sh.begin(), sh.end());
	
	tmp.resize(max({sz.size(), bigs.size(), sh.size()}));
	
	dnc(sz, 0, (int)sz.size() - 1, asz);
	dnc(bigs, 0, (int)bigs.size() - 1, abigs);
	dnc(sh, 0, (int)sh.size() - 1, ash);
	for(int i = 1; i <= q; ++i) {
		int u = qu[i];
		LL T = qt[i];
		LL ans = 0;
		if(id[u] == -1) {
			ans = asz[i];
		} else {
			LL L = len[clus[u]];
			LL lef = asz[i] % (m + 1), rig = asz[i] / (m + 1);
			ans = (lef + rig) * lowdiv(T + p[u], L) + lef;
			ans += abigs[i];
			ans += ash[i];
//			eprintf("len = %lld; %lld %lld %lld %lld\n", L, lef, rig, abigs[i], ash[i]);
		}
		printf("%lld\n", ans);
	}
	return 0;
}

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