oj.uz

Submission #68438

# Submission time Handle Problem Language Result Execution time Memory
68438 2018-08-17T07:06:31 Z ekrem Divide and conquer (IZhO14_divide) C++
100 / 100
 300 ms 33916 KB 
#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define inf 1000000007
#define orta ((bas + son)/2)
#define sol (k+k)
#define sag (k+k+1)
#define N 1000005
using namespace std;

typedef long long ll;

ll n, m, ans, a[N], b[N], c[N], suf[N], gol[N], seg[4*N];
pair < ll , ll > mx;
map < ll , ll > h, yer;
map < ll , ll > :: iterator it;

void up(ll k, ll bas, ll son, ll x, ll y){
	if(bas == son){
		seg[k] = min(seg[k], y);
		return;
	}
	if(x <= orta)
		up(sol, bas, orta, x, y);
	else
		up(sag, orta + 1, son, x, y);
	seg[k] = min(seg[sol] , seg[sag]);
}

ll qu(ll k, ll bas, ll son, ll x, ll y){
	if(bas > y or son < x)
		return inf;
	if(bas >= x and son <= y)
		return seg[k];
	return min(qu(sol, bas, orta, x, y), qu(sag, orta + 1, son, x, y));
}

void bu(ll k, ll bas, ll son){
	if(bas == son){
		seg[k] = inf;
		return;
	}
	bu(sol, bas, orta);
	bu(sag, orta + 1, son);
	seg[k] = inf;
}

int main() {
	// freopen("in.txt", "r", stdin);
	// freopen("outt.txt", "w", stdout);
	scanf("%lld",&n);
	for(ll i = 1; i <= n; i++)
		scanf("%lld %lld %lld",a + i, b + i, c + i);
	for(ll i = n; i >= 1; i--){
		suf[i] = suf[i + 1] + c[i];
		gol[i] = gol[i + 1] + b[i];
		h[suf[i] + a[i] ]++;
		h[suf[i + 1] + a[i] ]++;
	}
	for(it = h.begin(); it != h.end(); it++)
		yer[it->st] = ++m;

	bu(1, 1, m);

	for(ll i = 1; i <= n; i++){
		up(1, 1, m, yer[suf[i] + a[i] ], i);
		ll j = qu(1, 1, m, yer[suf[i + 1] + a[i] ], m);
		ans = max(ans, gol[j] - gol[i + 1]);
		// cout << j << " , " << i << " -> " << gol[j] << " , " << gol[i + 1] << " -> " << ans << endl;
	}
	printf("%lld\n", ans);
	return 0;
}

Compilation message

divide.cpp: In function 'int main()':
divide.cpp:53:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld",&n);
  ~~~~~^~~~~~~~~~~
divide.cpp:55:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld %lld",a + i, b + i, c + i);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
17.0 / 17.0

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

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 688 KB Output is correct
2 Correct 2 ms 688 KB Output is correct
3 Correct 3 ms 820 KB Output is correct
4 Correct 3 ms 828 KB Output is correct
5 Correct 4 ms 852 KB Output is correct
6 Correct 5 ms 1108 KB Output is correct
7 Correct 4 ms 1108 KB Output is correct
8 Correct 3 ms 1108 KB Output is correct
9 Correct 5 ms 1132 KB Output is correct
10 Correct 4 ms 1276 KB Output is correct
11 Correct 11 ms 2300 KB Output is correct
12 Correct 12 ms 2304 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 2304 KB Output is correct
2 Correct 19 ms 3980 KB Output is correct
3 Correct 22 ms 3980 KB Output is correct
4 Correct 125 ms 17224 KB Output is correct
5 Correct 128 ms 17224 KB Output is correct
6 Correct 300 ms 33780 KB Output is correct
7 Correct 268 ms 33780 KB Output is correct
8 Correct 273 ms 33808 KB Output is correct
9 Correct 253 ms 33808 KB Output is correct
10 Correct 242 ms 33808 KB Output is correct
11 Correct 273 ms 33820 KB Output is correct
12 Correct 262 ms 33916 KB Output is correct