oj.uz

답안 #431724

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
431724 2021-06-17T14:48:31 Z oolimry 수확 (JOI20_harvest) C++17
5 / 100
 319 ms 95160 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 R){
		create();
		if(R == m) return val;
		else if(R < m) return l->qq(R);
		else return l->val + r->qq(R);
	}
} *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(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

# 결과 실행 시간 메모리 Grader output
1 Correct 57 ms 70604 KB Output is correct
2 Correct 71 ms 86684 KB Output is correct
3 Correct 57 ms 72132 KB Output is correct
4 Correct 57 ms 65736 KB Output is correct
5 Correct 48 ms 65996 KB Output is correct
6 Correct 51 ms 65960 KB Output is correct
7 Correct 53 ms 65996 KB Output is correct
8 Correct 55 ms 65568 KB Output is correct
9 Correct 49 ms 65500 KB Output is correct
10 Correct 50 ms 65476 KB Output is correct
11 Correct 47 ms 65580 KB Output is correct
12 Correct 56 ms 72644 KB Output is correct
13 Correct 78 ms 85476 KB Output is correct
14 Correct 64 ms 79332 KB Output is correct
15 Correct 51 ms 65848 KB Output is correct
16 Correct 58 ms 65804 KB Output is correct
17 Correct 56 ms 65780 KB Output is correct
18 Correct 52 ms 65760 KB Output is correct
19 Correct 49 ms 65732 KB Output is correct
20 Correct 50 ms 65764 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 319 ms 95160 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Correct 57 ms 70604 KB Output is correct
2 Correct 71 ms 86684 KB Output is correct
3 Correct 57 ms 72132 KB Output is correct
4 Correct 57 ms 65736 KB Output is correct
5 Correct 48 ms 65996 KB Output is correct
6 Correct 51 ms 65960 KB Output is correct
7 Correct 53 ms 65996 KB Output is correct
8 Correct 55 ms 65568 KB Output is correct
9 Correct 49 ms 65500 KB Output is correct
10 Correct 50 ms 65476 KB Output is correct
11 Correct 47 ms 65580 KB Output is correct
12 Correct 56 ms 72644 KB Output is correct
13 Correct 78 ms 85476 KB Output is correct
14 Correct 64 ms 79332 KB Output is correct
15 Correct 51 ms 65848 KB Output is correct
16 Correct 58 ms 65804 KB Output is correct
17 Correct 56 ms 65780 KB Output is correct
18 Correct 52 ms 65760 KB Output is correct
19 Correct 49 ms 65732 KB Output is correct
20 Correct 50 ms 65764 KB Output is correct
21 Incorrect 319 ms 95160 KB Output isn't correct
22 Halted 0 ms 0 KB -