oj.uz

Submission #431727

# Submission time Handle Problem Language Result Execution time Memory
431727 2021-06-17T14:51:09 Z oolimry Harvest (JOI20_harvest) C++17
5 / 100
 700 ms 524292 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();
	return pos;
}

vector<lint> history;

struct node{
	lint s, e, m;
	lint val = 0;
	node *l = nullptr, *r = nullptr;
	
	node(lint S, lint E){
		s = S, e = E, m = (s+e)/2;
	}
	
	
	void create(){
		if(s != e and l == nullptr){
			l = new node(s, m);
			r = new node(m+1, e);
		}
	}
	
	void update(lint X){
		create();
		val++;
		if(s != e){
			if(X <= m) l->update(X);
			else r->update(X);
		}
	}
	
	lint qq(lint S, lint E){
		create();
		if(S == s and E == e) return val;
		else if(E <= m) return l->qq(S, E);
		else if(S >= m+1) return r->qq(S, E);
		else return l->qq(S, m) + r->qq(m+1, E);
	}
} *root = new node(0, 1e18);

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];
			root = new node(0, 1e18);
			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
					root->update(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 - root->qq(0, 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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 73412 KB Output is correct
2 Correct 85 ms 91656 KB Output is correct
3 Correct 60 ms 75168 KB Output is correct
4 Correct 51 ms 65808 KB Output is correct
5 Correct 49 ms 65988 KB Output is correct
6 Correct 50 ms 65932 KB Output is correct
7 Correct 54 ms 65976 KB Output is correct
8 Correct 48 ms 65532 KB Output is correct
9 Correct 53 ms 65492 KB Output is correct
10 Correct 58 ms 65540 KB Output is correct
11 Correct 56 ms 65608 KB Output is correct
12 Correct 60 ms 75700 KB Output is correct
13 Correct 79 ms 90480 KB Output is correct
14 Correct 69 ms 82452 KB Output is correct
15 Correct 58 ms 65880 KB Output is correct
16 Correct 51 ms 65936 KB Output is correct
17 Correct 52 ms 65860 KB Output is correct
18 Correct 48 ms 65612 KB Output is correct
19 Correct 50 ms 65748 KB Output is correct
20 Correct 50 ms 65640 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 419 ms 97288 KB Output is correct
2 Correct 413 ms 129576 KB Output is correct
3 Runtime error 700 ms 524292 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 73412 KB Output is correct
2 Correct 85 ms 91656 KB Output is correct
3 Correct 60 ms 75168 KB Output is correct
4 Correct 51 ms 65808 KB Output is correct
5 Correct 49 ms 65988 KB Output is correct
6 Correct 50 ms 65932 KB Output is correct
7 Correct 54 ms 65976 KB Output is correct
8 Correct 48 ms 65532 KB Output is correct
9 Correct 53 ms 65492 KB Output is correct
10 Correct 58 ms 65540 KB Output is correct
11 Correct 56 ms 65608 KB Output is correct
12 Correct 60 ms 75700 KB Output is correct
13 Correct 79 ms 90480 KB Output is correct
14 Correct 69 ms 82452 KB Output is correct
15 Correct 58 ms 65880 KB Output is correct
16 Correct 51 ms 65936 KB Output is correct
17 Correct 52 ms 65860 KB Output is correct
18 Correct 48 ms 65612 KB Output is correct
19 Correct 50 ms 65748 KB Output is correct
20 Correct 50 ms 65640 KB Output is correct
21 Correct 419 ms 97288 KB Output is correct
22 Correct 413 ms 129576 KB Output is correct
23 Runtime error 700 ms 524292 KB Execution killed with signal 9
24 Halted 0 ms 0 KB -