oj.uz

Submission #157654

# Submission time Handle Problem Language Result Execution time Memory
157654 2019-10-12T16:49:35 Z HungAnhGoldIBO2020 Two Dishes (JOI19_dishes) C++14
5 / 100
 838 ms 66876 KB 
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 3;
const int inf = 1e16 + 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(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(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]});
		}
		pts[i].push_back({0, 0});
	}		//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});
	sort(pts[0].begin(), pts[0].end());
	for(i = 0; i <= n; i++){
		sort(pts[i + 1].begin(), pts[i + 1].end());
		for(j = 0; j < pts[i].size(); j++){
			add(1, 0, m, 0, pts[i][j].first, pts[i][j].second);
		}
		pts[i].push_back({m + 1, 0});
		for(j = 0; j < pts[i].size() - 1; j++){
			k = getmax(1, 0, m, 0, min(pts[i][j].first, m));
			upd(1, 0, m, pts[i][j].first,pts[i][j + 1].first-1, k);
		}
	}
	cout << getmax(1, 0, m, 0, m) + sum_val;
}

Compilation message

dishes.cpp: In function 'int main()':
dishes.cpp:109:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j = 0; j < pts[i].size(); j++){
              ~~^~~~~~~~~~~~~~~
dishes.cpp:113:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j = 0; j < pts[i].size() - 1; 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 838 ms 64528 KB Output is correct
2 Correct 815 ms 63844 KB Output is correct
3 Correct 582 ms 57336 KB Output is correct
4 Correct 756 ms 60064 KB Output is correct
5 Correct 24 ms 23924 KB Output is correct
6 Correct 764 ms 66876 KB Output is correct
7 Correct 159 ms 42868 KB Output is correct
8 Correct 194 ms 49272 KB Output is correct
9 Correct 577 ms 61796 KB Output is correct
10 Correct 760 ms 66320 KB Output is correct
11 Correct 510 ms 62212 KB Output is correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23928 KB Output is correct
2 Correct 24 ms 23928 KB Output is correct
3 Correct 24 ms 23928 KB Output is correct
4 Correct 24 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 23 ms 23928 KB Output is correct
8 Correct 24 ms 24056 KB Output is correct
9 Correct 24 ms 23928 KB Output is correct
10 Incorrect 24 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 23 ms 23928 KB Output is correct
2 Correct 24 ms 23928 KB Output is correct
3 Correct 24 ms 23928 KB Output is correct
4 Correct 24 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 23 ms 23928 KB Output is correct
8 Correct 24 ms 24056 KB Output is correct
9 Correct 24 ms 23928 KB Output is correct
10 Incorrect 24 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 23 ms 23928 KB Output is correct
2 Correct 24 ms 23928 KB Output is correct
3 Correct 24 ms 23928 KB Output is correct
4 Correct 24 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 23 ms 23928 KB Output is correct
8 Correct 24 ms 24056 KB Output is correct
9 Correct 24 ms 23928 KB Output is correct
10 Incorrect 24 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 23 ms 23928 KB Output is correct
2 Correct 24 ms 23928 KB Output is correct
3 Correct 24 ms 23928 KB Output is correct
4 Correct 24 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 23 ms 23928 KB Output is correct
8 Correct 24 ms 24056 KB Output is correct
9 Correct 24 ms 23928 KB Output is correct
10 Incorrect 24 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 23 ms 23928 KB Output is correct
2 Correct 24 ms 23928 KB Output is correct
3 Correct 24 ms 23928 KB Output is correct
4 Correct 24 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 23 ms 23928 KB Output is correct
8 Correct 24 ms 24056 KB Output is correct
9 Correct 24 ms 23928 KB Output is correct
10 Incorrect 24 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 838 ms 64528 KB Output is correct
2 Correct 815 ms 63844 KB Output is correct
3 Correct 582 ms 57336 KB Output is correct
4 Correct 756 ms 60064 KB Output is correct
5 Correct 24 ms 23924 KB Output is correct
6 Correct 764 ms 66876 KB Output is correct
7 Correct 159 ms 42868 KB Output is correct
8 Correct 194 ms 49272 KB Output is correct
9 Correct 577 ms 61796 KB Output is correct
10 Correct 760 ms 66320 KB Output is correct
11 Correct 510 ms 62212 KB Output is correct
12 Correct 23 ms 23928 KB Output is correct
13 Correct 24 ms 23928 KB Output is correct
14 Correct 24 ms 23928 KB Output is correct
15 Correct 24 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 23 ms 23928 KB Output is correct
19 Correct 24 ms 24056 KB Output is correct
20 Correct 24 ms 23928 KB Output is correct
21 Incorrect 24 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 838 ms 64528 KB Output is correct
2 Correct 815 ms 63844 KB Output is correct
3 Correct 582 ms 57336 KB Output is correct
4 Correct 756 ms 60064 KB Output is correct
5 Correct 24 ms 23924 KB Output is correct
6 Correct 764 ms 66876 KB Output is correct
7 Correct 159 ms 42868 KB Output is correct
8 Correct 194 ms 49272 KB Output is correct
9 Correct 577 ms 61796 KB Output is correct
10 Correct 760 ms 66320 KB Output is correct
11 Correct 510 ms 62212 KB Output is correct
12 Correct 23 ms 23928 KB Output is correct
13 Correct 24 ms 23928 KB Output is correct
14 Correct 24 ms 23928 KB Output is correct
15 Correct 24 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 23 ms 23928 KB Output is correct
19 Correct 24 ms 24056 KB Output is correct
20 Correct 24 ms 23928 KB Output is correct
21 Incorrect 24 ms 23928 KB Output isn't correct
22 Halted 0 ms 0 KB -