oj.uz

Submission #677259

# Submission time Handle Problem Language Result Execution time Memory
677259 2023-01-02T16:51:10 Z dsyz Solar Storm (NOI20_solarstorm) C++17
36 / 100
 518 ms 212736 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (1000005)
vector<ll> v[MAXN];
int parent[20][MAXN]; //(2^19 + 2^18 + 2^17 ... + 2^0) = (2^20 - 1) which is > 10^6
bool visited[MAXN];
void dfs(ll x){
	visited[x] = 1;
	for(auto u : v[x]){
		if(!visited[u]){
			parent[0][u] = x;
			visited[u] = 1;
			dfs(u);
		}
	}
}
ll fp(ll x,ll k){
	for(ll i = 19;i >= 0;i--){
		if(k >= (1<<i)){
			if(x == -1) return -1;
			x = parent[i][x];
			k -= (1<<i);
		}
	}
	return x;
}
int main() {
	ios_base::sync_with_stdio(false);cin.tie(0);
	ll N,S,K;
	cin>>N>>S>>K;
	ll d[N];
	ll arr[N];
	memset(d,0,sizeof(d));
	d[0] = 0;
	for(ll i = 1;i < N;i++){
		ll a;
		cin>>a;
		d[i] = d[i - 1] + a;
	}
	for(ll i = 0;i < N;i++){
		cin>>arr[i];
	}
	ll indeg[N];
	memset(indeg,0,sizeof(indeg));
	for(ll i = 0;i < N;i++){
		ll p = lower_bound(d,d + N,d[i] - K) - d - 1;
		if(p < 0 || p == i) continue;
		p = lower_bound(d,d + N,d[p] - K) - d;
		if(p < 0 || p == i) continue;
		v[p].push_back(i);
		indeg[i]++;
	}
	memset(visited,0,sizeof(visited));
	memset(parent,-1,sizeof(parent));
	for(ll i = 0;i < N;i++){
		if(indeg[i] == 0){
			visited[i] = 1;
			parent[0][i] = -1;
			dfs(i);
		}
	}
	for(ll k = 1;k < 20;k++){
		for(ll i = 0;i < N;i++){
			if(parent[k - 1][i] != -1){
				parent[k][i] = parent[k - 1][parent[k - 1][i]];
			}else{
				parent[k][i] = -1;
			}
		}
	}
	ll psum[N];
	ll cur = 0;
	for(ll i = 0;i < N;i++){
		cur += arr[i];
		psum[i] = cur;
	}
	ll ans = 0;
	pair<ll,ll> range = {-1,-1};
	for(ll r = 0;r < N;r++){
		ll l = fp(r,S - 1);
		if(l == -1) l = r;
		ll s = lower_bound(d,d + N,d[l] - K) - d;
		ll e = upper_bound(d,d + N,d[r] + K) - d - 1;
		ll sum = psum[e];
		if(s >= 1) sum -= psum[s - 1];
		if(sum > ans){
			range = {s,e};
			ans = sum;
		}
	}
	vector<ll> modules;
	ll E = upper_bound(d,d + N,d[range.first] + K) - d - 1;
	modules.push_back(E + 1);
	ll modulepos = d[E];
	for(ll i = E + 1;i <= range.second;i++){
		E++;
		if(d[i] > modulepos + K){
			modules.push_back(i + 1);
			ll newpos = upper_bound(d,d + N,d[i] + K) - d - 1;
			modulepos = d[newpos];
			i = newpos;
		}
	}
	cout<<modules.size()<<'\n';
	for(auto u : modules){
		cout<<u<<" ";
	}
	cout<<'\n';
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 102920 KB Output is correct
2 Correct 43 ms 104008 KB Output is correct
3 Correct 45 ms 104120 KB Output is correct
4 Correct 40 ms 103516 KB Output is correct
5 Correct 41 ms 103036 KB Output is correct
6 Correct 45 ms 103368 KB Output is correct
7 Correct 43 ms 103332 KB Output is correct
8 Correct 42 ms 103436 KB Output is correct
9 Correct 42 ms 103372 KB Output is correct
10 Correct 46 ms 103576 KB Output is correct
11 Correct 44 ms 103556 KB Output is correct
12 Correct 48 ms 103368 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 251 ms 130320 KB Output is correct
2 Correct 222 ms 125316 KB Output is correct
3 Correct 259 ms 135852 KB Output is correct
4 Correct 336 ms 143524 KB Output is correct
5 Correct 427 ms 150544 KB Output is correct
6 Correct 479 ms 166476 KB Output is correct
7 Correct 329 ms 150100 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 102920 KB Output is correct
2 Correct 43 ms 104008 KB Output is correct
3 Correct 45 ms 104120 KB Output is correct
4 Correct 40 ms 103516 KB Output is correct
5 Correct 41 ms 103036 KB Output is correct
6 Correct 45 ms 103368 KB Output is correct
7 Correct 43 ms 103332 KB Output is correct
8 Correct 42 ms 103436 KB Output is correct
9 Correct 42 ms 103372 KB Output is correct
10 Correct 46 ms 103576 KB Output is correct
11 Correct 44 ms 103556 KB Output is correct
12 Correct 48 ms 103368 KB Output is correct
13 Correct 251 ms 130320 KB Output is correct
14 Correct 222 ms 125316 KB Output is correct
15 Correct 259 ms 135852 KB Output is correct
16 Correct 336 ms 143524 KB Output is correct
17 Correct 427 ms 150544 KB Output is correct
18 Correct 479 ms 166476 KB Output is correct
19 Correct 329 ms 150100 KB Output is correct
20 Correct 213 ms 122132 KB Output is correct
21 Correct 347 ms 171540 KB Output is correct
22 Correct 398 ms 184360 KB Output is correct
23 Correct 257 ms 129348 KB Output is correct
24 Correct 255 ms 126776 KB Output is correct
25 Correct 362 ms 139024 KB Output is correct
26 Correct 255 ms 127080 KB Output is correct
27 Correct 350 ms 138188 KB Output is correct
28 Correct 379 ms 139272 KB Output is correct
29 Correct 479 ms 150068 KB Output is correct
30 Correct 364 ms 144896 KB Output is correct
31 Correct 334 ms 153388 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 459 ms 193492 KB Output is correct
2 Correct 272 ms 154700 KB Output is correct
3 Correct 289 ms 158344 KB Output is correct
4 Correct 401 ms 183056 KB Output is correct
5 Correct 361 ms 180820 KB Output is correct
6 Correct 381 ms 185348 KB Output is correct
7 Correct 518 ms 212736 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 102920 KB Output is correct
2 Correct 43 ms 104008 KB Output is correct
3 Correct 45 ms 104120 KB Output is correct
4 Correct 40 ms 103516 KB Output is correct
5 Correct 41 ms 103036 KB Output is correct
6 Correct 45 ms 103368 KB Output is correct
7 Correct 43 ms 103332 KB Output is correct
8 Correct 42 ms 103436 KB Output is correct
9 Correct 42 ms 103372 KB Output is correct
10 Correct 46 ms 103576 KB Output is correct
11 Correct 44 ms 103556 KB Output is correct
12 Correct 48 ms 103368 KB Output is correct
13 Correct 44 ms 103372 KB Output is correct
14 Incorrect 44 ms 103520 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 102920 KB Output is correct
2 Correct 43 ms 104008 KB Output is correct
3 Correct 45 ms 104120 KB Output is correct
4 Correct 40 ms 103516 KB Output is correct
5 Correct 41 ms 103036 KB Output is correct
6 Correct 45 ms 103368 KB Output is correct
7 Correct 43 ms 103332 KB Output is correct
8 Correct 42 ms 103436 KB Output is correct
9 Correct 42 ms 103372 KB Output is correct
10 Correct 46 ms 103576 KB Output is correct
11 Correct 44 ms 103556 KB Output is correct
12 Correct 48 ms 103368 KB Output is correct
13 Correct 251 ms 130320 KB Output is correct
14 Correct 222 ms 125316 KB Output is correct
15 Correct 259 ms 135852 KB Output is correct
16 Correct 336 ms 143524 KB Output is correct
17 Correct 427 ms 150544 KB Output is correct
18 Correct 479 ms 166476 KB Output is correct
19 Correct 329 ms 150100 KB Output is correct
20 Correct 213 ms 122132 KB Output is correct
21 Correct 347 ms 171540 KB Output is correct
22 Correct 398 ms 184360 KB Output is correct
23 Correct 257 ms 129348 KB Output is correct
24 Correct 255 ms 126776 KB Output is correct
25 Correct 362 ms 139024 KB Output is correct
26 Correct 255 ms 127080 KB Output is correct
27 Correct 350 ms 138188 KB Output is correct
28 Correct 379 ms 139272 KB Output is correct
29 Correct 479 ms 150068 KB Output is correct
30 Correct 364 ms 144896 KB Output is correct
31 Correct 334 ms 153388 KB Output is correct
32 Correct 270 ms 130228 KB Output is correct
33 Incorrect 312 ms 132488 KB Output isn't correct
34 Halted 0 ms 0 KB -

Subtask #7
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 102920 KB Output is correct
2 Correct 43 ms 104008 KB Output is correct
3 Correct 45 ms 104120 KB Output is correct
4 Correct 40 ms 103516 KB Output is correct
5 Correct 41 ms 103036 KB Output is correct
6 Correct 45 ms 103368 KB Output is correct
7 Correct 43 ms 103332 KB Output is correct
8 Correct 42 ms 103436 KB Output is correct
9 Correct 42 ms 103372 KB Output is correct
10 Correct 46 ms 103576 KB Output is correct
11 Correct 44 ms 103556 KB Output is correct
12 Correct 48 ms 103368 KB Output is correct
13 Correct 251 ms 130320 KB Output is correct
14 Correct 222 ms 125316 KB Output is correct
15 Correct 259 ms 135852 KB Output is correct
16 Correct 336 ms 143524 KB Output is correct
17 Correct 427 ms 150544 KB Output is correct
18 Correct 479 ms 166476 KB Output is correct
19 Correct 329 ms 150100 KB Output is correct
20 Correct 213 ms 122132 KB Output is correct
21 Correct 347 ms 171540 KB Output is correct
22 Correct 398 ms 184360 KB Output is correct
23 Correct 257 ms 129348 KB Output is correct
24 Correct 255 ms 126776 KB Output is correct
25 Correct 362 ms 139024 KB Output is correct
26 Correct 255 ms 127080 KB Output is correct
27 Correct 350 ms 138188 KB Output is correct
28 Correct 379 ms 139272 KB Output is correct
29 Correct 479 ms 150068 KB Output is correct
30 Correct 364 ms 144896 KB Output is correct
31 Correct 334 ms 153388 KB Output is correct
32 Correct 459 ms 193492 KB Output is correct
33 Correct 272 ms 154700 KB Output is correct
34 Correct 289 ms 158344 KB Output is correct
35 Correct 401 ms 183056 KB Output is correct
36 Correct 361 ms 180820 KB Output is correct
37 Correct 381 ms 185348 KB Output is correct
38 Correct 518 ms 212736 KB Output is correct
39 Correct 44 ms 103372 KB Output is correct
40 Incorrect 44 ms 103520 KB Output isn't correct
41 Halted 0 ms 0 KB -