oj.uz

Submission #223832

# Submission time Handle Problem Language Result Execution time Memory
223832 2020-04-16T14:15:59 Z gs14004 Harvest (JOI20_harvest) C++17
5 / 100
 5000 ms 18660 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 = 200005;
const int MAXT = 530000;

struct bit{
	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;
	}
	void clear(){
		memset(tree, 0x3f, sizeof(tree));
	}
}bit;

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]];
	multiset<lint> ms;
	vector<lint> sum(sz(vtx));
	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]]){
			ms.insert(j + L + sum[i]);
		}
	}
	for(int i=0; i<sz(vtx); i++){
		for(auto &j : deliv[vtx[i]]){
			ms.erase(ms.find(j + L + sum[i]));
			ms.insert(j + sum[i]);
		}
		for(auto &[d, idx] : v[vtx[i]]){
			int cnt = 0;
			for(auto &j : ms){
				if(d + sum[i] < j) continue;
				if(d + sum[i] >= j){
					cnt += 1;
				}
				if(d + sum[i] >= j){
					ans[idx] -= j / L;
				}
				if(d + sum[i] >= j && (d + sum[i]) % L < j % L){
					ans[idx] -= 1;
				}
			}
			ans[idx] += (1 + (d + sum[i]) / L) * cnt;
		}
	}
}

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){
						bit.add(pinst[p++].second, +1);
					}
					int pos = upper_bound(all(crd), i.x) - crd.begin();
					ans[i.idx] -= bit.query(pos - 1);
				}
				for(int i=0; i<p; i++) bit.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){
						bit.add(pinst[p++].second, +1);
					}
					int pos = upper_bound(all(crd), i.x) - crd.begin();
					ans[i.idx] += bit.query(pos - 1);
				}
				for(int i=0; i<p; i++) bit.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:136:26: warning: unused variable 'pos' [-Wunused-variable]
     for(auto &[pos, thres] : pinst) crd.push_back(thres);
                          ^
harvest.cpp:139:26: warning: unused variable 'pos' [-Wunused-variable]
     for(auto &[pos, thres] : pinst){
                          ^
harvest.cpp: In function 'int main()':
harvest.cpp:182: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:185:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&a[i]);
   ~~~~~^~~~~~~~~~~~
harvest.cpp:190:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&b[i]);
   ~~~~~^~~~~~~~~~~~
harvest.cpp:200:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&q);
  ~~~~~^~~~~~~~~
harvest.cpp:204: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 14 ms 14592 KB Output is correct
2 Correct 17 ms 14976 KB Output is correct
3 Correct 208 ms 14976 KB Output is correct
4 Correct 21 ms 15232 KB Output is correct
5 Correct 18 ms 15616 KB Output is correct
6 Correct 19 ms 15616 KB Output is correct
7 Correct 19 ms 15652 KB Output is correct
8 Correct 19 ms 15232 KB Output is correct
9 Correct 18 ms 15232 KB Output is correct
10 Correct 19 ms 15232 KB Output is correct
11 Correct 18 ms 15232 KB Output is correct
12 Correct 108 ms 15096 KB Output is correct
13 Correct 201 ms 15096 KB Output is correct
14 Correct 118 ms 15096 KB Output is correct
15 Correct 19 ms 15488 KB Output is correct
16 Correct 19 ms 15488 KB Output is correct
17 Correct 19 ms 15488 KB Output is correct
18 Correct 18 ms 15360 KB Output is correct
19 Correct 19 ms 15360 KB Output is correct
20 Correct 18 ms 15412 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5089 ms 18660 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14592 KB Output is correct
2 Correct 17 ms 14976 KB Output is correct
3 Correct 208 ms 14976 KB Output is correct
4 Correct 21 ms 15232 KB Output is correct
5 Correct 18 ms 15616 KB Output is correct
6 Correct 19 ms 15616 KB Output is correct
7 Correct 19 ms 15652 KB Output is correct
8 Correct 19 ms 15232 KB Output is correct
9 Correct 18 ms 15232 KB Output is correct
10 Correct 19 ms 15232 KB Output is correct
11 Correct 18 ms 15232 KB Output is correct
12 Correct 108 ms 15096 KB Output is correct
13 Correct 201 ms 15096 KB Output is correct
14 Correct 118 ms 15096 KB Output is correct
15 Correct 19 ms 15488 KB Output is correct
16 Correct 19 ms 15488 KB Output is correct
17 Correct 19 ms 15488 KB Output is correct
18 Correct 18 ms 15360 KB Output is correct
19 Correct 19 ms 15360 KB Output is correct
20 Correct 18 ms 15412 KB Output is correct
21 Execution timed out 5089 ms 18660 KB Time limit exceeded
22 Halted 0 ms 0 KB -