oj.uz

Submission #155720

# Submission time Handle Problem Language Result Execution time Memory
155720 2019-09-30T05:45:42 Z junodeveloper Divide and conquer (IZhO14_divide) C++14
0 / 100
 4 ms 1400 KB 
#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INF=1e18;
struct point {
	int x,g,d;
	bool operator<(const point& b)const {
		return x<b.x;
	}
} p[100010];
int n;
ll tree[100010];
ll D[100010],G[100010];
void update(int p,ll x) {
	for(int i=p+1;i>0;i-=i&-i)
		tree[i]=min(tree[i],x);
}
ll query(int p) {
	ll ret=INF;
	for(int i=p+1;i<=100005;i+=i&-i)
		ret=max(ret,tree[i]);
	return ret;
}
int main() {
	scanf("%d",&n);
	fill(tree,tree+100010,INF);
	int i,j,k;
	for(i=1;i<=n;i++) {
		scanf("%d%d%d",&p[i].x,&p[i].g,&p[i].d);
	}
	sort(p+1,p+n+1);
	vector<ll> v;
	for(i=1;i<=n;i++) {
		D[i]=D[i-1]+p[i].d;
		G[i]=G[i-1]+p[i].g;
		v.push_back(p[i].x-D[i-1]);
	}
	ll res=0;
	for(i=1;i<=n;i++) {
		// x[i]-x[j]<=D[i]-D[j-1]
		// x[i]-D[i]<=x[j]-D[j-1];
		int idx=lower_bound(all(v),p[i].x-D[i])-v.begin();
		ll q=query(idx);
		res=max(res,G[i]-G[i-1]);
		res=max(res,G[i]-q);
		idx=lower_bound(all(v),p[i].x-D[i-1])-v.begin();
		update(idx,G[i-1]);
	}
	printf("%lld",res);
	return 0;
}

Compilation message

divide.cpp: In function 'int main()':
divide.cpp:34:8: warning: unused variable 'j' [-Wunused-variable]
  int i,j,k;
        ^
divide.cpp:34:10: warning: unused variable 'k' [-Wunused-variable]
  int i,j,k;
          ^
divide.cpp:32:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
divide.cpp:36:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d",&p[i].x,&p[i].g,&p[i].d);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 17.0

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

Subtask #2
0 / 31.0

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

Subtask #3
0 / 52.0

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