oj.uz

Submission #431740

# Submission time Handle Problem Language Result Execution time Memory
431740 2021-06-17T14:56:58 Z oolimry Harvest (JOI20_harvest) C++17
0 / 100
 373 ms 106884 KB 
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int) (x).size()
#define all(x) (x).begin(), (x).end()
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
#define tern(cond, a, b) (cond ? a : b)
typedef long long lint;
typedef pair<int,int> ii;
 
lint n, m, L, T;
const int BUFF = 250000;
const int ROOT = 500000;
 
vector<lint> person;
lint apple[500005];
lint point[500005];
bool vis[500005];
 
lint getdis(int i){
	lint dis = person[i%BUFF] - person[point[i%BUFF]%BUFF];
	
	if(dis < T){
		dis += (T/L)*L;
	}
	while(dis < T) dis += L;
	return dis;
}
 
lint inf = 1e18 + 1e17;
map<lint,lint> infs;
 
vector<ii> adj[500005];
lint cyclesz[500005];
lint dis[500005];
lint low[500005];
lint high[500005];
lint maxval[500005];
lint total[500005];
lint rep[500005];
 
struct query{
	lint u, t, id, ans;
};
vector<query> queries;
 
vector<lint> stuff[500005];
lint toinf[500005];
lint sumreps[500005];
vector<lint> allreps;
vector<lint> mods[500005];
 
lint ppcnt = 0;
void dfs(lint u, int p = -1){
	low[u] = high[u] = ppcnt++;
	for(ii e : adj[u]){
		lint v = e.first, w = e.second;
		if(v == p) continue;
		dis[v] = dis[u] + w;
		
		if(u == ROOT){
			rep[v] = v;
			allreps.push_back(v);
		}
		else rep[v] = rep[u];
		
		dfs(v, u);
		high[u] = max(high[u], high[v]);
	}
}
 
void dfs2(lint u, int p = -1){
	for(ii e : adj[u]){
		lint v = e.first;
		if(v == p) continue;
		dfs2(v, u);
		maxval[u] = max(maxval[u], maxval[v]);
		total[u] += total[v];
	}
}
 
const int N = (1<<19);
vector<lint> tree[2*N];
 
inline void addshit(int u, lint t){
	t += dis[u];
	//show2(u, t);
	maxval[u] = max(maxval[u], t);
	stuff[rep[u]].push_back(t);
	total[u]++;
	for(int i = low[u] + N;i > 0;i >>= 1) tree[i].push_back(t);
}
inline void getready(){
	for(int i = 0;i < 2*N;i++) sort(all(tree[i]));
}
inline lint get(vector<lint> &v, lint t){
	return (lint)(upper_bound(all(v), t) - v.begin());
}
inline lint shitquery(int u, lint t){
	lint res = 0;
	for(int l = low[u]+N, r = high[u]+N+1;l < r;l >>= 1, r >>= 1){
		if(l&1) res += get(tree[l++], t);
		if(r&1) res += get(tree[--r], t);
	}
	return res;
}
 
vector<lint> disshit;
int getshit(lint i){
	int pos = upper_bound(all(disshit), i) - disshit.begin() + 2;
	return pos;
}
 
vector<lint> history;
lint ft[1400005];
void unshitupdate(int i){
	i = getshit(i);
	if(i == 0) return;
	history.push_back(i);
	for(;i <= 1400001;i += i&(-i)){
		ft[i]++;
	}
}
lint unshitquery(int i){
	i = getshit(i);
	int res = 0;
	for(;i > 0;i -= i&(-i)) res += ft[i];
	return res;
}
void undoall(){
	while(not history.empty()){
		int i = history.back();
		history.pop_back();
		if(i == 0) continue;
		for(;i <= 1400001;i += i&(-i)){
			ft[i] = 0;
		}
	}
}
 
int main(){
	//freopen("i.txt","r",stdin);
	ios_base::sync_with_stdio(false); cin.tie(0);
	
	memset(point, -1, sizeof(point));
	cin >> n >> m >> L >> T;
	
	person.resize(n);
	for(int i = 0;i < n;i++) cin >> person[i];
	for(int i = 0;i < m;i++) cin >> apple[i];
	
	for(int i = 0;i < n;i++){
		auto it = upper_bound(all(person), person[i] - (T%L));
		if(it == person.begin()) it = upper_bound(all(person), person[i] - (T%L) + L);
		
		it--;
		point[i] = it - person.begin();
		point[i+BUFF] = point[i]+BUFF;
	}
	
	for(int i = 0;i < n;i++){
		set<int> cur;
		int u = i;
		int cycle = -1;
		
		while(true){
			if(cur.find(u) != cur.end()) cycle = u;
			cur.insert(u);
			if(vis[u]) break;
			vis[u] = true;
			u = point[u];
		}
		
		if(cycle == -1) continue;
		
		
		lint totaldis = 0;
		u = cycle;
		vector<int> nodes;
		while(true){
			nodes.push_back(u);
			totaldis += getdis(u);
			u = point[u];
			if(u == cycle) break;
		}
		
		for(int x : nodes){
			cyclesz[x] = totaldis;
			cyclesz[x+BUFF] = totaldis;
		}
		
		point[cycle] += BUFF;
		point[cycle+BUFF] = ROOT;
	}
	
	
	for(int i = 0;i <= ROOT;i++){
		if(point[i] == -1) continue;
		
		
		if(point[i] == ROOT) adj[ROOT].push_back(ii(i, 0));
		else{
			lint dis = getdis(i);
			adj[point[i]].push_back(ii(i, dis));
			
		}
	}
	
	dfs(ROOT);
	
	for(int i = 0;i < m;i++){
		auto it = lower_bound(all(person), apple[i]);
		if(it == person.begin()) it = person.end();
		it--;
		int x = it - person.begin();
		
		
		lint t = apple[i] - person[x];
		if(t < 0) t += L;
		addshit(x, t);
	}
	
	getready();
	dfs2(ROOT);
	
	for(lint r : allreps){
		//show(r);
		for(lint x : stuff[r]){
			lint MM = cyclesz[r];
			lint I = inf;
			I /= MM;
			I *= MM;
			infs[MM] = I;
			
			disshit.push_back(x % MM);
			
			lint hm = (I-x)/MM + 1;
			
			sumreps[r] += hm;
			//show(hm);
			mods[r].push_back(x%MM);
			
		}
		sort(all(mods[r]));
		sort(all(stuff[r]));
	}
	
	
	
	
	
	//show(inf);
	int Q; cin >> Q;
	for(int q = 0;q < Q;q++){
		lint u, t; cin >> u >> t;
		queries.push_back({u-1,t,q,0});
	}
	
	sort(all(disshit));
	disshit.erase(unique(all(disshit)), disshit.end());
	
	sort(all(queries), [&](query a, query b){
		if(rep[a.u] == rep[b.u]) return a.t < b.t;
		else return rep[a.u] < rep[b.u];
	});
	
	lint prevrep = -1;
	lint sumofshit = 0;
	lint shitcnt = 0;
	int ptr = 0;
	
	for(query &q : queries){
		lint u = q.u, t = q.t;
		lint ans = 0;
		
		if(rep[u] != prevrep){
			prevrep = rep[u];
			undoall();
			sumofshit = 0;
			shitcnt = 0;
			ptr = 0;
		}
 
		ans += shitquery(u, t+dis[u]);
		
		if(cyclesz[u+BUFF] != 0){
			t += dis[u+BUFF];
			lint r = rep[u+BUFF];
			
			lint MM = cyclesz[r];
			//show2(t, t%MM);
			
			while(ptr < sz(stuff[r])){
				if(stuff[r][ptr] > t) break;
				else{
					sumofshit += (infs[MM]-stuff[r][ptr])/MM + 1;
					//shitmods.push_back(stuff[r][ptr] % MM); ///change this
					unshitupdate(stuff[r][ptr] % MM);
					ptr++;
					shitcnt++;
				}
				//sort(all(shitmods));
			}
			
			ans += sumofshit;
			lint fulls = (infs[MM]-(t+1))/MM;
			fulls *= shitcnt;
			
			if(fulls >= 0){
				ans -= fulls;
				ans -= (shitcnt - unshitquery(t%MM)); ///change this
			}
		}
 
		
		q.ans = ans;
	}
	
	sort(all(queries), [&](query a, query b){ return a.id < b.id; });
	for(query q : queries) cout << q.ans << '\n';
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 64452 KB Output is correct
2 Correct 48 ms 65824 KB Output is correct
3 Correct 49 ms 65696 KB Output is correct
4 Correct 54 ms 65804 KB Output is correct
5 Correct 49 ms 65924 KB Output is correct
6 Correct 49 ms 65940 KB Output is correct
7 Correct 49 ms 65952 KB Output is correct
8 Correct 45 ms 65572 KB Output is correct
9 Correct 48 ms 65640 KB Output is correct
10 Correct 46 ms 65464 KB Output is correct
11 Correct 45 ms 65476 KB Output is correct
12 Correct 48 ms 66372 KB Output is correct
13 Incorrect 52 ms 66384 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 74892 KB Output is correct
2 Incorrect 373 ms 106884 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 64452 KB Output is correct
2 Correct 48 ms 65824 KB Output is correct
3 Correct 49 ms 65696 KB Output is correct
4 Correct 54 ms 65804 KB Output is correct
5 Correct 49 ms 65924 KB Output is correct
6 Correct 49 ms 65940 KB Output is correct
7 Correct 49 ms 65952 KB Output is correct
8 Correct 45 ms 65572 KB Output is correct
9 Correct 48 ms 65640 KB Output is correct
10 Correct 46 ms 65464 KB Output is correct
11 Correct 45 ms 65476 KB Output is correct
12 Correct 48 ms 66372 KB Output is correct
13 Incorrect 52 ms 66384 KB Output isn't correct
14 Halted 0 ms 0 KB -