oj.uz

Submission #223821

# Submission time Handle Problem Language Result Execution time Memory
223821 2020-04-16T14:05:16 Z gs14004 Harvest (JOI20_harvest) C++17
5 / 100
 5000 ms 23008 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]]){
			for(auto &j : ms){
				if(d + sum[i] >= j){
					ans[idx] += 1 + (d + sum[i] - j) / L;
				}
			}
		}
	}
}

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:127:26: warning: unused variable 'pos' [-Wunused-variable]
     for(auto &[pos, thres] : pinst) crd.push_back(thres);
                          ^
harvest.cpp:130:26: warning: unused variable 'pos' [-Wunused-variable]
     for(auto &[pos, thres] : pinst){
                          ^
harvest.cpp: In function 'int main()':
harvest.cpp:173: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:176:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&a[i]);
   ~~~~~^~~~~~~~~~~~
harvest.cpp:181:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&b[i]);
   ~~~~~^~~~~~~~~~~~
harvest.cpp:191:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&q);
  ~~~~~^~~~~~~~~
harvest.cpp:195: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 14848 KB Output is correct
2 Correct 17 ms 14976 KB Output is correct
3 Correct 123 ms 15096 KB Output is correct
4 Correct 20 ms 15232 KB Output is correct
5 Correct 18 ms 15616 KB Output is correct
6 Correct 18 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 17 ms 15232 KB Output is correct
10 Correct 18 ms 15232 KB Output is correct
11 Correct 19 ms 15232 KB Output is correct
12 Correct 106 ms 15096 KB Output is correct
13 Correct 121 ms 15096 KB Output is correct
14 Correct 73 ms 15096 KB Output is correct
15 Correct 19 ms 15488 KB Output is correct
16 Correct 18 ms 15488 KB Output is correct
17 Correct 18 ms 15488 KB Output is correct
18 Correct 18 ms 15488 KB Output is correct
19 Correct 18 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 5074 ms 23008 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 14848 KB Output is correct
2 Correct 17 ms 14976 KB Output is correct
3 Correct 123 ms 15096 KB Output is correct
4 Correct 20 ms 15232 KB Output is correct
5 Correct 18 ms 15616 KB Output is correct
6 Correct 18 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 17 ms 15232 KB Output is correct
10 Correct 18 ms 15232 KB Output is correct
11 Correct 19 ms 15232 KB Output is correct
12 Correct 106 ms 15096 KB Output is correct
13 Correct 121 ms 15096 KB Output is correct
14 Correct 73 ms 15096 KB Output is correct
15 Correct 19 ms 15488 KB Output is correct
16 Correct 18 ms 15488 KB Output is correct
17 Correct 18 ms 15488 KB Output is correct
18 Correct 18 ms 15488 KB Output is correct
19 Correct 18 ms 15360 KB Output is correct
20 Correct 18 ms 15412 KB Output is correct
21 Execution timed out 5074 ms 23008 KB Time limit exceeded
22 Halted 0 ms 0 KB -