Submission #42322

#	Time	Username	Problem	Language	Result	Execution time	Memory
42322		wzy	Divide and conquer (IZhO14_divide)	C++11	100 / 100	84 ms	26644 KiB

divide

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define F first
#define S second
#define mp make_pair
#define pb push_back
int n;

struct mine{
	int x, g,d;
};
int sd[100005] , sg[100005] , opt[100005] , st[400005];

bool cmp(mine a , mine b){
	return a.x < b.x;
}


void update(int x , int value , int l = 0 , int r = n-1 , int curr = 1){
	int mid = (l+r)/2;
	if(l == r){
		st[curr] = value;
		return;
	}
	if(x <= mid) update(x,value,l,mid,2*curr);
	else update(x,value,mid+1,r,2*curr + 1);
	st[curr] = min(st[2*curr] , st[2*curr + 1]);
}

int query(int val , int l = 0 , int r = n-1 , int curr = 1){
	int mid = (l+r)/2;
	if(l ==r) return l;
	if(st[2*curr] <= val) return query(val,l,mid,2*curr);
	return query(val,mid+1,r,2*curr + 1); 
}


int32_t main(){
	scanf("%lld" , &n);
	vector<mine> v(n);
	for(int i = 0 ; i < n;i++) scanf("%lld%lld%lld" , &v[i].x , &v[i].g , &v[i].d);
	sort(v.begin() , v.end() , cmp);
	for(int i = 0;i<n;i++){
		sd[i] = v[i].d;
		if(i) sd[i] += sd[i-1];
		sg[i] = v[i].g;
		if(i) sg[i] += sg[i-1];
	}
	for(int i = 0 ; i <= 4*n ; i++){
		st[i] = (int) 1e18;
	}
	for(int i = 0 ; i < n;i++){
		update(i,  - v[i].x + (i ? sd[i-1] : 0));
		opt[i] = query(sd[i] - v[i].x);
	}
	int ansj = 0;
	for(int i = 0 ; i <n;i++){
		ansj = max(ansj , sg[i] - (opt[i] ? sg[opt[i] - 1] : 0));
	}
	printf("%lld\n" , ansj);
}

Compilation message (stderr)

divide.cpp: In function 'int32_t main()':
divide.cpp:40:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld" , &n);
                    ^
divide.cpp:42:80: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 0 ; i < n;i++) scanf("%lld%lld%lld" , &v[i].x , &v[i].g , &v[i].d);
                                                                                ^

• Subtask 1: 17 / 17
• Subtask 2: 31 / 31
• Subtask 3: 52 / 52