oj.uz

Submission #157665

# Submission time Handle Problem Language Result Execution time Memory
157665 2019-10-12T16:58:12 Z HungAnhGoldIBO2020 Two Dishes (JOI19_dishes) C++14
5 / 100
 618 ms 58520 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));
}
vector<int> merge(vector<int> a, vector<int> b){
	int i=0,j=0;
	while(i<a.size()&&j<b.size()){
		
	}
}
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 'std::vector<long long int> merge(std::vector<long long int>, std::vector<long long int>)':
dishes.cpp:78:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(i<a.size()&&j<b.size()){
        ~^~~~~~~~~
dishes.cpp:78:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(i<a.size()&&j<b.size()){
                    ~^~~~~~~~~
dishes.cpp:81:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
dishes.cpp: In function 'int main()':
dishes.cpp:112:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j = 0; j < pts[i].size() ; j++){
              ~~^~~~~~~~~~~~~~~
dishes.cpp:115:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j = 0; j < pts[i].size() ; j++){
              ~~^~~~~~~~~~~~~~~
dishes.cpp:85: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 618 ms 58520 KB Output is correct
2 Correct 594 ms 57336 KB Output is correct
3 Correct 340 ms 49784 KB Output is correct
4 Correct 556 ms 54740 KB Output is correct
5 Correct 25 ms 23928 KB Output is correct
6 Correct 537 ms 55904 KB Output is correct
7 Correct 156 ms 40408 KB Output is correct
8 Correct 151 ms 37616 KB Output is correct
9 Correct 346 ms 49868 KB Output is correct
10 Correct 557 ms 57836 KB Output is correct
11 Correct 264 ms 50424 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 23888 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 23944 KB Output is correct
9 Correct 24 ms 23900 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 24 ms 23928 KB Output is correct
2 Correct 24 ms 23928 KB Output is correct
3 Correct 23 ms 23888 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 23944 KB Output is correct
9 Correct 24 ms 23900 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 24 ms 23928 KB Output is correct
2 Correct 24 ms 23928 KB Output is correct
3 Correct 23 ms 23888 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 23944 KB Output is correct
9 Correct 24 ms 23900 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 24 ms 23928 KB Output is correct
2 Correct 24 ms 23928 KB Output is correct
3 Correct 23 ms 23888 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 23944 KB Output is correct
9 Correct 24 ms 23900 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 24 ms 23928 KB Output is correct
2 Correct 24 ms 23928 KB Output is correct
3 Correct 23 ms 23888 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 23944 KB Output is correct
9 Correct 24 ms 23900 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 618 ms 58520 KB Output is correct
2 Correct 594 ms 57336 KB Output is correct
3 Correct 340 ms 49784 KB Output is correct
4 Correct 556 ms 54740 KB Output is correct
5 Correct 25 ms 23928 KB Output is correct
6 Correct 537 ms 55904 KB Output is correct
7 Correct 156 ms 40408 KB Output is correct
8 Correct 151 ms 37616 KB Output is correct
9 Correct 346 ms 49868 KB Output is correct
10 Correct 557 ms 57836 KB Output is correct
11 Correct 264 ms 50424 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 23888 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 23944 KB Output is correct
20 Correct 24 ms 23900 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 618 ms 58520 KB Output is correct
2 Correct 594 ms 57336 KB Output is correct
3 Correct 340 ms 49784 KB Output is correct
4 Correct 556 ms 54740 KB Output is correct
5 Correct 25 ms 23928 KB Output is correct
6 Correct 537 ms 55904 KB Output is correct
7 Correct 156 ms 40408 KB Output is correct
8 Correct 151 ms 37616 KB Output is correct
9 Correct 346 ms 49868 KB Output is correct
10 Correct 557 ms 57836 KB Output is correct
11 Correct 264 ms 50424 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 23888 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 23944 KB Output is correct
20 Correct 24 ms 23900 KB Output is correct
21 Incorrect 24 ms 23928 KB Output isn't correct
22 Halted 0 ms 0 KB -