oj.uz

Submission #224178

# Submission time Handle Problem Language Result Execution time Memory
224178 2020-04-17T11:12:21 Z gs14004 Harvest (JOI20_harvest) C++17
5 / 100
 5000 ms 99224 KB 
#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
using namespace std;
using lint = long long;
using pi = pair<lint, lint>;
const int MAXN = 400005;

struct b1{
	lint tree[MAXN];
	void add(int x, lint v){
		for(int i=x+1; i<MAXN; i+=i&-i){
			tree[i] += v;
		}
	}
	lint query(int x){
		lint ret = 0;
		for(int i=x+1; i; i-=i&-i){
			ret += tree[i];
		}
		return ret;
	}
}b1, b2;

struct fuck{
	vector<lint> tree[MAXN];
	void add(int x, lint v, int arg){
		for(int i=x+1; i<MAXN; i+=i&-i){
			if(arg == 1) tree[i].insert(lower_bound(all(tree[i]), v), v);
			else tree[i].erase(lower_bound(all(tree[i]), v));
		}
	}
	int query(int x, lint y){
		int ret = 0;
		for(int i=x+1; i; i-=i&-i){
			ret += upper_bound(all(tree[i]), y) - tree[i].begin();
		}
		return ret;
	}
}fuck;

int n, m, q, l, c;
vector<pi> v[MAXN];
vector<pi> gph[MAXN];
vector<lint> deliv[MAXN];
int nxt[MAXN]; lint len[MAXN];
lint cyclen[MAXN], ans[MAXN];

void solve(vector<int> vtx){
	lint L = cyclen[vtx[0]];
	vector<lint> sum(sz(vtx));
	vector<lint> crd;
	for(int i=sz(vtx)-1; i>=0; i--){
		sum[i] = (i+1 < sz(vtx) ? sum[i+1] : 0) + len[vtx[i]];
		for(auto &j : deliv[vtx[i]]){
			crd.push_back(j + sum[i]);
			crd.push_back(j + L + sum[i]);
		}
	}
	sort(all(crd));
	crd.resize(unique(all(crd)) - crd.begin());
	auto ADD = [&](lint x){
		int pos = lower_bound(all(crd), x) - crd.begin();
		b1.add(pos, +1);
		b2.add(pos, -(x/L));
		fuck.add(pos, L - x % L, +1);
	};
	auto REM = [&](lint x){
		int pos = lower_bound(all(crd), x) - crd.begin();
		b1.add(pos, -1);
		b2.add(pos, +x/L);
		fuck.add(pos, L - x % L, -1);
	};
	for(int i=sz(vtx)-1; i>=0; i--){
		sum[i] = (i+1 < sz(vtx) ? sum[i+1] : 0) + len[vtx[i]];
		for(auto &j : deliv[vtx[i]]){
			ADD(j + L + sum[i]);
		}
	}
	for(int i=0; i<sz(vtx); i++){
		for(auto &j : deliv[vtx[i]]){
			REM(j + L + sum[i]);
			ADD(j + sum[i]);
		}
		for(auto &[d, idx] : v[vtx[i]]){
			int j = lower_bound(all(crd), d + sum[i] + 1) - crd.begin();
			int cnt = b1.query(j - 1);
			ans[idx] += b2.query(j - 1);
			ans[idx] -= fuck.query(j - 1, L - 1 - (d + sum[i]) % L);
			ans[idx] += (1 + (d + sum[i]) / L) * cnt;
		}
	}
	for(int i=sz(vtx)-1; i>=0; i--){
		for(auto &j : deliv[vtx[i]]){
			REM(j + sum[i]);
		}
	}
}

struct query{
	int st, ed;
	lint x; int idx;
};

lint dep[MAXN];
int din[MAXN], dout[MAXN], piv;

void dfs(int x, vector<pi> &pinst, vector<query> &qinst){
	din[x] = ++piv;
	for(auto &i : deliv[x]){
		pinst.emplace_back(din[x], dep[x] + i);
	}
	for(auto &[w, v] : gph[x]){
		dep[v] = dep[x] + w;
		dfs(v, pinst, qinst);
	}
	dout[x] = piv;
	for(auto &[thres, idx] : v[x]){
		qinst.push_back({din[x], dout[x], thres + dep[x], (int)idx});
	}
	deliv[x].clear();
}


void solve(){
	vector<int> indeg(n);
	for(int i=0; i<n; i++){
		gph[nxt[i]].emplace_back(len[i], i);
		indeg[nxt[i]]++;
	}
	queue<int> que;
	for(int i=0; i<n; i++){
		if(!indeg[i]){
			que.push(i);
		}
	}
	while(sz(que)){
		int i = que.front();
		que.pop();
		indeg[nxt[i]]--;
		if(indeg[nxt[i]] == 0) que.push(nxt[i]);
	}
	for(int i=0; i<n; i++){
		if(indeg[i]){
			lint tot = len[i];
			for(int j=nxt[i]; j!=i; j=nxt[j]) tot += len[j];
			for(int j=i; !cyclen[j]; j=nxt[j]){
				cyclen[j] = tot;
			}
		}
	}
	for(int i=0; i<n; i++){
		if(indeg[i]){
			vector<pi> pinst;
			vector<query> qinst;
			for(auto &[w, v] : gph[i]){
				if(indeg[v]) continue;
				dep[v] = w;
				dfs(v, pinst, qinst);
			}
			for(auto &j : pinst){
				deliv[i].push_back(j.second);
			}
			{
				vector<lint> crd;
				for(auto &[pos, thres] : pinst) crd.push_back(thres);
				sort(all(crd));
				crd.resize(unique(all(crd)) - crd.begin());
				for(auto &[pos, thres] : pinst){
					thres = lower_bound(all(crd), thres) - crd.begin();
				}
				sort(all(pinst));
				sort(all(qinst), [&](const query &a, const query &b){
					return a.st < b.st;
				});
				int p = 0;
				for(auto &i : qinst){
					while(p < sz(pinst) && pinst[p].first < i.st){
						b1.add(pinst[p++].second, +1);
					}
					int pos = upper_bound(all(crd), i.x) - crd.begin();
					ans[i.idx] -= b1.query(pos - 1);
				}
				for(int i=0; i<p; i++) b1.add(pinst[i].second, -1);
				p = 0;
				sort(all(qinst), [&](const query &a, const query &b){
					return a.ed < b.ed;
				});
				for(auto &i : qinst){
					while(p < sz(pinst) && pinst[p].first <= i.ed){
						b1.add(pinst[p++].second, +1);
					}
					int pos = upper_bound(all(crd), i.x) - crd.begin();
					ans[i.idx] += b1.query(pos - 1);
				}
				for(int i=0; i<p; i++) b1.add(pinst[i].second, -1);
			}
		}
	}
	for(int i=0; i<n; i++){
		if(!indeg[i]) continue;
		vector<int> vtx;
		for(int j=i; indeg[j]; j=nxt[j]){
			vtx.push_back(j);
			indeg[j] = 0;
		}
		solve(vtx);
	}
}

int main(){
	scanf("%d %d %d %d",&n,&m,&l,&c);
	vector<int> a(n), b(m), idx(n);
	for(int i=0; i<n; i++){
		scanf("%d",&a[i]);
		a[i] = (l - a[i]) % l;
		idx[i] = i;
	}
	for(int i=0; i<m; i++){
		scanf("%d",&b[i]);
		b[i] = (l - b[i]) % l;
	}
	reverse(all(a));
	reverse(all(idx));
	reverse(all(b));
	if(a.back() == 0){
		rotate(a.begin(), a.end() - 1, a.end());
		rotate(idx.begin(), idx.end() - 1, idx.end());
	}
	scanf("%d",&q);
	for(int i=0; i<q; i++){
		int x;
		lint t; 
		scanf("%d %lld",&x,&t);
		x = idx[x - 1];
		v[x].emplace_back(t, i);
	}
	for(int i=0; i<n; i++){
		int nxtpos = (c + a[i]) % l;
		nxt[i] = lower_bound(all(a), nxtpos) - a.begin();
		lint newpos = (c + a[i]) + (nxt[i] == n ? (a[0] + l) : a[nxt[i]]) - nxtpos;
		len[i] = newpos - a[i];
		if(nxt[i] == n) nxt[i] = 0;
	}
	for(int i=0; i<m; i++){
		int nxt = lower_bound(all(a), b[i]) - a.begin();
		if(nxt == n) nxt = 0;
		int delay = (a[nxt] - b[i] + l) % l;
		deliv[nxt].push_back(delay);
	}
	solve();
	for(int i=0; i<q; i++) printf("%lld\n", ans[i]);
}

Compilation message

harvest.cpp: In function 'void solve()':
harvest.cpp:166:26: warning: unused variable 'pos' [-Wunused-variable]
     for(auto &[pos, thres] : pinst) crd.push_back(thres);
                          ^
harvest.cpp:169:26: warning: unused variable 'pos' [-Wunused-variable]
     for(auto &[pos, thres] : pinst){
                          ^
harvest.cpp: In function 'int main()':
harvest.cpp:212:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d %d",&n,&m,&l,&c);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
harvest.cpp:215:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&a[i]);
   ~~~~~^~~~~~~~~~~~
harvest.cpp:220:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&b[i]);
   ~~~~~^~~~~~~~~~~~
harvest.cpp:230:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&q);
  ~~~~~^~~~~~~~~
harvest.cpp:234:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %lld",&x,&t);
   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 38144 KB Output is correct
2 Correct 36 ms 38392 KB Output is correct
3 Correct 275 ms 39160 KB Output is correct
4 Correct 246 ms 39232 KB Output is correct
5 Correct 304 ms 39708 KB Output is correct
6 Correct 300 ms 39740 KB Output is correct
7 Correct 311 ms 39596 KB Output is correct
8 Correct 259 ms 39212 KB Output is correct
9 Correct 288 ms 39124 KB Output is correct
10 Correct 326 ms 39112 KB Output is correct
11 Correct 329 ms 39160 KB Output is correct
12 Correct 205 ms 39160 KB Output is correct
13 Correct 214 ms 39160 KB Output is correct
14 Correct 129 ms 39032 KB Output is correct
15 Correct 276 ms 39592 KB Output is correct
16 Correct 276 ms 39592 KB Output is correct
17 Correct 281 ms 39720 KB Output is correct
18 Correct 309 ms 39468 KB Output is correct
19 Correct 315 ms 39472 KB Output is correct
20 Correct 325 ms 39468 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 441 ms 46940 KB Output is correct
2 Correct 675 ms 64188 KB Output is correct
3 Correct 350 ms 64504 KB Output is correct
4 Correct 501 ms 65968 KB Output is correct
5 Correct 575 ms 99224 KB Output is correct
6 Correct 599 ms 99056 KB Output is correct
7 Correct 587 ms 71304 KB Output is correct
8 Correct 606 ms 71132 KB Output is correct
9 Execution timed out 5093 ms 62840 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 38144 KB Output is correct
2 Correct 36 ms 38392 KB Output is correct
3 Correct 275 ms 39160 KB Output is correct
4 Correct 246 ms 39232 KB Output is correct
5 Correct 304 ms 39708 KB Output is correct
6 Correct 300 ms 39740 KB Output is correct
7 Correct 311 ms 39596 KB Output is correct
8 Correct 259 ms 39212 KB Output is correct
9 Correct 288 ms 39124 KB Output is correct
10 Correct 326 ms 39112 KB Output is correct
11 Correct 329 ms 39160 KB Output is correct
12 Correct 205 ms 39160 KB Output is correct
13 Correct 214 ms 39160 KB Output is correct
14 Correct 129 ms 39032 KB Output is correct
15 Correct 276 ms 39592 KB Output is correct
16 Correct 276 ms 39592 KB Output is correct
17 Correct 281 ms 39720 KB Output is correct
18 Correct 309 ms 39468 KB Output is correct
19 Correct 315 ms 39472 KB Output is correct
20 Correct 325 ms 39468 KB Output is correct
21 Correct 441 ms 46940 KB Output is correct
22 Correct 675 ms 64188 KB Output is correct
23 Correct 350 ms 64504 KB Output is correct
24 Correct 501 ms 65968 KB Output is correct
25 Correct 575 ms 99224 KB Output is correct
26 Correct 599 ms 99056 KB Output is correct
27 Correct 587 ms 71304 KB Output is correct
28 Correct 606 ms 71132 KB Output is correct
29 Execution timed out 5093 ms 62840 KB Time limit exceeded
30 Halted 0 ms 0 KB -