oj.uz

Submission #163690

# Submission time Handle Problem Language Result Execution time Memory
163690 2019-11-14T16:09:42 Z TadijaSebez Two Dishes (JOI19_dishes) C++11
100 / 100
 8633 ms 218148 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int N=1e6+50;
const int M=2*N;
const ll inf=3e18;
ll ckmx(ll &a, ll b){ return a=max(a,b);}
int ls[M],rs[M],tsz,root;
ll lzy[M][2],mx[M];
void Upd(int c, ll x, int t)
{
	if(t==0) mx[c]+=x,lzy[c][0]+=x,lzy[c][1]+=x;
	else ckmx(mx[c],x),ckmx(lzy[c][1],x);
}
void Push(int c)
{
	Upd(ls[c],lzy[c][0],0);Upd(ls[c],lzy[c][1],1);
	Upd(rs[c],lzy[c][0],0);Upd(rs[c],lzy[c][1],1);
	lzy[c][0]=0;lzy[c][1]=-inf;
}
void Set(int c, int ss, int se, int qs, int qe, ll x, int t)
{
	if(qs>qe || qs>se || ss>qe) return;
	if(qs<=ss && qe>=se) return Upd(c,x,t);
	int mid=ss+se>>1;Push(c);
	Set(ls[c],ss,mid,qs,qe,x,t);
	Set(rs[c],mid+1,se,qs,qe,x,t);
	mx[c]=max(mx[ls[c]],mx[rs[c]]);
}
ll Get(int c, int ss, int se, int qi)
{
	if(ss==se) return mx[c];
	int mid=ss+se>>1;Push(c);
	return qi<=mid?Get(ls[c],ss,mid,qi):Get(rs[c],mid+1,se,qi);
}
void Build(int &c, int ss, int se)
{
	c=++tsz;mx[c]=lzy[c][0]=0;lzy[c][1]=-inf;
	if(ss==se) return;
	int mid=ss+se>>1;
	Build(ls[c],ss,mid);
	Build(rs[c],mid+1,se);
}
ll a[N],s[N],p[N],b[N],t[N],q[N];
vector<pair<int,ll>> Us[N];
int main()
{
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n,m;
	cin>>n>>m;
	for(int i=0;i<n;i++) cin>>a[i+1]>>s[i]>>p[i],a[i+1]+=a[i];
	for(int i=0;i<m;i++) cin>>b[i+1]>>t[i]>>q[i],b[i+1]+=b[i];
	for(int i=0;i<n;i++)
	{
		int j=upper_bound(b,b+m+1,s[i]-a[i+1])-b-1;
		if(j>=0) Us[j].pb({i+1,p[i]});
	}
	ll sum=0;
	for(int i=0;i<m;i++)
	{
		sum+=q[i];
		int j=upper_bound(a,a+n+1,t[i]-b[i+1])-a-1;
		if(j<n) Us[i].pb({j+1,-q[i]});
	}
	Build(root,0,n);
	for(int i=0;i<=m;i++)
	{
		for(auto u:Us[i]) Set(root,0,n,u.first,n,u.second,0);
		if(i==m) break;
		for(auto u:Us[i]) if(u.first) Set(root,0,n,u.first,n,Get(root,0,n,u.first-1),1);
	}
	cout<<sum+Get(root,0,n,n)<<endl;
	return 0;
}

Compilation message

dishes.cpp: In function 'void Set(int, int, int, int, int, long long int, int)':
dishes.cpp:26:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;Push(c);
          ~~^~~
dishes.cpp: In function 'long long int Get(int, int, int, int)':
dishes.cpp:34:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;Push(c);
          ~~^~~
dishes.cpp: In function 'void Build(int&, int, int)':
dishes.cpp:41:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 834 ms 63448 KB Output is correct
2 Correct 823 ms 62656 KB Output is correct
3 Correct 422 ms 56996 KB Output is correct
4 Correct 639 ms 61676 KB Output is correct
5 Correct 23 ms 23928 KB Output is correct
6 Correct 768 ms 61240 KB Output is correct
7 Correct 133 ms 35964 KB Output is correct
8 Correct 259 ms 51344 KB Output is correct
9 Correct 383 ms 56800 KB Output is correct
10 Correct 804 ms 62828 KB Output is correct
11 Correct 308 ms 57056 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 23844 KB Output is correct
2 Correct 28 ms 23900 KB Output is correct
3 Correct 30 ms 23928 KB Output is correct
4 Correct 26 ms 23840 KB Output is correct
5 Correct 25 ms 23928 KB Output is correct
6 Correct 24 ms 23928 KB Output is correct
7 Correct 24 ms 23928 KB Output is correct
8 Correct 25 ms 23944 KB Output is correct
9 Correct 24 ms 23928 KB Output is correct
10 Correct 27 ms 23928 KB Output is correct
11 Correct 24 ms 23928 KB Output is correct
12 Correct 28 ms 23928 KB Output is correct
13 Correct 27 ms 23928 KB Output is correct
14 Correct 24 ms 23884 KB Output is correct
15 Correct 25 ms 23940 KB Output is correct
16 Correct 26 ms 23932 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 23844 KB Output is correct
2 Correct 28 ms 23900 KB Output is correct
3 Correct 30 ms 23928 KB Output is correct
4 Correct 26 ms 23840 KB Output is correct
5 Correct 25 ms 23928 KB Output is correct
6 Correct 24 ms 23928 KB Output is correct
7 Correct 24 ms 23928 KB Output is correct
8 Correct 25 ms 23944 KB Output is correct
9 Correct 24 ms 23928 KB Output is correct
10 Correct 27 ms 23928 KB Output is correct
11 Correct 24 ms 23928 KB Output is correct
12 Correct 28 ms 23928 KB Output is correct
13 Correct 27 ms 23928 KB Output is correct
14 Correct 24 ms 23884 KB Output is correct
15 Correct 25 ms 23940 KB Output is correct
16 Correct 26 ms 23932 KB Output is correct
17 Correct 38 ms 24312 KB Output is correct
18 Correct 36 ms 24312 KB Output is correct
19 Correct 30 ms 24312 KB Output is correct
20 Correct 30 ms 24312 KB Output is correct
21 Correct 35 ms 24284 KB Output is correct
22 Correct 30 ms 24312 KB Output is correct
23 Correct 34 ms 24284 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 23844 KB Output is correct
2 Correct 28 ms 23900 KB Output is correct
3 Correct 30 ms 23928 KB Output is correct
4 Correct 26 ms 23840 KB Output is correct
5 Correct 25 ms 23928 KB Output is correct
6 Correct 24 ms 23928 KB Output is correct
7 Correct 24 ms 23928 KB Output is correct
8 Correct 25 ms 23944 KB Output is correct
9 Correct 24 ms 23928 KB Output is correct
10 Correct 27 ms 23928 KB Output is correct
11 Correct 24 ms 23928 KB Output is correct
12 Correct 28 ms 23928 KB Output is correct
13 Correct 27 ms 23928 KB Output is correct
14 Correct 24 ms 23884 KB Output is correct
15 Correct 25 ms 23940 KB Output is correct
16 Correct 26 ms 23932 KB Output is correct
17 Correct 38 ms 24312 KB Output is correct
18 Correct 36 ms 24312 KB Output is correct
19 Correct 30 ms 24312 KB Output is correct
20 Correct 30 ms 24312 KB Output is correct
21 Correct 35 ms 24284 KB Output is correct
22 Correct 30 ms 24312 KB Output is correct
23 Correct 34 ms 24284 KB Output is correct
24 Correct 534 ms 60996 KB Output is correct
25 Correct 606 ms 62696 KB Output is correct
26 Correct 563 ms 63848 KB Output is correct
27 Correct 599 ms 62696 KB Output is correct
28 Correct 564 ms 60220 KB Output is correct
29 Correct 364 ms 57696 KB Output is correct
30 Correct 1197 ms 64704 KB Output is correct
31 Correct 137 ms 36892 KB Output is correct
32 Correct 388 ms 49780 KB Output is correct
33 Correct 722 ms 62528 KB Output is correct
34 Correct 1004 ms 63848 KB Output is correct
35 Correct 1190 ms 60152 KB Output is correct
36 Correct 1117 ms 60108 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 23844 KB Output is correct
2 Correct 28 ms 23900 KB Output is correct
3 Correct 30 ms 23928 KB Output is correct
4 Correct 26 ms 23840 KB Output is correct
5 Correct 25 ms 23928 KB Output is correct
6 Correct 24 ms 23928 KB Output is correct
7 Correct 24 ms 23928 KB Output is correct
8 Correct 25 ms 23944 KB Output is correct
9 Correct 24 ms 23928 KB Output is correct
10 Correct 27 ms 23928 KB Output is correct
11 Correct 24 ms 23928 KB Output is correct
12 Correct 28 ms 23928 KB Output is correct
13 Correct 27 ms 23928 KB Output is correct
14 Correct 24 ms 23884 KB Output is correct
15 Correct 25 ms 23940 KB Output is correct
16 Correct 26 ms 23932 KB Output is correct
17 Correct 38 ms 24312 KB Output is correct
18 Correct 36 ms 24312 KB Output is correct
19 Correct 30 ms 24312 KB Output is correct
20 Correct 30 ms 24312 KB Output is correct
21 Correct 35 ms 24284 KB Output is correct
22 Correct 30 ms 24312 KB Output is correct
23 Correct 34 ms 24284 KB Output is correct
24 Correct 534 ms 60996 KB Output is correct
25 Correct 606 ms 62696 KB Output is correct
26 Correct 563 ms 63848 KB Output is correct
27 Correct 599 ms 62696 KB Output is correct
28 Correct 564 ms 60220 KB Output is correct
29 Correct 364 ms 57696 KB Output is correct
30 Correct 1197 ms 64704 KB Output is correct
31 Correct 137 ms 36892 KB Output is correct
32 Correct 388 ms 49780 KB Output is correct
33 Correct 722 ms 62528 KB Output is correct
34 Correct 1004 ms 63848 KB Output is correct
35 Correct 1190 ms 60152 KB Output is correct
36 Correct 1117 ms 60108 KB Output is correct
37 Correct 595 ms 62892 KB Output is correct
38 Correct 625 ms 61912 KB Output is correct
39 Correct 856 ms 64632 KB Output is correct
40 Correct 848 ms 64500 KB Output is correct
41 Correct 25 ms 24056 KB Output is correct
42 Correct 1250 ms 64376 KB Output is correct
43 Correct 750 ms 66624 KB Output is correct
44 Correct 1032 ms 68344 KB Output is correct
45 Correct 1234 ms 63228 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 23844 KB Output is correct
2 Correct 28 ms 23900 KB Output is correct
3 Correct 30 ms 23928 KB Output is correct
4 Correct 26 ms 23840 KB Output is correct
5 Correct 25 ms 23928 KB Output is correct
6 Correct 24 ms 23928 KB Output is correct
7 Correct 24 ms 23928 KB Output is correct
8 Correct 25 ms 23944 KB Output is correct
9 Correct 24 ms 23928 KB Output is correct
10 Correct 27 ms 23928 KB Output is correct
11 Correct 24 ms 23928 KB Output is correct
12 Correct 28 ms 23928 KB Output is correct
13 Correct 27 ms 23928 KB Output is correct
14 Correct 24 ms 23884 KB Output is correct
15 Correct 25 ms 23940 KB Output is correct
16 Correct 26 ms 23932 KB Output is correct
17 Correct 38 ms 24312 KB Output is correct
18 Correct 36 ms 24312 KB Output is correct
19 Correct 30 ms 24312 KB Output is correct
20 Correct 30 ms 24312 KB Output is correct
21 Correct 35 ms 24284 KB Output is correct
22 Correct 30 ms 24312 KB Output is correct
23 Correct 34 ms 24284 KB Output is correct
24 Correct 534 ms 60996 KB Output is correct
25 Correct 606 ms 62696 KB Output is correct
26 Correct 563 ms 63848 KB Output is correct
27 Correct 599 ms 62696 KB Output is correct
28 Correct 564 ms 60220 KB Output is correct
29 Correct 364 ms 57696 KB Output is correct
30 Correct 1197 ms 64704 KB Output is correct
31 Correct 137 ms 36892 KB Output is correct
32 Correct 388 ms 49780 KB Output is correct
33 Correct 722 ms 62528 KB Output is correct
34 Correct 1004 ms 63848 KB Output is correct
35 Correct 1190 ms 60152 KB Output is correct
36 Correct 1117 ms 60108 KB Output is correct
37 Correct 595 ms 62892 KB Output is correct
38 Correct 625 ms 61912 KB Output is correct
39 Correct 856 ms 64632 KB Output is correct
40 Correct 848 ms 64500 KB Output is correct
41 Correct 25 ms 24056 KB Output is correct
42 Correct 1250 ms 64376 KB Output is correct
43 Correct 750 ms 66624 KB Output is correct
44 Correct 1032 ms 68344 KB Output is correct
45 Correct 1234 ms 63228 KB Output is correct
46 Correct 3122 ms 209208 KB Output is correct
47 Correct 3323 ms 206988 KB Output is correct
48 Correct 4635 ms 207688 KB Output is correct
49 Correct 4588 ms 207692 KB Output is correct
50 Correct 8633 ms 218148 KB Output is correct
51 Correct 4856 ms 200652 KB Output is correct
52 Correct 6045 ms 206876 KB Output is correct
53 Correct 7517 ms 201420 KB Output is correct

Subtask #7
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 834 ms 63448 KB Output is correct
2 Correct 823 ms 62656 KB Output is correct
3 Correct 422 ms 56996 KB Output is correct
4 Correct 639 ms 61676 KB Output is correct
5 Correct 23 ms 23928 KB Output is correct
6 Correct 768 ms 61240 KB Output is correct
7 Correct 133 ms 35964 KB Output is correct
8 Correct 259 ms 51344 KB Output is correct
9 Correct 383 ms 56800 KB Output is correct
10 Correct 804 ms 62828 KB Output is correct
11 Correct 308 ms 57056 KB Output is correct
12 Correct 36 ms 23844 KB Output is correct
13 Correct 28 ms 23900 KB Output is correct
14 Correct 30 ms 23928 KB Output is correct
15 Correct 26 ms 23840 KB Output is correct
16 Correct 25 ms 23928 KB Output is correct
17 Correct 24 ms 23928 KB Output is correct
18 Correct 24 ms 23928 KB Output is correct
19 Correct 25 ms 23944 KB Output is correct
20 Correct 24 ms 23928 KB Output is correct
21 Correct 27 ms 23928 KB Output is correct
22 Correct 24 ms 23928 KB Output is correct
23 Correct 28 ms 23928 KB Output is correct
24 Correct 27 ms 23928 KB Output is correct
25 Correct 24 ms 23884 KB Output is correct
26 Correct 25 ms 23940 KB Output is correct
27 Correct 26 ms 23932 KB Output is correct
28 Correct 38 ms 24312 KB Output is correct
29 Correct 36 ms 24312 KB Output is correct
30 Correct 30 ms 24312 KB Output is correct
31 Correct 30 ms 24312 KB Output is correct
32 Correct 35 ms 24284 KB Output is correct
33 Correct 30 ms 24312 KB Output is correct
34 Correct 34 ms 24284 KB Output is correct
35 Correct 534 ms 60996 KB Output is correct
36 Correct 606 ms 62696 KB Output is correct
37 Correct 563 ms 63848 KB Output is correct
38 Correct 599 ms 62696 KB Output is correct
39 Correct 564 ms 60220 KB Output is correct
40 Correct 364 ms 57696 KB Output is correct
41 Correct 1197 ms 64704 KB Output is correct
42 Correct 137 ms 36892 KB Output is correct
43 Correct 388 ms 49780 KB Output is correct
44 Correct 722 ms 62528 KB Output is correct
45 Correct 1004 ms 63848 KB Output is correct
46 Correct 1190 ms 60152 KB Output is correct
47 Correct 1117 ms 60108 KB Output is correct
48 Correct 595 ms 62892 KB Output is correct
49 Correct 625 ms 61912 KB Output is correct
50 Correct 856 ms 64632 KB Output is correct
51 Correct 848 ms 64500 KB Output is correct
52 Correct 25 ms 24056 KB Output is correct
53 Correct 1250 ms 64376 KB Output is correct
54 Correct 750 ms 66624 KB Output is correct
55 Correct 1032 ms 68344 KB Output is correct
56 Correct 1234 ms 63228 KB Output is correct
57 Correct 667 ms 69108 KB Output is correct
58 Correct 638 ms 67972 KB Output is correct
59 Correct 865 ms 67360 KB Output is correct
60 Correct 881 ms 67296 KB Output is correct
61 Correct 1292 ms 66680 KB Output is correct
62 Correct 28 ms 23928 KB Output is correct
63 Correct 1279 ms 69752 KB Output is correct
64 Correct 755 ms 67164 KB Output is correct
65 Correct 1022 ms 67540 KB Output is correct
66 Correct 1133 ms 63356 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 834 ms 63448 KB Output is correct
2 Correct 823 ms 62656 KB Output is correct
3 Correct 422 ms 56996 KB Output is correct
4 Correct 639 ms 61676 KB Output is correct
5 Correct 23 ms 23928 KB Output is correct
6 Correct 768 ms 61240 KB Output is correct
7 Correct 133 ms 35964 KB Output is correct
8 Correct 259 ms 51344 KB Output is correct
9 Correct 383 ms 56800 KB Output is correct
10 Correct 804 ms 62828 KB Output is correct
11 Correct 308 ms 57056 KB Output is correct
12 Correct 36 ms 23844 KB Output is correct
13 Correct 28 ms 23900 KB Output is correct
14 Correct 30 ms 23928 KB Output is correct
15 Correct 26 ms 23840 KB Output is correct
16 Correct 25 ms 23928 KB Output is correct
17 Correct 24 ms 23928 KB Output is correct
18 Correct 24 ms 23928 KB Output is correct
19 Correct 25 ms 23944 KB Output is correct
20 Correct 24 ms 23928 KB Output is correct
21 Correct 27 ms 23928 KB Output is correct
22 Correct 24 ms 23928 KB Output is correct
23 Correct 28 ms 23928 KB Output is correct
24 Correct 27 ms 23928 KB Output is correct
25 Correct 24 ms 23884 KB Output is correct
26 Correct 25 ms 23940 KB Output is correct
27 Correct 26 ms 23932 KB Output is correct
28 Correct 38 ms 24312 KB Output is correct
29 Correct 36 ms 24312 KB Output is correct
30 Correct 30 ms 24312 KB Output is correct
31 Correct 30 ms 24312 KB Output is correct
32 Correct 35 ms 24284 KB Output is correct
33 Correct 30 ms 24312 KB Output is correct
34 Correct 34 ms 24284 KB Output is correct
35 Correct 534 ms 60996 KB Output is correct
36 Correct 606 ms 62696 KB Output is correct
37 Correct 563 ms 63848 KB Output is correct
38 Correct 599 ms 62696 KB Output is correct
39 Correct 564 ms 60220 KB Output is correct
40 Correct 364 ms 57696 KB Output is correct
41 Correct 1197 ms 64704 KB Output is correct
42 Correct 137 ms 36892 KB Output is correct
43 Correct 388 ms 49780 KB Output is correct
44 Correct 722 ms 62528 KB Output is correct
45 Correct 1004 ms 63848 KB Output is correct
46 Correct 1190 ms 60152 KB Output is correct
47 Correct 1117 ms 60108 KB Output is correct
48 Correct 595 ms 62892 KB Output is correct
49 Correct 625 ms 61912 KB Output is correct
50 Correct 856 ms 64632 KB Output is correct
51 Correct 848 ms 64500 KB Output is correct
52 Correct 25 ms 24056 KB Output is correct
53 Correct 1250 ms 64376 KB Output is correct
54 Correct 750 ms 66624 KB Output is correct
55 Correct 1032 ms 68344 KB Output is correct
56 Correct 1234 ms 63228 KB Output is correct
57 Correct 3122 ms 209208 KB Output is correct
58 Correct 3323 ms 206988 KB Output is correct
59 Correct 4635 ms 207688 KB Output is correct
60 Correct 4588 ms 207692 KB Output is correct
61 Correct 8633 ms 218148 KB Output is correct
62 Correct 4856 ms 200652 KB Output is correct
63 Correct 6045 ms 206876 KB Output is correct
64 Correct 7517 ms 201420 KB Output is correct
65 Correct 667 ms 69108 KB Output is correct
66 Correct 638 ms 67972 KB Output is correct
67 Correct 865 ms 67360 KB Output is correct
68 Correct 881 ms 67296 KB Output is correct
69 Correct 1292 ms 66680 KB Output is correct
70 Correct 28 ms 23928 KB Output is correct
71 Correct 1279 ms 69752 KB Output is correct
72 Correct 755 ms 67164 KB Output is correct
73 Correct 1022 ms 67540 KB Output is correct
74 Correct 1133 ms 63356 KB Output is correct
75 Correct 3205 ms 213692 KB Output is correct
76 Correct 3417 ms 208440 KB Output is correct
77 Correct 4653 ms 209228 KB Output is correct
78 Correct 4705 ms 206832 KB Output is correct
79 Correct 8413 ms 204700 KB Output is correct
80 Correct 4687 ms 191508 KB Output is correct
81 Correct 5954 ms 184720 KB Output is correct
82 Correct 8044 ms 198156 KB Output is correct
83 Correct 8048 ms 198720 KB Output is correct