oj.uz

Submission #247514

# Submission time Handle Problem Language Result Execution time Memory
247514 2020-07-11T14:37:12 Z gs18081 Two Dishes (JOI19_dishes) C++11
5 / 100
 1535 ms 52056 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1535 ms 51200 KB Output is correct
2 Correct 1330 ms 51292 KB Output is correct
3 Correct 1095 ms 51032 KB Output is correct
4 Correct 1032 ms 51648 KB Output is correct
5 Correct 6 ms 384 KB Output is correct
6 Correct 1319 ms 50648 KB Output is correct
7 Correct 643 ms 31448 KB Output is correct
8 Correct 141 ms 18924 KB Output is correct
9 Correct 1082 ms 52056 KB Output is correct
10 Correct 1422 ms 45016 KB Output is correct
11 Correct 996 ms 45400 KB Output is correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 512 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Incorrect 6 ms 384 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 512 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Incorrect 6 ms 384 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 512 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Incorrect 6 ms 384 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 512 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Incorrect 6 ms 384 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 512 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Incorrect 6 ms 384 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1535 ms 51200 KB Output is correct
2 Correct 1330 ms 51292 KB Output is correct
3 Correct 1095 ms 51032 KB Output is correct
4 Correct 1032 ms 51648 KB Output is correct
5 Correct 6 ms 384 KB Output is correct
6 Correct 1319 ms 50648 KB Output is correct
7 Correct 643 ms 31448 KB Output is correct
8 Correct 141 ms 18924 KB Output is correct
9 Correct 1082 ms 52056 KB Output is correct
10 Correct 1422 ms 45016 KB Output is correct
11 Correct 996 ms 45400 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 5 ms 384 KB Output is correct
19 Correct 5 ms 384 KB Output is correct
20 Correct 5 ms 384 KB Output is correct
21 Correct 5 ms 512 KB Output is correct
22 Correct 5 ms 384 KB Output is correct
23 Incorrect 6 ms 384 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1535 ms 51200 KB Output is correct
2 Correct 1330 ms 51292 KB Output is correct
3 Correct 1095 ms 51032 KB Output is correct
4 Correct 1032 ms 51648 KB Output is correct
5 Correct 6 ms 384 KB Output is correct
6 Correct 1319 ms 50648 KB Output is correct
7 Correct 643 ms 31448 KB Output is correct
8 Correct 141 ms 18924 KB Output is correct
9 Correct 1082 ms 52056 KB Output is correct
10 Correct 1422 ms 45016 KB Output is correct
11 Correct 996 ms 45400 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 5 ms 384 KB Output is correct
19 Correct 5 ms 384 KB Output is correct
20 Correct 5 ms 384 KB Output is correct
21 Correct 5 ms 512 KB Output is correct
22 Correct 5 ms 384 KB Output is correct
23 Incorrect 6 ms 384 KB Output isn't correct
24 Halted 0 ms 0 KB -