oj.uz

Submission #431705

# Submission time Handle Problem Language Result Execution time Memory
431705 2021-06-17T14:38:15 Z oolimry Harvest (JOI20_harvest) C++17
0 / 100
 468 ms 106948 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() + 1;
	return pos;
}

vector<lint> history;
lint ft[600005];
void unshitupdate(int i){
	i = getshit(i);
	history.push_back(i);
	for(;i <= 600000;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();
		for(;i <= 600000;i += i&(-i)){
			ft[i] = 0;
		}
	}
}

int main(){
	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 43 ms 64424 KB Output is correct
2 Correct 51 ms 65856 KB Output is correct
3 Correct 60 ms 65676 KB Output is correct
4 Correct 59 ms 65684 KB Output is correct
5 Correct 57 ms 65916 KB Output is correct
6 Correct 58 ms 65944 KB Output is correct
7 Correct 58 ms 65928 KB Output is correct
8 Correct 48 ms 65564 KB Output is correct
9 Correct 53 ms 65536 KB Output is correct
10 Correct 49 ms 65508 KB Output is correct
11 Correct 55 ms 65520 KB Output is correct
12 Correct 67 ms 66332 KB Output is correct
13 Incorrect 62 ms 66364 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 242 ms 74908 KB Output is correct
2 Incorrect 468 ms 106948 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 64424 KB Output is correct
2 Correct 51 ms 65856 KB Output is correct
3 Correct 60 ms 65676 KB Output is correct
4 Correct 59 ms 65684 KB Output is correct
5 Correct 57 ms 65916 KB Output is correct
6 Correct 58 ms 65944 KB Output is correct
7 Correct 58 ms 65928 KB Output is correct
8 Correct 48 ms 65564 KB Output is correct
9 Correct 53 ms 65536 KB Output is correct
10 Correct 49 ms 65508 KB Output is correct
11 Correct 55 ms 65520 KB Output is correct
12 Correct 67 ms 66332 KB Output is correct
13 Incorrect 62 ms 66364 KB Output isn't correct
14 Halted 0 ms 0 KB -