oj.uz

Submission #344604

# Submission time Handle Problem Language Result Execution time Memory
344604 2021-01-06T06:32:36 Z maskoff Divide and conquer (IZhO14_divide) C++14
17 / 100
 8 ms 10092 KB 
#include <bits/stdc++.h>

#define file ""

#define all(x) x.begin(), x.end()

#define sc second
#define fr first

#define pb push_back
#define mp make_pair

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const ll inf = 1e18 + 5;
const ll mod = 1e9 + 7;

const int N = 5e5 + 5;

int dx[] = {+1, 0, -1, 0};
int dy[] = {0, +1, 0, -1};

struct pt{
 	int x, g, d;
};

vector<pt> a(N);
vector<int> pref(N), opt(N);

struct tree{
 	int mx;
 	int tag;
} t[N];

void build(int u, int l, int r) {
 	if (l == r) {
 	 	t[u].mx = a[l].x;
 	 	return;
 	}
 	int m = l + r >> 1;
 	build(u + u, l, m);
 	build(u + u + 1, m + 1, r);
 	t[u].mx = min(t[u + u].mx, t[u + u + 1].mx);
}

void push(int u, int l, int r) {
 	if (l == r || t[u].tag == 0) return;
 	t[u + u].mx += t[u].tag;
 	t[u + u + 1].mx += t[u].tag;
 	t[u + u + 1].tag += t[u].tag;
 	t[u + u].tag += t[u].tag;
 	t[u].tag = 0;
 	return;
}

void update(int u, int ul, int ur, int l, int r, int val) {
	push(u, ul, ur);
 	if (ul > r || l > ur) return;
 	if (l <= ul && ur <= r) {
 		t[u].mx += val;
 		t[u].tag += val;
 	 	return;
	}
	int um = ul + ur >> 1;
	update(u + u, ul, um, l, r, val);
	update(u + u + 1, um + 1, ur, l, r, val);
	t[u].mx = min(t[u + u].mx, t[u + u + 1].mx);
}

int get(int u, int ul, int ur, int l, int r) {
	push(u, ul, ur);
 	if (ul > r || l > ur || t[u].mx > 0) return -1;
 	if (ul == ur) return ul;
 	int um = ul + ur >> 1;
 	int res = get(u + u + 1, um + 1, ur, l, r);
 	if (res == -1) res = get(u + u, ul, um, l, r);
 	return res;
}


ll calc(int l, int r) {
	if (l == -1 || r == -1) return -1;
 	return pref[r] - pref[l - 1];
}


int main() {
	ios_base :: sync_with_stdio(false);               
	cin.tie(nullptr);
	srand(time(nullptr));
	int n;
	cin >> n;
	ll mx = 0;
	for (int i = 1; i <= n; i++) cin >> a[i].x >> a[i].g >> a[i].d, mx = max(mx, (ll)a[i].g); 
	for (int i = 1; i <= n; i++) pref[i] = pref[i - 1] + a[i].g;
	build(1, 1, n);
	for (int i = n; i >= 1; i--) {
		update(1, 1, n, i + 1, n, -a[i].x);
		update(1, 1, n, i, n, -a[i].d);
		opt[i] = get(1, 1, n, i, n);
		//cout << i << " " << opt[i] << endl;
		update(1, 1, n, i + 1, n, +a[i].x);
	}
	for (int i = 1; i <= n; i++) 
	 	mx = max(mx, calc(i, opt[i]));
	cout << mx << endl;
  return 0;              
}

Compilation message

divide.cpp: In function 'void build(int, int, int)':
divide.cpp:43:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |   int m = l + r >> 1;
      |           ~~^~~
divide.cpp: In function 'void update(int, int, int, int, int, int)':
divide.cpp:67:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   67 |  int um = ul + ur >> 1;
      |           ~~~^~~~
divide.cpp: In function 'int get(int, int, int, int, int)':
divide.cpp:77:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   77 |   int um = ul + ur >> 1;
      |            ~~~^~~~

Subtask #1
17.0 / 17.0

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

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 10092 KB Output is correct
2 Correct 7 ms 10092 KB Output is correct
3 Correct 7 ms 10092 KB Output is correct
4 Correct 7 ms 10092 KB Output is correct
5 Correct 7 ms 10092 KB Output is correct
6 Correct 7 ms 10092 KB Output is correct
7 Correct 7 ms 10092 KB Output is correct
8 Correct 7 ms 10092 KB Output is correct
9 Correct 8 ms 10092 KB Output is correct
10 Correct 7 ms 10092 KB Output is correct
11 Correct 7 ms 10092 KB Output is correct
12 Correct 7 ms 10092 KB Output is correct
13 Correct 7 ms 10092 KB Output is correct
14 Correct 8 ms 10092 KB Output is correct
15 Correct 8 ms 10092 KB Output is correct
16 Correct 8 ms 10092 KB Output is correct
17 Incorrect 8 ms 10092 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #3
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 10092 KB Output is correct
2 Correct 7 ms 10092 KB Output is correct
3 Correct 7 ms 10092 KB Output is correct
4 Correct 7 ms 10092 KB Output is correct
5 Correct 7 ms 10092 KB Output is correct
6 Correct 7 ms 10092 KB Output is correct
7 Correct 7 ms 10092 KB Output is correct
8 Correct 7 ms 10092 KB Output is correct
9 Correct 8 ms 10092 KB Output is correct
10 Correct 7 ms 10092 KB Output is correct
11 Correct 7 ms 10092 KB Output is correct
12 Correct 7 ms 10092 KB Output is correct
13 Correct 7 ms 10092 KB Output is correct
14 Correct 8 ms 10092 KB Output is correct
15 Correct 8 ms 10092 KB Output is correct
16 Correct 8 ms 10092 KB Output is correct
17 Incorrect 8 ms 10092 KB Output isn't correct
18 Halted 0 ms 0 KB -