oj.uz

Submission #155721

# Submission time Handle Problem Language Result Execution time Memory
155721 2019-09-30T05:51:47 Z junodeveloper Divide and conquer (IZhO14_divide) C++14
100 / 100
 77 ms 7656 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=min(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]);
	}
	sort(all(v));
	v.erase(unique(all(v)),v.end());
	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
17.0 / 17.0

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

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1144 KB Output is correct
2 Correct 3 ms 1148 KB Output is correct
3 Correct 3 ms 1144 KB Output is correct
4 Correct 3 ms 1144 KB Output is correct
5 Correct 3 ms 1144 KB Output is correct
6 Correct 4 ms 1144 KB Output is correct
7 Correct 3 ms 1144 KB Output is correct
8 Correct 4 ms 1144 KB Output is correct
9 Correct 4 ms 1224 KB Output is correct
10 Correct 4 ms 1272 KB Output is correct
11 Correct 6 ms 1528 KB Output is correct
12 Correct 7 ms 1400 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1400 KB Output is correct
2 Correct 8 ms 1656 KB Output is correct
3 Correct 8 ms 1784 KB Output is correct
4 Correct 33 ms 3952 KB Output is correct
5 Correct 37 ms 4332 KB Output is correct
6 Correct 77 ms 7656 KB Output is correct
7 Correct 60 ms 6512 KB Output is correct
8 Correct 61 ms 6604 KB Output is correct
9 Correct 59 ms 6380 KB Output is correct
10 Correct 60 ms 6408 KB Output is correct
11 Correct 66 ms 6888 KB Output is correct
12 Correct 68 ms 7016 KB Output is correct