oj.uz

Submission #431765

# Submission time Handle Problem Language Result Execution time Memory
431765 2021-06-17T15:10:18 Z oolimry Harvest (JOI20_harvest) C++17
0 / 100
 208 ms 74884 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 getshit1(lint i){
	int pos = upper_bound(all(disshit), i) - disshit.begin() + 1;
	return pos;
}

 
vector<lint> history;
lint ft[1400005];
void unshitupdate(int i){
	i = getshit1(i);
	if(i == 0) return;
	history.push_back(i);
	for(;i <= 1400001;i += i&(-i)){
		ft[i]++;
	}
}
lint unshitquery(int i){
	i = getshit1(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+1)); ///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 52 ms 64452 KB Output is correct
2 Correct 58 ms 65932 KB Output is correct
3 Correct 50 ms 65788 KB Output is correct
4 Correct 57 ms 65672 KB Output is correct
5 Correct 54 ms 66024 KB Output is correct
6 Correct 54 ms 65956 KB Output is correct
7 Correct 54 ms 66116 KB Output is correct
8 Correct 53 ms 65512 KB Output is correct
9 Correct 54 ms 65548 KB Output is correct
10 Correct 54 ms 65536 KB Output is correct
11 Correct 52 ms 65500 KB Output is correct
12 Correct 53 ms 66260 KB Output is correct
13 Incorrect 55 ms 66424 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 208 ms 74884 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 64452 KB Output is correct
2 Correct 58 ms 65932 KB Output is correct
3 Correct 50 ms 65788 KB Output is correct
4 Correct 57 ms 65672 KB Output is correct
5 Correct 54 ms 66024 KB Output is correct
6 Correct 54 ms 65956 KB Output is correct
7 Correct 54 ms 66116 KB Output is correct
8 Correct 53 ms 65512 KB Output is correct
9 Correct 54 ms 65548 KB Output is correct
10 Correct 54 ms 65536 KB Output is correct
11 Correct 52 ms 65500 KB Output is correct
12 Correct 53 ms 66260 KB Output is correct
13 Incorrect 55 ms 66424 KB Output isn't correct
14 Halted 0 ms 0 KB -