oj.uz

답안 #123337

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
123337 2019-07-01T07:34:33 Z 구재현(#3026) Two Dishes (JOI19_dishes) C++14
10 / 100
 6 ms 760 KB 
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000005;
const int MAXT = 2100000;
const int mod = 1e9 + 7;
using lint = long long;
using pi = pair<int, int>;

struct pnt{
	int x, y;
	lint c;
	bool operator<(const pnt &p)const{
		return pi(x, y) < pi(p.x, p.y);
	}
};

struct seg{
	lint lazy[MAXT], tree[MAXT];
	void lazydown(int p){
		lazy[2*p] += lazy[p];
		lazy[2*p+1] += lazy[p];
		tree[2*p] += lazy[p];
		tree[2*p+1] += lazy[p];
		lazy[p] = 0;
		tree[2*p] = max(tree[2*p], tree[p]);
		tree[2*p+1] = max(tree[2*p+1], tree[p]);
		tree[p] = 0;
	}
	void add(int s, int e, int ps, int pe, int p, lint v){
		if(e < ps || pe < s) return;
		if(s <= ps && pe <= e){
			lazy[p] += v;
			tree[p] += v;
			return;
		}
		int pm = (ps + pe) / 2;
		lazydown(p);
		add(s, e, ps, pm, 2*p, v);
		add(s, e, pm + 1, pe, 2*p + 1, v);
	}
	void upperize(int s, int e, int ps, int pe, int p, lint v){
		if(e < ps || pe < s) return;
		if(s <= ps && pe <= e){
			tree[p] = max(tree[p], v);
			return;
		}
		int pm = (ps + pe) / 2;
		lazydown(p);
		upperize(s, e, ps, pm, 2*p, v);
		upperize(s, e, pm+1, pe, 2*p+1, v);
	}
	lint query(int pos, int s, int e, int p){
		if(s == e) return tree[p];
		int m = (s + e) / 2;
		lazydown(p);
		if(pos <= m) return query(pos, s, m, 2*p);
		return query(pos, m+1, e, 2*p+1);
	}
}seg;

int n, m;
lint a[MAXN], s[MAXN], p[MAXN];
lint b[MAXN], t[MAXN], q[MAXN];
int da[MAXN], db[MAXN];
lint dp[MAXN];
vector<pnt> v, w;

lint getCostV(int s, int e, int x){
	lint ret = 0;
	for(auto &i : v){
		if(s <= i.x && i.x <= e && i.y >= x) ret += i.c; 
	}
	return ret;
}

lint getCostW(int s, int e, int x){
	lint ret = 0;
	for(auto &i : w){
		if(s <= i.x && i.x <= e && i.y <= x) ret += i.c; 
	}
	return ret;
}

int main(){
	scanf("%d %d",&n,&m);
	if(n > 2000 || m > 2000) return 0;
	for(int i=1; i<=n; i++){
		scanf("%lld %lld %lld",&a[i],&s[i],&p[i]);
		a[i] += a[i-1];
	}
	for(int i=1; i<=m; i++){
		scanf("%lld %lld %lld",&b[i],&t[i],&q[i]);
		b[i] += b[i-1];
	}
	lint ret = 0;
	v.push_back({0, 0, 0});
	for(int i=1; i<=n; i++){
		da[i] = upper_bound(b, b + m + 1, s[i] - a[i]) - b;
		if(da[i] > 0){
			if(p[i] > 0) v.push_back({i, da[i], p[i]});
			else w.push_back({i, da[i], -p[i]}), ret += p[i];
		}
	}
	for(int i=1; i<=m; i++){
		db[i] = upper_bound(a, a + n + 1, t[i] - b[i]) - a;
		if(db[i] > 0){
			if(q[i] > 0) w.push_back({db[i], i, q[i]});
			else v.push_back({db[i], i, -q[i]}), ret += q[i];
		}
	}
	sort(v.begin(), v.end());
	sort(w.begin(), w.end());
	v.push_back({n + 1, m + 1, 0});
	int pw = 0;
	for(int i=1; i<v.size(); ){
		int e = i;
		while(e < v.size() && v[e].x == v[i].x) e++;
		for(int j = i; j < e; j++){
			seg.add(0, v[j].y, 0, m + 1, 1, v[j].c);
		}
		while(pw < w.size() && w[pw].x <= v[i].x){
			seg.add(w[pw].y + 1, m + 1, 0, m + 1, 1, w[pw].c);
			pw++;
		}
		for(int j = i; j < e; j++){
			lint val = seg.query(v[j].y, 0, m + 1, 1);
			seg.upperize(v[j].y, m + 1, 0, m + 1, 1, val);
		}
		i = e;
	}
	lint dap = -1e18;
	for(int i=0; i<m+2; i++) dap = max(dap, seg.query(i, 0, m+1, 1));
	cout << ret + dap << endl;
}

Compilation message

dishes.cpp: In function 'int main()':
dishes.cpp:115:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1; i<v.size(); ){
               ~^~~~~~~~~
dishes.cpp:117:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(e < v.size() && v[e].x == v[i].x) e++;
         ~~^~~~~~~~~~
dishes.cpp:121:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(pw < w.size() && w[pw].x <= v[i].x){
         ~~~^~~~~~~~~~
dishes.cpp:85:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~
dishes.cpp:88:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld %lld",&a[i],&s[i],&p[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dishes.cpp:92:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld %lld",&b[i],&t[i],&q[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 4 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 3 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 4 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 3 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 5 ms 632 KB Output is correct
18 Correct 5 ms 632 KB Output is correct
19 Correct 6 ms 632 KB Output is correct
20 Correct 5 ms 760 KB Output is correct
21 Correct 6 ms 632 KB Output is correct
22 Correct 6 ms 632 KB Output is correct
23 Correct 5 ms 632 KB Output is correct

Subtask #4
0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 4 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 3 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 5 ms 632 KB Output is correct
18 Correct 5 ms 632 KB Output is correct
19 Correct 6 ms 632 KB Output is correct
20 Correct 5 ms 760 KB Output is correct
21 Correct 6 ms 632 KB Output is correct
22 Correct 6 ms 632 KB Output is correct
23 Correct 5 ms 632 KB Output is correct
24 Incorrect 2 ms 376 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 4 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 3 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 5 ms 632 KB Output is correct
18 Correct 5 ms 632 KB Output is correct
19 Correct 6 ms 632 KB Output is correct
20 Correct 5 ms 760 KB Output is correct
21 Correct 6 ms 632 KB Output is correct
22 Correct 6 ms 632 KB Output is correct
23 Correct 5 ms 632 KB Output is correct
24 Incorrect 2 ms 376 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 4 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 3 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 5 ms 632 KB Output is correct
18 Correct 5 ms 632 KB Output is correct
19 Correct 6 ms 632 KB Output is correct
20 Correct 5 ms 760 KB Output is correct
21 Correct 6 ms 632 KB Output is correct
22 Correct 6 ms 632 KB Output is correct
23 Correct 5 ms 632 KB Output is correct
24 Incorrect 2 ms 376 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #7
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -