oj.uz

답안 #157670

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
157670 2019-10-12T17:05:17 Z HungAnhGoldIBO2020 Two Dishes (JOI19_dishes) C++14
0 / 100
 619 ms 57408 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(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++){
			if(pts[i][j].first){
				k = getmax(1, 0, m, 0, pts[i][j].first - 1);
				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
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 619 ms 57408 KB Output is correct
2 Correct 601 ms 56508 KB Output is correct
3 Correct 424 ms 49116 KB Output is correct
4 Correct 553 ms 54108 KB Output is correct
5 Incorrect 24 ms 23928 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 23928 KB Output is correct
2 Correct 23 ms 23904 KB Output is correct
3 Correct 24 ms 24056 KB Output is correct
4 Correct 24 ms 23884 KB Output is correct
5 Incorrect 23 ms 23908 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 23928 KB Output is correct
2 Correct 23 ms 23904 KB Output is correct
3 Correct 24 ms 24056 KB Output is correct
4 Correct 24 ms 23884 KB Output is correct
5 Incorrect 23 ms 23908 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 23928 KB Output is correct
2 Correct 23 ms 23904 KB Output is correct
3 Correct 24 ms 24056 KB Output is correct
4 Correct 24 ms 23884 KB Output is correct
5 Incorrect 23 ms 23908 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 23928 KB Output is correct
2 Correct 23 ms 23904 KB Output is correct
3 Correct 24 ms 24056 KB Output is correct
4 Correct 24 ms 23884 KB Output is correct
5 Incorrect 23 ms 23908 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 23928 KB Output is correct
2 Correct 23 ms 23904 KB Output is correct
3 Correct 24 ms 24056 KB Output is correct
4 Correct 24 ms 23884 KB Output is correct
5 Incorrect 23 ms 23908 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 619 ms 57408 KB Output is correct
2 Correct 601 ms 56508 KB Output is correct
3 Correct 424 ms 49116 KB Output is correct
4 Correct 553 ms 54108 KB Output is correct
5 Incorrect 24 ms 23928 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 619 ms 57408 KB Output is correct
2 Correct 601 ms 56508 KB Output is correct
3 Correct 424 ms 49116 KB Output is correct
4 Correct 553 ms 54108 KB Output is correct
5 Incorrect 24 ms 23928 KB Output isn't correct
6 Halted 0 ms 0 KB -