oj.uz

Submission #116760

# Submission time Handle Problem Language Result Execution time Memory
116760 2019-06-13T17:53:03 Z roseanne_pcy Divide and conquer (IZhO14_divide) C++14
100 / 100
 79 ms 8812 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;

const int maxn = 1e5+5;

ll st[4*maxn];

int m;

void build(int p = 1, int L = 0, int R = m-1)
{
	if(L == R)
	{
		st[p] = 4e18;
		return;
	}
	int M = (L+R)/2;
	build(2*p, L, M);
	build(2*p+1, M+1, R);
	st[p] = 4e18;
}
void update(int x, ll dx, int p = 1, int L = 0, int R = m-1)
{
	if(L == R)
	{
		st[p] = min(st[p], dx);
		return;
	}
	int M = (L+R)/2;
	if(x<= M) update(x, dx, 2*p, L, M);
	else update(x, dx, 2*p+1, M+1, R);
	st[p] = min(st[2*p], st[2*p+1]);
}

ll ask(int i, int j, int p = 1, int L = 0, int R = m-1)
{
	if(i> R || j< L) return 4e18;
	if(i<= L && R<= j) return st[p];
	int M = (L+R)/2;
	ll x = ask(i, j, 2*p, L, M);
	ll y = ask(i, j, 2*p+1, M+1, R);
	return min(x, y);
}

ll x[maxn], g[maxn], d[maxn];

int n;

int main()
{
	scanf("%d", &n);
	for(int i = 1; i<= n; i++) scanf("%lld %lld %lld", &x[i], &g[i], &d[i]);
	for(int i = 1; i<= n; i++)
	{
		g[i] += g[i-1];
		d[i] += d[i-1];
	}
	vector<ll> det;
	for(int i = 1; i<= n; i++) det.pb(d[i-1]-x[i]);
	sort(det.begin(), det.end());
	det.erase(unique(det.begin(), det.end()), det.end());
	m = det.size();
	build();
	// printf("%lld\n", ask(0, m-1));
	ll opt = 0;
	for(int i = 1; i<= n; i++)
	{
		int pos = lower_bound(det.begin(), det.end(), d[i-1]-x[i])-det.begin();
		update(pos, g[i-1]);
		int lim = upper_bound(det.begin(), det.end(), d[i]-x[i])-det.begin()-1;
		ll best = ask(0, lim);
		opt = max(opt, g[i]-best);
	}
	printf("%lld\n", opt);
}

Compilation message

divide.cpp: In function 'int main()':
divide.cpp:58:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
divide.cpp:59:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 1; i<= n; i++) scanf("%lld %lld %lld", &x[i], &g[i], &d[i]);
                             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
17.0 / 17.0

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

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 3 ms 444 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 6 ms 384 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 6 ms 768 KB Output is correct
12 Correct 6 ms 768 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 768 KB Output is correct
2 Correct 8 ms 1152 KB Output is correct
3 Correct 9 ms 1280 KB Output is correct
4 Correct 35 ms 4096 KB Output is correct
5 Correct 37 ms 4472 KB Output is correct
6 Correct 79 ms 8812 KB Output is correct
7 Correct 64 ms 7532 KB Output is correct
8 Correct 66 ms 7536 KB Output is correct
9 Correct 65 ms 7404 KB Output is correct
10 Correct 65 ms 7404 KB Output is correct
11 Correct 71 ms 7848 KB Output is correct
12 Correct 71 ms 8044 KB Output is correct