oj.uz

Submission #224187

# Submission time Handle Problem Language Result Execution time Memory
224187 2020-04-17T11:50:27 Z gs14004 Harvest (JOI20_harvest) C++17
5 / 100
 5000 ms 96020 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<int> tree[MAXN];
	vector<lint> elem[MAXN];
	int SZ;
	void prepare(vector<pi> v){
		SZ = sz(v) + 2;
		for(auto &[x, y] : v){
			for(int i=x+1; i<SZ; i+=i&-i){
				elem[i].push_back(y);
			}
		}
		for(int i=0; i<SZ; i++){
			sort(all(elem[i]));
			elem[i].resize(unique(all(elem[i])) - elem[i].begin());
			tree[i].resize(sz(elem[i]) + 1);
		}
	}
	void add(int x, lint v, int arg){
		for(int i=x+1; i<SZ; i+=i&-i){
			auto lp = lower_bound(all(elem[i]), v) - elem[i].begin() + 1;
			for(int j=lp; j<sz(tree[i]); j+=j&-j){
				tree[i][j] += arg;
			}
		}
	}
	int query(int x, lint y){
		int ret = 0;
		for(int i=x+1; i; i-=i&-i){
			int pos = upper_bound(all(elem[i]), y) - elem[i].begin();
			for(int j=pos; j; j-=j&-j){
				ret += tree[i][j];
			}
		}
		return ret;
	}
	void clear(){
		for(int i=0; i<SZ; i++){
			tree[i].clear();
			elem[i].clear();
		}
	}
}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());
	vector<pi> preps;
	for(int i=0; i<sz(crd); i++){
		preps.emplace_back(i, L - crd[i] % L);
	}
	fuck.prepare(preps);
	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]);
		}
	}
	fuck.clear();
}

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:198:26: warning: unused variable 'pos' [-Wunused-variable]
     for(auto &[pos, thres] : pinst) crd.push_back(thres);
                          ^
harvest.cpp:201:26: warning: unused variable 'pos' [-Wunused-variable]
     for(auto &[pos, thres] : pinst){
                          ^
harvest.cpp: In function 'int main()':
harvest.cpp:244: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:247:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&a[i]);
   ~~~~~^~~~~~~~~~~~
harvest.cpp:252:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&b[i]);
   ~~~~~^~~~~~~~~~~~
harvest.cpp:262:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&q);
  ~~~~~^~~~~~~~~
harvest.cpp:266: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 34 ms 47616 KB Output is correct
2 Correct 37 ms 47864 KB Output is correct
3 Correct 42 ms 48888 KB Output is correct
4 Correct 44 ms 48972 KB Output is correct
5 Correct 44 ms 49308 KB Output is correct
6 Correct 43 ms 49316 KB Output is correct
7 Correct 45 ms 49332 KB Output is correct
8 Correct 49 ms 48948 KB Output is correct
9 Correct 45 ms 48980 KB Output is correct
10 Correct 44 ms 48964 KB Output is correct
11 Correct 45 ms 49024 KB Output is correct
12 Correct 70 ms 48888 KB Output is correct
13 Correct 75 ms 49272 KB Output is correct
14 Correct 58 ms 48504 KB Output is correct
15 Correct 49 ms 49064 KB Output is correct
16 Correct 56 ms 49192 KB Output is correct
17 Correct 44 ms 49064 KB Output is correct
18 Correct 43 ms 49076 KB Output is correct
19 Correct 44 ms 49080 KB Output is correct
20 Correct 44 ms 49076 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 56924 KB Output is correct
2 Correct 482 ms 73896 KB Output is correct
3 Correct 337 ms 67632 KB Output is correct
4 Correct 298 ms 69088 KB Output is correct
5 Correct 308 ms 96020 KB Output is correct
6 Correct 299 ms 95892 KB Output is correct
7 Correct 296 ms 74336 KB Output is correct
8 Correct 279 ms 74336 KB Output is correct
9 Execution timed out 5081 ms 65912 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 47616 KB Output is correct
2 Correct 37 ms 47864 KB Output is correct
3 Correct 42 ms 48888 KB Output is correct
4 Correct 44 ms 48972 KB Output is correct
5 Correct 44 ms 49308 KB Output is correct
6 Correct 43 ms 49316 KB Output is correct
7 Correct 45 ms 49332 KB Output is correct
8 Correct 49 ms 48948 KB Output is correct
9 Correct 45 ms 48980 KB Output is correct
10 Correct 44 ms 48964 KB Output is correct
11 Correct 45 ms 49024 KB Output is correct
12 Correct 70 ms 48888 KB Output is correct
13 Correct 75 ms 49272 KB Output is correct
14 Correct 58 ms 48504 KB Output is correct
15 Correct 49 ms 49064 KB Output is correct
16 Correct 56 ms 49192 KB Output is correct
17 Correct 44 ms 49064 KB Output is correct
18 Correct 43 ms 49076 KB Output is correct
19 Correct 44 ms 49080 KB Output is correct
20 Correct 44 ms 49076 KB Output is correct
21 Correct 207 ms 56924 KB Output is correct
22 Correct 482 ms 73896 KB Output is correct
23 Correct 337 ms 67632 KB Output is correct
24 Correct 298 ms 69088 KB Output is correct
25 Correct 308 ms 96020 KB Output is correct
26 Correct 299 ms 95892 KB Output is correct
27 Correct 296 ms 74336 KB Output is correct
28 Correct 279 ms 74336 KB Output is correct
29 Execution timed out 5081 ms 65912 KB Time limit exceeded
30 Halted 0 ms 0 KB -