oj.uz

Submission #157635

# Submission time Handle Problem Language Result Execution time Memory
157635 2019-10-12T16:13:27 Z HungAnhGoldIBO2020 Two Dishes (JOI19_dishes) C++14
0 / 100
 640 ms 56568 KB 
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 3;
const int inf = 1e18 + 2;
int it[4 * N], lazy[4 * N], sA[N], sB[N] ,s[N], t[N], p[N], q[N];
vector<pair<int, int> >  pts[N];
void init(int idx, int l, int r){
	it[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){
		lazy[idx] = 0;
		return;
	}
	it[idx << 1] += lazy[idx];
	it[idx << 1 | 1] += lazy[idx];
	lazy[idx << 1] += lazy[idx];
	lazy[idx << 1 | 1] += lazy[idx];
	lazy[idx] = 0;
}
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;
		return;
	}
	if(lazy[idx]){
		push(idx, l, r);
	}
	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 pos, int val){
	if(l > pos || r < pos){
		return;
	}
	if(l == r){
		it[idx] = val;
		lazy[idx] = 0;
		return;
	}
	if(lazy[idx]){
		push(idx, l, r);
	}
	int mid = (l + r) >> 1;
	upd(idx << 1, l, mid, pos, val);
	upd(idx << 1 | 1, mid + 1, r, pos, 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];
	}
	if(lazy[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);
	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);
		}			//chuan bi cho tong cac diem tu x' tro len
		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, k);
			//cout << i << ' ' << pts[i][j].first << ' ' << k << endl;
		}
//		for(j = 0; j <= m; j++){
//			k=getmax(1,0,m,0,j);
//			upd(1,0,m,j,k);
//		}
		if(i < n){
			for(j = 0; j < pts[i + 1].size(); j++){
				k = getmax(1, 0, m, 0, pts[i + 1][j].first);
				upd(1, 0, m, pts[i + 1][j].first, 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:119:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(j = 0; j < pts[i + 1].size(); j++){
               ~~^~~~~~~~~~~~~~~~~~~
dishes.cpp:78:21: warning: unused variable 'l' [-Wunused-variable]
  int n, m, i, j, k, l, sum_val = 0;
                     ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 640 ms 56568 KB Output is correct
2 Correct 626 ms 55632 KB Output is correct
3 Correct 358 ms 48232 KB Output is correct
4 Correct 565 ms 53108 KB Output is correct
5 Incorrect 30 ms 23928 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 23928 KB Output is correct
2 Correct 30 ms 23928 KB Output is correct
3 Correct 24 ms 23928 KB Output is correct
4 Correct 22 ms 23928 KB Output is correct
5 Incorrect 25 ms 23928 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 23928 KB Output is correct
2 Correct 30 ms 23928 KB Output is correct
3 Correct 24 ms 23928 KB Output is correct
4 Correct 22 ms 23928 KB Output is correct
5 Incorrect 25 ms 23928 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 23928 KB Output is correct
2 Correct 30 ms 23928 KB Output is correct
3 Correct 24 ms 23928 KB Output is correct
4 Correct 22 ms 23928 KB Output is correct
5 Incorrect 25 ms 23928 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 23928 KB Output is correct
2 Correct 30 ms 23928 KB Output is correct
3 Correct 24 ms 23928 KB Output is correct
4 Correct 22 ms 23928 KB Output is correct
5 Incorrect 25 ms 23928 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 23928 KB Output is correct
2 Correct 30 ms 23928 KB Output is correct
3 Correct 24 ms 23928 KB Output is correct
4 Correct 22 ms 23928 KB Output is correct
5 Incorrect 25 ms 23928 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 640 ms 56568 KB Output is correct
2 Correct 626 ms 55632 KB Output is correct
3 Correct 358 ms 48232 KB Output is correct
4 Correct 565 ms 53108 KB Output is correct
5 Incorrect 30 ms 23928 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 640 ms 56568 KB Output is correct
2 Correct 626 ms 55632 KB Output is correct
3 Correct 358 ms 48232 KB Output is correct
4 Correct 565 ms 53108 KB Output is correct
5 Incorrect 30 ms 23928 KB Output isn't correct
6 Halted 0 ms 0 KB -