oj.uz

Submission #157671

# Submission time Handle Problem Language Result Execution time Memory
157671 2019-10-12T17:07:10 Z HungAnhGoldIBO2020 Two Dishes (JOI19_dishes) C++14
5 / 100
 626 ms 56424 KB 
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 3;
const int inf = 1e18 + 2;
int it[N << 2], lazy[N << 2], sA[N], sB[N] ,s[N], t[N], p[N], q[N], ass[N << 2];
vector<pair<int, int> >  pts[N];
void init(int idx, int l, int r){
	it[idx] = -inf;
	ass[idx] = -inf;
	if(l == r){
		return;
	}
	int mid = (l + r) >> 1;
	init(idx << 1, l, mid);
	init(idx << 1 | 1, mid + 1, r);
}
void push(int idx, int l, int r){
	if(l == r){
		ass[idx] = -inf;
		lazy[idx] = 0;
		return;
	}
	ass[idx << 1] = max(ass[idx << 1] + lazy[idx], ass[idx]);
	ass[idx << 1 | 1] = max(ass[idx << 1 | 1] + lazy[idx], ass[idx]);
	it[idx << 1] = max(it[idx << 1] + lazy[idx], ass[idx]);
	it[idx << 1 | 1] = max(it[idx << 1 | 1] + lazy[idx], ass[idx]);
	lazy[idx << 1] += lazy[idx];
	lazy[idx << 1 | 1] += lazy[idx];
	lazy[idx] = 0;
	ass[idx] = -inf;
}
void add(int idx, int l, int r, int lef, int rig, int val){
	if(l > rig || r < lef){
		return;
	}
	if(l >= lef && r <= rig){
		it[idx] += val;
		lazy[idx] += val;
		ass[idx] += val;
		return;
	}
	push(idx, l, r);
	//cout << idx << ' ' << l << ' ' << r << ' ' << lef << ' ' << rig << ' ' << val <<endl;
	int mid = (l + r) >> 1;
	add(idx << 1, l, mid, lef, rig, val);
	add(idx << 1 | 1, mid + 1, r, lef, rig, val);
	it[idx] = max(ass[idx], max(it[idx << 1], it[idx << 1 | 1]));
}
void upd(int idx, int l, int r, int lef, int rig, int val){
	if(l > rig || r < lef){
		return;
	}
	if(l >= lef && r <= rig){
		ass[idx] = val;
		it[idx] = max(it[idx], val);
		return;
	}
	push(idx, l, r);
	int mid = (l + r) >> 1;
	upd(idx << 1, l, mid, lef, rig, val);
	upd(idx << 1 | 1, mid + 1, r, lef, rig, val);
	it[idx] = max(ass[idx], max(it[idx << 1], it[idx << 1 | 1]));
}
int getmax(int idx, int l, int r, int lef, int rig){
	if(l > rig || r < lef){
		return -inf;
	}
	if(l >= lef && r <= rig){
		return it[idx];
	}
	push(idx, l, r);
	int mid = (l + r) >> 1;
	return max(getmax(idx << 1, l, mid, lef, rig), getmax(idx << 1 | 1, mid + 1, r, lef, rig));
}
signed main(){
	ios :: sync_with_stdio(0);
	cin. tie(0);
	int n, m, i, j, k, l, sum_val = 0;
	cin >> n >> m;
	for(i = 1; i <= n; i++){
		cin >> j >> s[i] >> p[i];
		sA[i] = sA[i - 1] + j;
	}
	for(i = 1; i <= m; i++){
		cin >> j >> t[i] >> q[i];
		sB[i] = sB[i - 1] + j;
		sum_val += q[i];
	}
	for(i = 1; i <= n; i++){
		j = upper_bound(sB, sB + 1 + m, s[i] - sA[i]) - sB - 1;
		if(j >= 0){
			pts[i].push_back({j, p[i]});
		}
	}		//true
	for(i = 1; i <= m; i++){
		j = upper_bound(sA, sA + 1 + n, t[i] - sB[i]) - sA - 1;
		if(j < n){
			pts[j + 1].push_back({i - 1, -q[i]}); 
		}
	}	//true, why? consider the point moving which don't really affect the answer.
	init(1, 0, m);
	upd(1, 0, m, 0, 0, 0);
	pts[0].push_back({0, 0});
	for(i = 0; i <= n; i++){
		for(j = 0; j < pts[i].size() ; j++){
			add(1, 0, m, 0, pts[i][j].first, pts[i][j].second);
		}
		for(j = 0; j < pts[i].size() ; j++){
			k = getmax(1, 0, m, 0, pts[i][j].first);
			upd(1, 0, m, pts[i][j].first, m, k);
		}
	}
	cout << getmax(1, 0, m, 0, m) + sum_val;
}

Compilation message

dishes.cpp: In function 'int main()':
dishes.cpp:106:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j = 0; j < pts[i].size() ; j++){
              ~~^~~~~~~~~~~~~~~
dishes.cpp:109:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j = 0; j < pts[i].size() ; j++){
              ~~^~~~~~~~~~~~~~~
dishes.cpp:79:21: warning: unused variable 'l' [-Wunused-variable]
  int n, m, i, j, k, l, sum_val = 0;
                     ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 626 ms 56144 KB Output is correct
2 Correct 605 ms 55368 KB Output is correct
3 Correct 337 ms 47852 KB Output is correct
4 Correct 560 ms 52892 KB Output is correct
5 Correct 23 ms 23928 KB Output is correct
6 Correct 548 ms 55160 KB Output is correct
7 Correct 163 ms 38644 KB Output is correct
8 Correct 149 ms 36092 KB Output is correct
9 Correct 359 ms 49244 KB Output is correct
10 Correct 576 ms 56424 KB Output is correct
11 Correct 264 ms 49188 KB Output is correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23928 KB Output is correct
2 Correct 24 ms 23928 KB Output is correct
3 Correct 23 ms 23900 KB Output is correct
4 Correct 23 ms 23928 KB Output is correct
5 Correct 23 ms 23928 KB Output is correct
6 Correct 24 ms 23928 KB Output is correct
7 Correct 24 ms 23928 KB Output is correct
8 Correct 24 ms 23928 KB Output is correct
9 Correct 24 ms 23928 KB Output is correct
10 Incorrect 28 ms 23928 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23928 KB Output is correct
2 Correct 24 ms 23928 KB Output is correct
3 Correct 23 ms 23900 KB Output is correct
4 Correct 23 ms 23928 KB Output is correct
5 Correct 23 ms 23928 KB Output is correct
6 Correct 24 ms 23928 KB Output is correct
7 Correct 24 ms 23928 KB Output is correct
8 Correct 24 ms 23928 KB Output is correct
9 Correct 24 ms 23928 KB Output is correct
10 Incorrect 28 ms 23928 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23928 KB Output is correct
2 Correct 24 ms 23928 KB Output is correct
3 Correct 23 ms 23900 KB Output is correct
4 Correct 23 ms 23928 KB Output is correct
5 Correct 23 ms 23928 KB Output is correct
6 Correct 24 ms 23928 KB Output is correct
7 Correct 24 ms 23928 KB Output is correct
8 Correct 24 ms 23928 KB Output is correct
9 Correct 24 ms 23928 KB Output is correct
10 Incorrect 28 ms 23928 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23928 KB Output is correct
2 Correct 24 ms 23928 KB Output is correct
3 Correct 23 ms 23900 KB Output is correct
4 Correct 23 ms 23928 KB Output is correct
5 Correct 23 ms 23928 KB Output is correct
6 Correct 24 ms 23928 KB Output is correct
7 Correct 24 ms 23928 KB Output is correct
8 Correct 24 ms 23928 KB Output is correct
9 Correct 24 ms 23928 KB Output is correct
10 Incorrect 28 ms 23928 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23928 KB Output is correct
2 Correct 24 ms 23928 KB Output is correct
3 Correct 23 ms 23900 KB Output is correct
4 Correct 23 ms 23928 KB Output is correct
5 Correct 23 ms 23928 KB Output is correct
6 Correct 24 ms 23928 KB Output is correct
7 Correct 24 ms 23928 KB Output is correct
8 Correct 24 ms 23928 KB Output is correct
9 Correct 24 ms 23928 KB Output is correct
10 Incorrect 28 ms 23928 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 626 ms 56144 KB Output is correct
2 Correct 605 ms 55368 KB Output is correct
3 Correct 337 ms 47852 KB Output is correct
4 Correct 560 ms 52892 KB Output is correct
5 Correct 23 ms 23928 KB Output is correct
6 Correct 548 ms 55160 KB Output is correct
7 Correct 163 ms 38644 KB Output is correct
8 Correct 149 ms 36092 KB Output is correct
9 Correct 359 ms 49244 KB Output is correct
10 Correct 576 ms 56424 KB Output is correct
11 Correct 264 ms 49188 KB Output is correct
12 Correct 24 ms 23928 KB Output is correct
13 Correct 24 ms 23928 KB Output is correct
14 Correct 23 ms 23900 KB Output is correct
15 Correct 23 ms 23928 KB Output is correct
16 Correct 23 ms 23928 KB Output is correct
17 Correct 24 ms 23928 KB Output is correct
18 Correct 24 ms 23928 KB Output is correct
19 Correct 24 ms 23928 KB Output is correct
20 Correct 24 ms 23928 KB Output is correct
21 Incorrect 28 ms 23928 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 626 ms 56144 KB Output is correct
2 Correct 605 ms 55368 KB Output is correct
3 Correct 337 ms 47852 KB Output is correct
4 Correct 560 ms 52892 KB Output is correct
5 Correct 23 ms 23928 KB Output is correct
6 Correct 548 ms 55160 KB Output is correct
7 Correct 163 ms 38644 KB Output is correct
8 Correct 149 ms 36092 KB Output is correct
9 Correct 359 ms 49244 KB Output is correct
10 Correct 576 ms 56424 KB Output is correct
11 Correct 264 ms 49188 KB Output is correct
12 Correct 24 ms 23928 KB Output is correct
13 Correct 24 ms 23928 KB Output is correct
14 Correct 23 ms 23900 KB Output is correct
15 Correct 23 ms 23928 KB Output is correct
16 Correct 23 ms 23928 KB Output is correct
17 Correct 24 ms 23928 KB Output is correct
18 Correct 24 ms 23928 KB Output is correct
19 Correct 24 ms 23928 KB Output is correct
20 Correct 24 ms 23928 KB Output is correct
21 Incorrect 28 ms 23928 KB Output isn't correct
22 Halted 0 ms 0 KB -