oj.uz

Submission #677261

# Submission time Handle Problem Language Result Execution time Memory
677261 2023-01-02T16:55:40 Z dsyz Solar Storm (NOI20_solarstorm) C++17
36 / 100
 562 ms 212608 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] = i;
			dfs(i);
		}
	}
	for(ll k = 1;k < 20;k++){
		for(ll i = 0;i < N;i++){
			if(parent[k - 1][i] != i){
				parent[k][i] = parent[k - 1][parent[k - 1][i]];
			}else{
				parent[k][i] = i;
			}
		}
	}
	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 38 ms 102988 KB Output is correct
2 Correct 44 ms 103860 KB Output is correct
3 Correct 43 ms 104012 KB Output is correct
4 Correct 47 ms 103480 KB Output is correct
5 Correct 39 ms 102996 KB Output is correct
6 Correct 58 ms 103248 KB Output is correct
7 Correct 42 ms 103204 KB Output is correct
8 Correct 49 ms 103244 KB Output is correct
9 Correct 42 ms 103356 KB Output is correct
10 Correct 45 ms 103520 KB Output is correct
11 Correct 47 ms 103620 KB Output is correct
12 Correct 42 ms 103320 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 129880 KB Output is correct
2 Correct 219 ms 124768 KB Output is correct
3 Correct 256 ms 135144 KB Output is correct
4 Correct 337 ms 142884 KB Output is correct
5 Correct 403 ms 149788 KB Output is correct
6 Correct 469 ms 165436 KB Output is correct
7 Correct 325 ms 149284 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 102988 KB Output is correct
2 Correct 44 ms 103860 KB Output is correct
3 Correct 43 ms 104012 KB Output is correct
4 Correct 47 ms 103480 KB Output is correct
5 Correct 39 ms 102996 KB Output is correct
6 Correct 58 ms 103248 KB Output is correct
7 Correct 42 ms 103204 KB Output is correct
8 Correct 49 ms 103244 KB Output is correct
9 Correct 42 ms 103356 KB Output is correct
10 Correct 45 ms 103520 KB Output is correct
11 Correct 47 ms 103620 KB Output is correct
12 Correct 42 ms 103320 KB Output is correct
13 Correct 244 ms 129880 KB Output is correct
14 Correct 219 ms 124768 KB Output is correct
15 Correct 256 ms 135144 KB Output is correct
16 Correct 337 ms 142884 KB Output is correct
17 Correct 403 ms 149788 KB Output is correct
18 Correct 469 ms 165436 KB Output is correct
19 Correct 325 ms 149284 KB Output is correct
20 Correct 213 ms 121328 KB Output is correct
21 Correct 334 ms 170808 KB Output is correct
22 Correct 388 ms 183612 KB Output is correct
23 Correct 242 ms 128472 KB Output is correct
24 Correct 237 ms 126156 KB Output is correct
25 Correct 359 ms 138184 KB Output is correct
26 Correct 241 ms 126324 KB Output is correct
27 Correct 348 ms 137564 KB Output is correct
28 Correct 360 ms 138668 KB Output is correct
29 Correct 459 ms 149228 KB Output is correct
30 Correct 363 ms 144696 KB Output is correct
31 Correct 334 ms 153132 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 432 ms 193488 KB Output is correct
2 Correct 248 ms 154772 KB Output is correct
3 Correct 270 ms 158452 KB Output is correct
4 Correct 360 ms 183068 KB Output is correct
5 Correct 366 ms 180636 KB Output is correct
6 Correct 374 ms 185344 KB Output is correct
7 Correct 562 ms 212608 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 102988 KB Output is correct
2 Correct 44 ms 103860 KB Output is correct
3 Correct 43 ms 104012 KB Output is correct
4 Correct 47 ms 103480 KB Output is correct
5 Correct 39 ms 102996 KB Output is correct
6 Correct 58 ms 103248 KB Output is correct
7 Correct 42 ms 103204 KB Output is correct
8 Correct 49 ms 103244 KB Output is correct
9 Correct 42 ms 103356 KB Output is correct
10 Correct 45 ms 103520 KB Output is correct
11 Correct 47 ms 103620 KB Output is correct
12 Correct 42 ms 103320 KB Output is correct
13 Correct 48 ms 103376 KB Output is correct
14 Incorrect 51 ms 103372 KB Damaged module blocking communication between protected modules
15 Halted 0 ms 0 KB -

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 102988 KB Output is correct
2 Correct 44 ms 103860 KB Output is correct
3 Correct 43 ms 104012 KB Output is correct
4 Correct 47 ms 103480 KB Output is correct
5 Correct 39 ms 102996 KB Output is correct
6 Correct 58 ms 103248 KB Output is correct
7 Correct 42 ms 103204 KB Output is correct
8 Correct 49 ms 103244 KB Output is correct
9 Correct 42 ms 103356 KB Output is correct
10 Correct 45 ms 103520 KB Output is correct
11 Correct 47 ms 103620 KB Output is correct
12 Correct 42 ms 103320 KB Output is correct
13 Correct 244 ms 129880 KB Output is correct
14 Correct 219 ms 124768 KB Output is correct
15 Correct 256 ms 135144 KB Output is correct
16 Correct 337 ms 142884 KB Output is correct
17 Correct 403 ms 149788 KB Output is correct
18 Correct 469 ms 165436 KB Output is correct
19 Correct 325 ms 149284 KB Output is correct
20 Correct 213 ms 121328 KB Output is correct
21 Correct 334 ms 170808 KB Output is correct
22 Correct 388 ms 183612 KB Output is correct
23 Correct 242 ms 128472 KB Output is correct
24 Correct 237 ms 126156 KB Output is correct
25 Correct 359 ms 138184 KB Output is correct
26 Correct 241 ms 126324 KB Output is correct
27 Correct 348 ms 137564 KB Output is correct
28 Correct 360 ms 138668 KB Output is correct
29 Correct 459 ms 149228 KB Output is correct
30 Correct 363 ms 144696 KB Output is correct
31 Correct 334 ms 153132 KB Output is correct
32 Correct 291 ms 130304 KB Output is correct
33 Correct 312 ms 132548 KB Output is correct
34 Incorrect 450 ms 149800 KB Damaged module blocking communication between protected modules
35 Halted 0 ms 0 KB -

Subtask #7
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 102988 KB Output is correct
2 Correct 44 ms 103860 KB Output is correct
3 Correct 43 ms 104012 KB Output is correct
4 Correct 47 ms 103480 KB Output is correct
5 Correct 39 ms 102996 KB Output is correct
6 Correct 58 ms 103248 KB Output is correct
7 Correct 42 ms 103204 KB Output is correct
8 Correct 49 ms 103244 KB Output is correct
9 Correct 42 ms 103356 KB Output is correct
10 Correct 45 ms 103520 KB Output is correct
11 Correct 47 ms 103620 KB Output is correct
12 Correct 42 ms 103320 KB Output is correct
13 Correct 244 ms 129880 KB Output is correct
14 Correct 219 ms 124768 KB Output is correct
15 Correct 256 ms 135144 KB Output is correct
16 Correct 337 ms 142884 KB Output is correct
17 Correct 403 ms 149788 KB Output is correct
18 Correct 469 ms 165436 KB Output is correct
19 Correct 325 ms 149284 KB Output is correct
20 Correct 213 ms 121328 KB Output is correct
21 Correct 334 ms 170808 KB Output is correct
22 Correct 388 ms 183612 KB Output is correct
23 Correct 242 ms 128472 KB Output is correct
24 Correct 237 ms 126156 KB Output is correct
25 Correct 359 ms 138184 KB Output is correct
26 Correct 241 ms 126324 KB Output is correct
27 Correct 348 ms 137564 KB Output is correct
28 Correct 360 ms 138668 KB Output is correct
29 Correct 459 ms 149228 KB Output is correct
30 Correct 363 ms 144696 KB Output is correct
31 Correct 334 ms 153132 KB Output is correct
32 Correct 432 ms 193488 KB Output is correct
33 Correct 248 ms 154772 KB Output is correct
34 Correct 270 ms 158452 KB Output is correct
35 Correct 360 ms 183068 KB Output is correct
36 Correct 366 ms 180636 KB Output is correct
37 Correct 374 ms 185344 KB Output is correct
38 Correct 562 ms 212608 KB Output is correct
39 Correct 48 ms 103376 KB Output is correct
40 Incorrect 51 ms 103372 KB Damaged module blocking communication between protected modules
41 Halted 0 ms 0 KB -