oj.uz

Submission #224177

# Submission time Handle Problem Language Result Execution time Memory
224177 2020-04-17T11:11:15 Z gs14004 Harvest (JOI20_harvest) C++17
0 / 100
 715 ms 70588 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, int 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, int 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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 38144 KB Output is correct
2 Correct 32 ms 38400 KB Output is correct
3 Correct 262 ms 39160 KB Output is correct
4 Correct 255 ms 39236 KB Output is correct
5 Correct 310 ms 39580 KB Output is correct
6 Correct 302 ms 39580 KB Output is correct
7 Correct 305 ms 39676 KB Output is correct
8 Correct 250 ms 39084 KB Output is correct
9 Correct 283 ms 39124 KB Output is correct
10 Correct 330 ms 39236 KB Output is correct
11 Correct 328 ms 39160 KB Output is correct
12 Correct 206 ms 39320 KB Output is correct
13 Incorrect 281 ms 39140 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 426 ms 47008 KB Output is correct
2 Incorrect 715 ms 70588 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 38144 KB Output is correct
2 Correct 32 ms 38400 KB Output is correct
3 Correct 262 ms 39160 KB Output is correct
4 Correct 255 ms 39236 KB Output is correct
5 Correct 310 ms 39580 KB Output is correct
6 Correct 302 ms 39580 KB Output is correct
7 Correct 305 ms 39676 KB Output is correct
8 Correct 250 ms 39084 KB Output is correct
9 Correct 283 ms 39124 KB Output is correct
10 Correct 330 ms 39236 KB Output is correct
11 Correct 328 ms 39160 KB Output is correct
12 Correct 206 ms 39320 KB Output is correct
13 Incorrect 281 ms 39140 KB Output isn't correct
14 Halted 0 ms 0 KB -