Submission #31127

#	Time	Username	Problem	Language	Result	Execution time	Memory
31127		trath	Divide and conquer (IZhO14_divide)	C++14	17 / 100	79 ms	72332 KiB

divide

#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 (stderr)

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 / 17
• Subtask 2: 0 / 31
• Subtask 3: 0 / 52