oj.uz

Submission #223594

# Submission time Handle Problem Language Result Execution time Memory
223594 2020-04-15T14:32:39 Z gs14004 Harvest (JOI20_harvest) C++17
5 / 100
 5000 ms 20724 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{
	int tree[MAXN];
	void add(int x, int v){
		for(int i=x+1; i<MAXN; i+=i&-i){
			tree[i] += v;
		}
	}
	int query(int x){
		int 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];

bool vis[MAXN];
lint dfs(int x, lint d, lint isCycle){
	if(vis[x]) return 0;
	vis[x] = 1;
	lint ret = 0;
	for(auto &j : deliv[x]){
		if(d >= j){
			ret += 1;
			if(isCycle) ret += (d - j) / isCycle;
		}
	}
	for(auto &[w, v] : gph[x]){
		ret += dfs(v, d - w, isCycle);
	}
	return ret;
}

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++){
		for(auto &j : v[i]){
			memset(vis, 0, sizeof(vis));
			ans[j.second] += dfs(i, j.first, cyclen[i]);
		}
	}
}

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:119:26: warning: unused variable 'pos' [-Wunused-variable]
     for(auto &[pos, thres] : pinst) crd.push_back(thres);
                          ^
harvest.cpp:122:26: warning: unused variable 'pos' [-Wunused-variable]
     for(auto &[pos, thres] : pinst){
                          ^
harvest.cpp: In function 'int main()':
harvest.cpp:162: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:165:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&a[i]);
   ~~~~~^~~~~~~~~~~~
harvest.cpp:170:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&b[i]);
   ~~~~~^~~~~~~~~~~~
harvest.cpp:180:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&q);
  ~~~~~^~~~~~~~~
harvest.cpp:184: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 32 ms 14848 KB Output is correct
2 Correct 35 ms 15104 KB Output is correct
3 Correct 130 ms 15096 KB Output is correct
4 Correct 41 ms 15436 KB Output is correct
5 Correct 70 ms 15900 KB Output is correct
6 Correct 70 ms 15780 KB Output is correct
7 Correct 71 ms 15780 KB Output is correct
8 Correct 35 ms 15284 KB Output is correct
9 Correct 39 ms 15324 KB Output is correct
10 Correct 36 ms 15308 KB Output is correct
11 Correct 39 ms 15480 KB Output is correct
12 Correct 154 ms 15224 KB Output is correct
13 Correct 261 ms 15224 KB Output is correct
14 Correct 96 ms 15232 KB Output is correct
15 Correct 53 ms 15656 KB Output is correct
16 Correct 52 ms 15600 KB Output is correct
17 Correct 53 ms 15536 KB Output is correct
18 Correct 58 ms 15540 KB Output is correct
19 Correct 58 ms 15544 KB Output is correct
20 Correct 58 ms 15540 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 14848 KB Output is correct
2 Correct 35 ms 15104 KB Output is correct
3 Correct 130 ms 15096 KB Output is correct
4 Correct 41 ms 15436 KB Output is correct
5 Correct 70 ms 15900 KB Output is correct
6 Correct 70 ms 15780 KB Output is correct
7 Correct 71 ms 15780 KB Output is correct
8 Correct 35 ms 15284 KB Output is correct
9 Correct 39 ms 15324 KB Output is correct
10 Correct 36 ms 15308 KB Output is correct
11 Correct 39 ms 15480 KB Output is correct
12 Correct 154 ms 15224 KB Output is correct
13 Correct 261 ms 15224 KB Output is correct
14 Correct 96 ms 15232 KB Output is correct
15 Correct 53 ms 15656 KB Output is correct
16 Correct 52 ms 15600 KB Output is correct
17 Correct 53 ms 15536 KB Output is correct
18 Correct 58 ms 15540 KB Output is correct
19 Correct 58 ms 15544 KB Output is correct
20 Correct 58 ms 15540 KB Output is correct
21 Execution timed out 5070 ms 20724 KB Time limit exceeded
22 Halted 0 ms 0 KB -