제출 #123313

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
123313		gs14004	Two Dishes (JOI19_dishes)	C++17	5 / 100	430 ms	26116 KiB

dishes

#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];
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);
	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(); i++){
		seg.add(0, v[i].y, 0, m + 1, 1, v[i].c);
		while(pw < w.size() && pi(w[pw].x, w[pw].y) <= pi(v[i].x, v[i].y)){
			seg.add(w[pw].y + 1, m + 1, 0, m + 1, 1, w[pw].c);
			pw++;
		}
		lint val = seg.query(v[i].y, 0, m + 1, 1); 
		seg.upperize(v[i].y, m + 1, 0, m + 1, 1, val);
	}
	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;
}

컴파일 시 표준 에러 (stderr) 메시지

dishes.cpp: In function 'int main()':
dishes.cpp:113:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1; i<v.size(); i++){
               ~^~~~~~~~~
dishes.cpp:115:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(pw < w.size() && pi(w[pw].x, w[pw].y) <= pi(v[i].x, v[i].y)){
         ~~~^~~~~~~~~~
dishes.cpp:84: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:86: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:90: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: 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