Submission #157654

#	Time	Username	Problem	Language	Result	Execution time	Memory
157654		HungAnhGoldIBO2020	Two Dishes (JOI19_dishes)	C++14	5 / 100	838 ms	66876 KiB

dishes

#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 (stderr)

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 / 5
• Subtask 2: 0 / 3
• Subtask 3: 0 / 7
• Subtask 4: 0 / 39
• Subtask 5: 0 / 11
• Subtask 6: 0 / 9
• Subtask 7: 0 / 17
• Subtask 8: 0 / 9