oj.uz

Submission #223574

# Submission time Handle Problem Language Result Execution time Memory
223574 2020-04-15T13:43:02 Z gs14004 Harvest (JOI20_harvest) C++17
5 / 100
 5000 ms 22836 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;

int n, m, q, l, c;
vector<pi> v[MAXN];
vector<pi> gph[MAXN];
vector<int> 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;
}

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; indeg[j]; j=nxt[j]){
				cyclen[j] = tot;
				indeg[j] = 0;
			}
		}
	}
	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 'int main()':
harvest.cpp:71: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:74:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&a[i]);
   ~~~~~^~~~~~~~~~~~
harvest.cpp:79:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&b[i]);
   ~~~~~^~~~~~~~~~~~
harvest.cpp:89:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&q);
  ~~~~~^~~~~~~~~
harvest.cpp:93: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 33 ms 14848 KB Output is correct
2 Correct 36 ms 15232 KB Output is correct
3 Correct 132 ms 15096 KB Output is correct
4 Correct 39 ms 15104 KB Output is correct
5 Correct 75 ms 15232 KB Output is correct
6 Correct 76 ms 15232 KB Output is correct
7 Correct 77 ms 15232 KB Output is correct
8 Correct 32 ms 15104 KB Output is correct
9 Correct 32 ms 15104 KB Output is correct
10 Correct 33 ms 15104 KB Output is correct
11 Correct 34 ms 15104 KB Output is correct
12 Correct 130 ms 15232 KB Output is correct
13 Correct 242 ms 15332 KB Output is correct
14 Correct 85 ms 15228 KB Output is correct
15 Correct 58 ms 15224 KB Output is correct
16 Correct 58 ms 15104 KB Output is correct
17 Correct 55 ms 15104 KB Output is correct
18 Correct 59 ms 15104 KB Output is correct
19 Correct 60 ms 15224 KB Output is correct
20 Correct 62 ms 15104 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 14848 KB Output is correct
2 Correct 36 ms 15232 KB Output is correct
3 Correct 132 ms 15096 KB Output is correct
4 Correct 39 ms 15104 KB Output is correct
5 Correct 75 ms 15232 KB Output is correct
6 Correct 76 ms 15232 KB Output is correct
7 Correct 77 ms 15232 KB Output is correct
8 Correct 32 ms 15104 KB Output is correct
9 Correct 32 ms 15104 KB Output is correct
10 Correct 33 ms 15104 KB Output is correct
11 Correct 34 ms 15104 KB Output is correct
12 Correct 130 ms 15232 KB Output is correct
13 Correct 242 ms 15332 KB Output is correct
14 Correct 85 ms 15228 KB Output is correct
15 Correct 58 ms 15224 KB Output is correct
16 Correct 58 ms 15104 KB Output is correct
17 Correct 55 ms 15104 KB Output is correct
18 Correct 59 ms 15104 KB Output is correct
19 Correct 60 ms 15224 KB Output is correct
20 Correct 62 ms 15104 KB Output is correct
21 Execution timed out 5097 ms 22836 KB Time limit exceeded
22 Halted 0 ms 0 KB -