oj.uz

Submission #31127

# Submission time Handle Problem Language Result Execution time Memory
31127 2017-08-10T19:32:47 Z trath Divide and conquer (IZhO14_divide) C++14
17 / 100
 79 ms 72332 KB 
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define int long long
#define ieps (int) 1e6
#define eps (int) 1e9
#define pii pair<int,int>

struct node{
	int sz, xsz, posz;
} st[ieps];

int n;
int x[ieps] , g[ieps] , d[ieps] , sfx[ieps] , dp[ieps] , energys[ieps];


node mixnode(node left, node right){
	if(left.xsz + left.sz > right.xsz + right.sz){
		return left;
	}
	else{
		return right;
	}
}


void build(int l = 0 , int r = n -1  , int curr = 1){
	if(l == r ){
		st[ieps].sz = d[l];
		st[ieps].xsz = x[l];
		st[ieps].posz = l;
		return ;
	}
	build(l , (l+r)/2 , 2*curr);
	build((l+r)/2 + 1 , r , 2*curr + 1);
	st[curr] = mixnode(st[2*curr] , st[2*curr + 1]);
}

node query(int x , int y , int l = 0 , int r = n- 1 , int curr = 1){
	if(l == x && r ==y){
		return st[curr];
	}
	int mid = (l+r)/2;
	if(y <= mid){
		return query(x , y , l, mid , 2*curr);
	}
	if(x > mid){
		return query(x , y ,mid + 1 , r,  2*curr + 1);
	}
	return mixnode(query(x , mid, l , mid , 2*curr) , query(mid + 1 , y,  mid + 1 , r, 2*curr + 1));
}


int32_t main(){
	scanf("%lld" , &n);
	for(int i = 0;i<n;i++){
		scanf("%lld %lld %lld" , & x[i] , & g[i] , & d[i]);
	}
	sfx[0] = g[0];
	energys[0] = d[0];
	for(int i = 1;i<n;i++){
		sfx[i] = sfx[i-1] + g[i];
		energys[i] = energys[i-1] + d[i];
	}
	dp[n] = 0;
	dp[n - 1] = 1;
	for(int i = n- 2 ; i>=0 ; i--){
		int ans = -1;
		int getsfx = 0LL;
		if(i) getsfx = energys[i-1];
		int l = i + 1 , r = n - 1; 
		while(l<=r){
			int mid = (l + r)/2;
			if(x[mid] - x[i] <= energys[mid] - getsfx){
				ans = mid;
				l = mid + 1;
			}
			else{
				r = mid - 1;
			}
		}
		if(ans == -1) dp[i] = 1;
		else{
			node r = query(i , ans);
			dp[i] = max(ans - i + 1 , (r.posz - i) + dp[r.posz]);
		}
	}
	int ans  = sfx[dp[0]-1];
	for(int i = 1;i<n;i++){
		ans = max(ans , sfx[(dp[i] + i - 1)] - sfx[i - 1]);
	}
	printf("%lld\n" , ans);
}

Compilation message

divide.cpp: In function 'int32_t main()':
divide.cpp:58:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld" , &n);
                    ^
divide.cpp:60:53: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld %lld" , & x[i] , & g[i] , & d[i]);
                                                     ^
divide.cpp: In function 'void build(long long int, long long int, long long int)':
divide.cpp:32:10: warning: array subscript is above array bounds [-Warray-bounds]
   st[ieps].sz = d[l];
          ^
divide.cpp:33:10: warning: array subscript is above array bounds [-Warray-bounds]
   st[ieps].xsz = x[l];
          ^
divide.cpp:34:10: warning: array subscript is above array bounds [-Warray-bounds]
   st[ieps].posz = l;
          ^

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 72332 KB Output is correct
2 Correct 0 ms 72332 KB Output is correct
3 Correct 0 ms 72332 KB Output is correct
4 Correct 0 ms 72332 KB Output is correct
5 Correct 0 ms 72332 KB Output is correct
6 Correct 0 ms 72332 KB Output is correct
7 Correct 0 ms 72332 KB Output is correct
8 Correct 0 ms 72332 KB Output is correct
9 Correct 0 ms 72332 KB Output is correct
10 Correct 0 ms 72332 KB Output is correct
11 Correct 0 ms 72332 KB Output is correct
12 Correct 0 ms 72332 KB Output is correct

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 72332 KB Output is correct
2 Correct 0 ms 72332 KB Output is correct
3 Incorrect 0 ms 72332 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 72332 KB Output is correct
2 Correct 0 ms 72332 KB Output is correct
3 Correct 6 ms 72332 KB Output is correct
4 Correct 43 ms 72332 KB Output is correct
5 Correct 33 ms 72332 KB Output is correct
6 Correct 76 ms 72332 KB Output is correct
7 Correct 69 ms 72332 KB Output is correct
8 Correct 79 ms 72332 KB Output is correct
9 Correct 66 ms 72332 KB Output is correct
10 Incorrect 56 ms 72332 KB Output isn't correct
11 Halted 0 ms 0 KB -