oj.uz

Submission #42322

# Submission time Handle Problem Language Result Execution time Memory
42322 2018-02-26T03:31:28 Z wzy Divide and conquer (IZhO14_divide) C++11
100 / 100
 84 ms 26644 KB 
#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

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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 252 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 2 ms 592 KB Output is correct
4 Correct 2 ms 592 KB Output is correct
5 Correct 2 ms 612 KB Output is correct
6 Correct 2 ms 616 KB Output is correct
7 Correct 2 ms 620 KB Output is correct
8 Correct 2 ms 624 KB Output is correct
9 Correct 2 ms 732 KB Output is correct
10 Correct 1 ms 736 KB Output is correct
11 Correct 2 ms 740 KB Output is correct
12 Correct 1 ms 744 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 748 KB Output is correct
2 Correct 1 ms 752 KB Output is correct
3 Correct 2 ms 756 KB Output is correct
4 Correct 2 ms 788 KB Output is correct
5 Correct 2 ms 820 KB Output is correct
6 Correct 3 ms 992 KB Output is correct
7 Correct 2 ms 992 KB Output is correct
8 Correct 2 ms 992 KB Output is correct
9 Correct 2 ms 1112 KB Output is correct
10 Correct 3 ms 1112 KB Output is correct
11 Correct 5 ms 1424 KB Output is correct
12 Correct 5 ms 1660 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1692 KB Output is correct
2 Correct 6 ms 2232 KB Output is correct
3 Correct 7 ms 2360 KB Output is correct
4 Correct 36 ms 6524 KB Output is correct
5 Correct 39 ms 7968 KB Output is correct
6 Correct 84 ms 14824 KB Output is correct
7 Correct 64 ms 16616 KB Output is correct
8 Correct 66 ms 18624 KB Output is correct
9 Correct 61 ms 20292 KB Output is correct
10 Correct 83 ms 22060 KB Output is correct
11 Correct 74 ms 24256 KB Output is correct
12 Correct 84 ms 26644 KB Output is correct