oj.uz

답안 #431748

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
431748 2021-06-17T15:01:32 Z oolimry 수확 (JOI20_harvest) C++17
5 / 100
 760 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 val = 0;
	node *l = nullptr, *r = nullptr;

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

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();
			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';
}

Compilation message

harvest.cpp: In member function 'void node::create(lint, lint)':
harvest.cpp:125:8: warning: unused variable 'm' [-Wunused-variable]
  125 |   lint m = (s+e)/2;
      |        ^

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 49 ms 68816 KB Output is correct
2 Correct 63 ms 78656 KB Output is correct
3 Correct 55 ms 70292 KB Output is correct
4 Correct 47 ms 65756 KB Output is correct
5 Correct 48 ms 65964 KB Output is correct
6 Correct 47 ms 65940 KB Output is correct
7 Correct 48 ms 66036 KB Output is correct
8 Correct 52 ms 65540 KB Output is correct
9 Correct 46 ms 65484 KB Output is correct
10 Correct 45 ms 65452 KB Output is correct
11 Correct 44 ms 65464 KB Output is correct
12 Correct 55 ms 70872 KB Output is correct
13 Correct 68 ms 78332 KB Output is correct
14 Correct 59 ms 74232 KB Output is correct
15 Correct 49 ms 65860 KB Output is correct
16 Correct 48 ms 65756 KB Output is correct
17 Correct 48 ms 65868 KB Output is correct
18 Correct 44 ms 65668 KB Output is correct
19 Correct 47 ms 65712 KB Output is correct
20 Correct 45 ms 65716 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 318 ms 86032 KB Output is correct
2 Correct 390 ms 117428 KB Output is correct
3 Runtime error 760 ms 524292 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Correct 49 ms 68816 KB Output is correct
2 Correct 63 ms 78656 KB Output is correct
3 Correct 55 ms 70292 KB Output is correct
4 Correct 47 ms 65756 KB Output is correct
5 Correct 48 ms 65964 KB Output is correct
6 Correct 47 ms 65940 KB Output is correct
7 Correct 48 ms 66036 KB Output is correct
8 Correct 52 ms 65540 KB Output is correct
9 Correct 46 ms 65484 KB Output is correct
10 Correct 45 ms 65452 KB Output is correct
11 Correct 44 ms 65464 KB Output is correct
12 Correct 55 ms 70872 KB Output is correct
13 Correct 68 ms 78332 KB Output is correct
14 Correct 59 ms 74232 KB Output is correct
15 Correct 49 ms 65860 KB Output is correct
16 Correct 48 ms 65756 KB Output is correct
17 Correct 48 ms 65868 KB Output is correct
18 Correct 44 ms 65668 KB Output is correct
19 Correct 47 ms 65712 KB Output is correct
20 Correct 45 ms 65716 KB Output is correct
21 Correct 318 ms 86032 KB Output is correct
22 Correct 390 ms 117428 KB Output is correct
23 Runtime error 760 ms 524292 KB Execution killed with signal 9
24 Halted 0 ms 0 KB -