Submission #960570

#	Time	Username	Problem	Language	Result	Execution time	Memory
960570		Pring	Harvest (JOI20_harvest)	C++17	0 / 100	95 ms	55132 KiB

harvest

#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;

#ifdef MIKU
string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m";
#define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x)
void dout() { cout << dbrs << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif

#define int long long
#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
using ll = long long;
typedef pair<int, int> pii;
typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> PBDS_TREE;

const int MXN = 200005;
int n, m, L, adf, a[MXN], b[MXN], q, qid[MXN];
ll qt[MXN];
int p[MXN], pt[MXN];
ll ans[MXN];
vector<pii> edge[MXN];
vector<int> qry[MXN];
bitset<MXN> vis;
PBDS_TREE tr[MXN];
ll lz[MXN];

struct VSET {
	bitset<MXN> b;
	vector<int> v;
	void init() {
		b.reset();
		v.clear();
	}
	void insert(int x) {
		if (b[x]) return;
		b[x] = true;
		v.push_back(x);
	}
	void clear() {
		for (auto &i : v) b[i] = false;
		v.clear();
	}
} sr;

struct BIT {
	int n;
	ll val[MXN];
	void init(int _n) {
		n = _n;
		fill(val, val + n, 0);
	}
	void modify(int id, ll v) {
		for (id++; id <= n; id += (id & -id)) val[id] += v;
	}
	ll query(int id) {
		ll ans = 0;
		for (; id > 0; id -= (id & -id)) ans += val[id];
		return ans;
	}
} B;

void PUT_TREE() {
	FOR(i, 0, m) {
		int pp = lower_bound(a, a + n, b[i]) - a - 1;
		if (pp == -1) pp += n;
		int x = (b[i] - a[pp] + L) % L;
		debug(i, pp, x);
		tr[pp].insert(x);
	}
}

void GET_P() {
	vector<pii> v;
	FOR(i, 0, n) v.push_back(mp(a[i], i));
	FOR(i, 0, n) v.push_back(mp(a[i] + L, i));
	FOR(i, 0, n) {
		auto pp = prev(lower_bound(v.begin(), v.end(), mp(a[i] + L - adf % L, MXN)));
		p[i] = pp -> sc;
		pt[i] = adf / L * L + (a[i] + L - pp -> fs);
		debug(i, p[i], pt[i]);
		edge[p[i]].push_back(mp(pt[i], i));
	}
}

void CALC_CYC(vector<ll> &v, vector<pair<ll, int>> &vq, ll C) {
	int n = v.size(), m = vq.size();
	vector<ll> p(1, 0), pc(1, 0);
	for (auto &i : v) {
		p.push_back(p.back() + i);
		pc.push_back(pc.back() + (C - i) % C);
	}
	B.init(n);
	vector<pair<ll, int>> dist;
	FOR(i, 0, n) dist.push_back(mp(C - (C - v[i]) % C - 1, i));
	FOR(i, 0, m) dist.push_back(mp(vq[i].fs % C, -i - 1));
	sort(dist.begin(), dist.end());
	for (auto &[t, id] : dist) {
		if (id < 0) {
			id = -id - 1;
			auto [Q, aid] = vq[id];
			int s = lower_bound(v.begin(), v.end(), Q) - v.begin();
			if (s == 0) continue;
			ll x = Q * s - p[s] - (pc[s] + t * s + B.query(s));
			debug(Q, s, aid, x / C);
			ans[aid] += x / C + s;
		} else {
			B.modify(id, -C);
		}
	}
}

namespace JELLY {
	void MERGE(int rt, int id, ll w) {
		if (tr[rt].size() >= tr[id].size()) {
			for (auto i : tr[id]) tr[rt].insert(i + lz[id] + w - lz[rt]);
		} else {
			lz[id] += w;
			for (auto i : tr[rt]) tr[id].insert(i + lz[rt] - w);
			swap(tr[rt], tr[id]);
			swap(lz[rt], lz[id]);
		}
		tr[id].clear();
	}
	void DFS(int id) {
		vis[id] = true;
		for (auto &[w, i] : edge[id]) {
			if (vis[i]) continue;
			DFS(i);
		}
	}
	void GET_SR() {
		FOR(i, 0, n) {
			if (vis[i]) continue;
			sr.insert(i);
			DFS(i);
		}
	}
	void CALC_MERGE(int id, bool f = true) {
		vis[id] = false;
		for (auto &[w, i] : edge[id]) {
			if (!vis[i]) continue;
			CALC_MERGE(i);
			MERGE(id, i, w);
		}
		if (f) {
			for (auto &i : qry[id]) {
				ll Q = qt[i] - lz[id];
				int x = tr[id].order_of_key(Q + 1);
				debug(i, x);
				ans[i] += x;
			}
		}
	}
	void SOLVE(int rt) {
		debug(rt);
		CALC_MERGE(rt, false);
		vector<ll> v;
		for (auto i : tr[rt]) v.push_back(i + lz[rt]);
		vector<pair<ll, int>> vq;
		vector<int> cyc;
		cyc.push_back(rt);
		while (p[cyc.back()] != rt) cyc.push_back(p[cyc.back()]);
		int acc = 0;
		FOR(i, 0, cyc.size()) {
			debug(cyc[i]);
			for (auto &j : qry[cyc[i]]) {
				debug(j);
				vq.push_back(mp(qt[j] - acc, j));
			}
			acc += pt[cyc[i]];
		}
		CALC_CYC(v, vq, acc);
	}
}

void miku() {
	cin >> n >> m >> L >> adf;
	FOR(i, 0, n) cin >> a[i];
	FOR(i, 0, m) cin >> b[i];
	cin >> q;
	FOR(i, 0, q) {
		cin >> qid[i] >> qt[i];
		qid[i]--;
		qry[qid[i]].push_back(i);
	}
	PUT_TREE();
	GET_P();
	JELLY::GET_SR();
	for (auto &i : sr.v) {
		debug(i);
		JELLY::SOLVE(i);
	}
	FOR(i, 0, q) cout << ans[i] << '\n';
}

int32_t main() {
	cin.tie(0) -> sync_with_stdio(false);
	cin.exceptions(cin.failbit);
	miku();
	return 0;
}

Compilation message (stderr)

harvest.cpp: In function 'void PUT_TREE()':
harvest.cpp:13:20: warning: statement has no effect [-Wunused-value]
   13 | #define debug(...) 39
      |                    ^~
harvest.cpp:76:3: note: in expansion of macro 'debug'
   76 |   debug(i, pp, x);
      |   ^~~~~
harvest.cpp: In function 'void GET_P()':
harvest.cpp:13:20: warning: statement has no effect [-Wunused-value]
   13 | #define debug(...) 39
      |                    ^~
harvest.cpp:89:3: note: in expansion of macro 'debug'
   89 |   debug(i, p[i], pt[i]);
      |   ^~~~~
harvest.cpp: In function 'void CALC_CYC(std::vector<long long int>&, std::vector<std::pair<long long int, long long int> >&, ll)':
harvest.cpp:13:20: warning: statement has no effect [-Wunused-value]
   13 | #define debug(...) 39
      |                    ^~
harvest.cpp:113:4: note: in expansion of macro 'debug'
  113 |    debug(Q, s, aid, x / C);
      |    ^~~~~
harvest.cpp: In function 'void JELLY::CALC_MERGE(long long int, bool)':
harvest.cpp:13:20: warning: statement has no effect [-Wunused-value]
   13 | #define debug(...) 39
      |                    ^~
harvest.cpp:158:5: note: in expansion of macro 'debug'
  158 |     debug(i, x);
      |     ^~~~~
harvest.cpp: In function 'void JELLY::SOLVE(long long int)':
harvest.cpp:13:20: warning: statement has no effect [-Wunused-value]
   13 | #define debug(...) 39
      |                    ^~
harvest.cpp:164:3: note: in expansion of macro 'debug'
  164 |   debug(rt);
      |   ^~~~~
harvest.cpp:13:20: warning: statement has no effect [-Wunused-value]
   13 | #define debug(...) 39
      |                    ^~
harvest.cpp:174:4: note: in expansion of macro 'debug'
  174 |    debug(cyc[i]);
      |    ^~~~~
harvest.cpp:13:20: warning: statement has no effect [-Wunused-value]
   13 | #define debug(...) 39
      |                    ^~
harvest.cpp:176:5: note: in expansion of macro 'debug'
  176 |     debug(j);
      |     ^~~~~
harvest.cpp: In function 'void miku()':
harvest.cpp:13:20: warning: statement has no effect [-Wunused-value]
   13 | #define debug(...) 39
      |                    ^~
harvest.cpp:199:3: note: in expansion of macro 'debug'
  199 |   debug(i);
      |   ^~~~~

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