oj.uz

Submission #521581

# Submission time Handle Problem Language Result Execution time Memory
521581 2022-02-02T13:25:44 Z Kalashnikov Divide and conquer (IZhO14_divide) C++17
100 / 100
 188 ms 43000 KB 
#include <bits/stdc++.h>
 
#define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
#define all(a) a.begin() , a.end()
#define F first
#define S second
 
using namespace std;
using ll = long long;
 
const int N = 1e5+5 , inf = 2e9 + 7;
const ll INF = 1e18 ,   mod = 1e9+7 , P = 6547;

ll x[N] , g[N], d[N] , p[N] , ps[N];
ll t[10*N];
int sz = 1;
int n;
void upd(int pos , ll val , int u = 1, int ul = 1, int ur = 2*n) {
	t[u] = min(t[u] , val);
	if(ul == ur) {
		return;
	}
	int um = ul+ur >> 1;
	if(pos <= um) {
		upd(pos , val , u<<1 , ul , um);
	}
	else {
		upd(pos , val , u<<1|1 , um+1 , ur);
	}
}

ll get(int pos , int u = 1 , int ul = 1, int ur = 2*n) {
	if(pos <= ul) {
		return t[u];
	}
	if(ur < pos) return INF;
	int um = ul+ur >> 1;
	return min(get(pos , u<<1 , ul, um) , get(pos , u<<1|1 , um+1,ur));
}

void solve(int tc) {
	cin >> n;
	set<ll> st;
	fill(t , t+10*N , INF);
	for(int i = 1; i <= n; i ++) {
		cin >> x[i] >> g[i] >> d[i];
		p[i] = p[i-1] + d[i];
		ps[i] = ps[i-1] + g[i];
		st.insert(x[i] - p[i]);
		st.insert(x[i] - p[i-1]);
	}
	map<ll,int> mp;
	int cnt = 1;
	for(auto to: st) {
		mp[to] = cnt++;
	}
	ll ans = 0;
	for(int i = 1; i <= n; i ++) {
		upd(mp[x[i] - p[i-1]] , ps[i-1]);
		int cur = x[i] - p[i];
		ans = max(ans , ps[i] - get(mp[cur]));
	}
	cout << ans;
}
/*
*/
main() {
    ios;
    int tt = 1 , tc = 0;
    // cin >> tt;
    while(tt --) {
        solve(++tc);
    }
    return 0;
}

Compilation message

divide.cpp: In function 'void upd(int, ll, int, int, int)':
divide.cpp:24:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   24 |  int um = ul+ur >> 1;
      |           ~~^~~
divide.cpp: In function 'll get(int, int, int, int)':
divide.cpp:38:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |  int um = ul+ur >> 1;
      |           ~~^~~
divide.cpp: At global scope:
divide.cpp:68:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   68 | main() {
      | ^~~~

Subtask #1
17.0 / 17.0

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

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8140 KB Output is correct
2 Correct 4 ms 8128 KB Output is correct
3 Correct 4 ms 8140 KB Output is correct
4 Correct 4 ms 8140 KB Output is correct
5 Correct 6 ms 8140 KB Output is correct
6 Correct 4 ms 8140 KB Output is correct
7 Correct 4 ms 8140 KB Output is correct
8 Correct 4 ms 8140 KB Output is correct
9 Correct 4 ms 8128 KB Output is correct
10 Correct 4 ms 8140 KB Output is correct
11 Correct 4 ms 8132 KB Output is correct
12 Correct 6 ms 8176 KB Output is correct
13 Correct 4 ms 8124 KB Output is correct
14 Correct 4 ms 8136 KB Output is correct
15 Correct 4 ms 8268 KB Output is correct
16 Correct 4 ms 8268 KB Output is correct
17 Correct 5 ms 8396 KB Output is correct
18 Correct 5 ms 8528 KB Output is correct
19 Correct 5 ms 8400 KB Output is correct
20 Correct 5 ms 8396 KB Output is correct
21 Correct 5 ms 8524 KB Output is correct
22 Correct 7 ms 8652 KB Output is correct
23 Correct 11 ms 9548 KB Output is correct
24 Correct 10 ms 9548 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8140 KB Output is correct
2 Correct 4 ms 8128 KB Output is correct
3 Correct 4 ms 8140 KB Output is correct
4 Correct 4 ms 8140 KB Output is correct
5 Correct 6 ms 8140 KB Output is correct
6 Correct 4 ms 8140 KB Output is correct
7 Correct 4 ms 8140 KB Output is correct
8 Correct 4 ms 8140 KB Output is correct
9 Correct 4 ms 8128 KB Output is correct
10 Correct 4 ms 8140 KB Output is correct
11 Correct 4 ms 8132 KB Output is correct
12 Correct 6 ms 8176 KB Output is correct
13 Correct 4 ms 8124 KB Output is correct
14 Correct 4 ms 8136 KB Output is correct
15 Correct 4 ms 8268 KB Output is correct
16 Correct 4 ms 8268 KB Output is correct
17 Correct 5 ms 8396 KB Output is correct
18 Correct 5 ms 8528 KB Output is correct
19 Correct 5 ms 8400 KB Output is correct
20 Correct 5 ms 8396 KB Output is correct
21 Correct 5 ms 8524 KB Output is correct
22 Correct 7 ms 8652 KB Output is correct
23 Correct 11 ms 9548 KB Output is correct
24 Correct 10 ms 9548 KB Output is correct
25 Correct 9 ms 9420 KB Output is correct
26 Correct 20 ms 10828 KB Output is correct
27 Correct 20 ms 11164 KB Output is correct
28 Correct 75 ms 24904 KB Output is correct
29 Correct 88 ms 25212 KB Output is correct
30 Correct 188 ms 43000 KB Output is correct
31 Correct 150 ms 41676 KB Output is correct
32 Correct 173 ms 41760 KB Output is correct
33 Correct 138 ms 35588 KB Output is correct
34 Correct 159 ms 34844 KB Output is correct
35 Correct 152 ms 36064 KB Output is correct
36 Correct 149 ms 36264 KB Output is correct