Submission #247514

#	Time	Username	Problem	Language	Result	Execution time	Memory
247514		gs18081	Two Dishes (JOI19_dishes)	C++11	5 / 100	1535 ms	52056 KiB

dishes

#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;
typedef pair<ll,ll> pl;
typedef tuple<ll,ll,ll> tl;

const int MAXN = 1010101;
const ll MAX = 4e15;


struct segtree{
	ll tree[MAXN * 4];
	ll lazy1[MAXN * 4];
	ll lazy2[MAXN * 4];
	int lazy2c[MAXN * 4];
	int n;
	segtree(){}
	void resize(int _n){
		n = _n;
		init(1,0,n);
	}
	void init(int node,int s,int e){
		tree[node] = lazy1[node] = lazy2[node] = lazy2c[node] = 0;
		if(s != e){
			int m = (s + e) >> 1;
			init(node<<1,s,m);
			init(node<<1 | 1,m + 1,e);
		}
	}
	void laz(int node,int s,int e,int t){
		if(!t) return;
		if(s != e){
			if(lazy2c[node]){
				lazy1[node << 1] = 0;
				lazy1[node << 1 | 1] = 0;
				lazy2[node << 1] = lazy2[node];
				lazy2[node << 1 | 1] = lazy2[node];
				lazy2c[node << 1] = 1;
				lazy2c[node << 1 | 1] = 1;
			}
			lazy1[node << 1] += lazy1[node];
			lazy1[node << 1 | 1] += lazy1[node];
			laz(node << 1 , s , (s + e) >> 1 , t - 1);
			laz(node << 1 | 1 ,  ((s + e) >> 1) + 1 ,e , t - 1);
		}
		if(lazy2c[node]){
			tree[node] = lazy2[node];
			lazy2c[node] = 0;
		}
		tree[node] += lazy1[node];
		lazy1[node] = 0;
	}
	int query(int node,int s,int e,ll v){
		int m = (s + e) >> 1;
		laz(node,s,e,2);
		if(tree[node] <= v) return n + 1;
		if(s == e) return s;
		if(tree[node << 1] <= v) return query(node << 1 | 1,m + 1,e,v);
		return query(node << 1 , s, m ,v);
	}
	int query(ll v){
		return query(1,0,n,v);
	}
	void update1(int node,int s,int e,int l,int r,ll v){
		int m = (s + e) >> 1;
		laz(node,s,e,2);
		if(e < l||r < s) return;
		if(l <= s && e <= r){
			lazy1[node] = v;
			laz(node,s,e,2);
			return;
		}
		update1(node << 1,s,m,l,r,v);
		update1(node << 1 | 1,m + 1,e,l,r,v);
		tree[node] = max(tree[node<<1],tree[node<<1|1]);
	}
	void update1(int l,int r,ll v){ update1(1,0,n,l,r,v);}
	void update2(int node,int s,int e,int l,int r,ll v){
		int m = (s + e) >> 1;
		laz(node,s,e,2);
		if(e < l||r < s) return;
		if(l <= s && e <= r){
			lazy2[node] = v;
			lazy2c[node] = 1;
			laz(node,s,e,2);
			return;
		}
		update2(node << 1,s,m,l,r,v);
		update2(node << 1 | 1,m + 1,e,l,r,v);
		tree[node] = max(tree[node<<1],tree[node<<1|1]);
	}
	void update2(int l,int r,ll v){ update2(1,0,n,l,r,v);}
	ll getv(int node,int s,int e,int pos){
		int m = (s + e) >> 1;
		laz(node,s,e,2);
		if(e < pos || pos < s) return 0;
		if(s == e) return tree[node];
		return getv(node<<1,s,m,pos) + getv(node<<1|1,m+1,e,pos);
	}
	ll getv(int pos){return getv(1,0,n,pos);}
}myseg;

int N,M;
ll A[MAXN],S[MAXN],P[MAXN];
ll B[MAXN],T[MAXN],Q[MAXN];
int Apos[MAXN],Bpos[MAXN];
vector<tl> change;
ll ans;



int main(){
	scanf("%d %d",&N,&M);
	myseg.resize(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];
		Bpos[i] = upper_bound(A,A + N + 1,T[i] - B[i]) - A - 1;
		if(Bpos[i] != -1)change.push_back(tl(Bpos[i] + 1 , i - 1,-Q[i]));
		if(Bpos[i] != -1)ans += Q[i];
	}
	for(int i=1;i<=N;i++){
		Apos[i] = upper_bound(B,B + M + 1,S[i] - A[i]) - B - 1;
		change.push_back(tl(i, Apos[i],P[i]));
	}
	change.push_back(tl(N + 1,M - 1 , -MAX));
	sort(change.begin(),change.end(),[&](tl a,tl b){
		if(get<0>(a) != get<0>(b)) return get<0>(a) < get<0>(b);
		return get<1>(a) < get<1>(b);
	});
	int cpos = 0;
	int ncpos;
	while(cpos < change.size() && get<0>(change[cpos]) == 0) cpos++;
	for(int i=1;i<=N + 1;i++){
		for(ncpos=cpos;ncpos < change.size() && get<0>(change[ncpos]) == i;ncpos++);
		for(int j=cpos;j<ncpos;j++){
			myseg.update1(0,get<1>(change[j]) , get<2>(change[j]));
//			printf("done1 %lld %lld %lld\n",get<0>(change[j]),get<1>(change[j]),get<2>(change[j]));
//		for(int k=0;k<=M;k++) printf("%lld ",myseg.getv(k) + ans);
//		printf("\n");
		}
		for(int j=cpos;j<ncpos;j++){
			int nxt; 
			if(j == ncpos - 1) nxt = M;
			else nxt = get<1>(change[j + 1]);
			int tp = myseg.query(myseg.getv(get<1>(change[j])));
			if(tp <= nxt) myseg.update2(get<1>(change[j]) + 1 , tp - 1 , myseg.getv(get<1>(change[j])));
			else myseg.update2(get<1>(change[j]) + 1 , nxt , myseg.getv(get<1>(change[j])));
//			printf("done2 %lld %lld %lld\n",get<0>(change[j]),get<1>(change[j]),get<2>(change[j]));
//		for(int k=0;k<=M;k++) printf("%lld ",myseg.getv(k) + ans);
//		printf("\n");
		}
		cpos = ncpos;
//		printf("%d\n",i);
//		for(int k=0;k<=M;k++) printf("%lld ",myseg.getv(k) + ans);
//		printf("\n");
	}
	printf("%lld\n",myseg.getv(M) + ans);
	return 0;
}

Compilation message (stderr)

dishes.cpp: In function 'int main()':
dishes.cpp:139:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(cpos < change.size() && get<0>(change[cpos]) == 0) cpos++;
        ~~~~~^~~~~~~~~~~~~~~
dishes.cpp:141:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(ncpos=cpos;ncpos < change.size() && get<0>(change[ncpos]) == i;ncpos++);
                  ~~~~~~^~~~~~~~~~~~~~~
dishes.cpp:115: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:118: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:122: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