oj.uz

Submission #105117

# Submission time Handle Problem Language Result Execution time Memory
105117 2019-04-10T15:15:10 Z reality Two Dishes (JOI19_dishes) C++17
82 / 100
 10000 ms 211784 KB 
#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define vii vector < pii >
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
template < class P , class Q > ostream& operator<<(ostream& stream, pair < P , Q > v){ stream << "(" << v.fi << ',' << v.se << ")"; return stream;}
template < class T > ostream& operator<<(ostream& stream, const vector<T> v){ stream << "[ "; for (int i=0; i<(int)v.size(); i++) stream << v[i] << " "; stream << "]"; return stream;}
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}
const int N = 1e6 + 5;
ll A[N],C[N],D[N];
ll B[N],E[N],F[N];
map < pii , ll > M;
ll T[N * 4];
ll Lz[N * 4];
void llz(int l,int r,int node) {
	T[node] += Lz[node];
	if (l != r) {
		Lz[node * 2] += Lz[node];
		Lz[node * 2 + 1] += Lz[node];
	}
	Lz[node] = 0;
}
void update(int l,int r,int pos,ll val,int node) {
	llz(l,r,node);
	if (l == r)
		T[node] = val;
	else {
		int m = (l + r) / 2;
		if (pos <= m)
			update(l,m,pos,val,node * 2),llz(m+1,r,node * 2 + 1);
		else
			update(m+1,r,pos,val,node * 2 + 1),llz(l,m,node * 2);
		T[node] = max(T[node * 2],T[node * 2 + 1]);
	}
}
void Add(int l,int r,int l1,int r1,ll Val,int node) {
	llz(l,r,node);
	if (l1 <= l && r <= r1) {
		Lz[node] += Val;
		llz(l,r,node);
	} else {
		int m = (l + r) / 2;
		if (l1 <= m)
			Add(l,m,l1,r1,Val,node * 2);
		else
			llz(l,m,node * 2);
		if (m+1<=r1)
			Add(m+1,r,l1,r1,Val,node * 2 + 1);
		else
			llz(m+1,r,node * 2 + 1);
		T[node] = max(T[node * 2],T[node * 2 + 1]);
	}
}
ll query(int l,int r,int l1,int r1,int node) {
	llz(l,r,node);
	if (l1 <= l && r <= r1)
		return T[node];
	int m = (l + r) / 2;
	ll ans = -1e18;
	if (l1 <= m)
		smax(ans,query(l,m,l1,r1,node * 2));
	if (m+1<=r1)
		smax(ans,query(m+1,r,l1,r1,node * 2 + 1));
	return ans;
}
int main(void) {
    int n,m;
    cin>>n>>m;
    for (int i = 1;i <= n;++i)
    	cin>>A[i]>>C[i]>>D[i],A[i] += A[i - 1];
    for (int i = 1;i <= m;++i)
    	cin>>B[i]>>E[i]>>F[i],B[i] += B[i - 1];
    ll bst = 0;
    for (int i = 1;i <= n;++i) {
    	if (A[i] > C[i]) {
    		continue;
    	}
    	if (A[i] + B[m] <= C[i]) {
    		bst += D[i];
    		continue;
    	}
    	int Index = lower_bound(B + 1,B + 1 + m,C[i] - A[i] + 1) - B;
    	--Index;
    	M[mp(i - 1,- 1 - Index)] += D[i];
    }
    for (int i = 1;i <= m;++i) {
    	if (B[i] > E[i]) {
    		continue;
    	}
    	if (A[n] + B[i] <= E[i]) {
    		bst += F[i];
    		continue;
    	}
    	int Index = lower_bound(A + 1,A + 1 + n,E[i] - B[i] + 1) - A;
    	--Index;
    	M[mp(Index,-i)] -= F[i];
    	bst += F[i];
    }
    for (auto It : M) {
    	const int Pos = -It.fi.se;
	    update(0,m + 1,Pos,query(0,m + 1,0,Pos,1),1);
	    Add(0,m + 1,0,Pos - 1,It.se,1);
    }
    cout << query(0,m + 1,0,m + 1,1) + bst << '\n';
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1072 ms 33400 KB Output is correct
2 Correct 955 ms 32264 KB Output is correct
3 Correct 721 ms 10872 KB Output is correct
4 Correct 982 ms 23544 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 869 ms 39160 KB Output is correct
7 Correct 323 ms 12024 KB Output is correct
8 Correct 310 ms 12268 KB Output is correct
9 Correct 827 ms 22552 KB Output is correct
10 Correct 724 ms 37920 KB Output is correct
11 Correct 495 ms 17628 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 3 ms 384 KB Output is correct
13 Correct 3 ms 512 KB Output is correct
14 Correct 3 ms 384 KB Output is correct
15 Correct 0 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 3 ms 384 KB Output is correct
13 Correct 3 ms 512 KB Output is correct
14 Correct 3 ms 384 KB Output is correct
15 Correct 0 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 8 ms 640 KB Output is correct
18 Correct 9 ms 768 KB Output is correct
19 Correct 11 ms 896 KB Output is correct
20 Correct 13 ms 816 KB Output is correct
21 Correct 11 ms 768 KB Output is correct
22 Correct 12 ms 768 KB Output is correct
23 Correct 11 ms 768 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 3 ms 384 KB Output is correct
13 Correct 3 ms 512 KB Output is correct
14 Correct 3 ms 384 KB Output is correct
15 Correct 0 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 8 ms 640 KB Output is correct
18 Correct 9 ms 768 KB Output is correct
19 Correct 11 ms 896 KB Output is correct
20 Correct 13 ms 816 KB Output is correct
21 Correct 11 ms 768 KB Output is correct
22 Correct 12 ms 768 KB Output is correct
23 Correct 11 ms 768 KB Output is correct
24 Correct 799 ms 29748 KB Output is correct
25 Correct 869 ms 38576 KB Output is correct
26 Correct 797 ms 38776 KB Output is correct
27 Correct 833 ms 38716 KB Output is correct
28 Correct 900 ms 32524 KB Output is correct
29 Correct 590 ms 18808 KB Output is correct
30 Correct 1658 ms 50560 KB Output is correct
31 Correct 434 ms 24828 KB Output is correct
32 Correct 329 ms 16696 KB Output is correct
33 Correct 1131 ms 37624 KB Output is correct
34 Correct 1673 ms 45372 KB Output is correct
35 Correct 1431 ms 46884 KB Output is correct
36 Correct 1506 ms 45924 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 3 ms 384 KB Output is correct
13 Correct 3 ms 512 KB Output is correct
14 Correct 3 ms 384 KB Output is correct
15 Correct 0 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 8 ms 640 KB Output is correct
18 Correct 9 ms 768 KB Output is correct
19 Correct 11 ms 896 KB Output is correct
20 Correct 13 ms 816 KB Output is correct
21 Correct 11 ms 768 KB Output is correct
22 Correct 12 ms 768 KB Output is correct
23 Correct 11 ms 768 KB Output is correct
24 Correct 799 ms 29748 KB Output is correct
25 Correct 869 ms 38576 KB Output is correct
26 Correct 797 ms 38776 KB Output is correct
27 Correct 833 ms 38716 KB Output is correct
28 Correct 900 ms 32524 KB Output is correct
29 Correct 590 ms 18808 KB Output is correct
30 Correct 1658 ms 50560 KB Output is correct
31 Correct 434 ms 24828 KB Output is correct
32 Correct 329 ms 16696 KB Output is correct
33 Correct 1131 ms 37624 KB Output is correct
34 Correct 1673 ms 45372 KB Output is correct
35 Correct 1431 ms 46884 KB Output is correct
36 Correct 1506 ms 45924 KB Output is correct
37 Correct 1051 ms 42104 KB Output is correct
38 Correct 1018 ms 42716 KB Output is correct
39 Correct 917 ms 39220 KB Output is correct
40 Correct 920 ms 39224 KB Output is correct
41 Correct 3 ms 384 KB Output is correct
42 Correct 1821 ms 54008 KB Output is correct
43 Correct 1366 ms 41976 KB Output is correct
44 Correct 1420 ms 49324 KB Output is correct
45 Correct 1465 ms 49908 KB Output is correct

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 3 ms 384 KB Output is correct
13 Correct 3 ms 512 KB Output is correct
14 Correct 3 ms 384 KB Output is correct
15 Correct 0 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 8 ms 640 KB Output is correct
18 Correct 9 ms 768 KB Output is correct
19 Correct 11 ms 896 KB Output is correct
20 Correct 13 ms 816 KB Output is correct
21 Correct 11 ms 768 KB Output is correct
22 Correct 12 ms 768 KB Output is correct
23 Correct 11 ms 768 KB Output is correct
24 Correct 799 ms 29748 KB Output is correct
25 Correct 869 ms 38576 KB Output is correct
26 Correct 797 ms 38776 KB Output is correct
27 Correct 833 ms 38716 KB Output is correct
28 Correct 900 ms 32524 KB Output is correct
29 Correct 590 ms 18808 KB Output is correct
30 Correct 1658 ms 50560 KB Output is correct
31 Correct 434 ms 24828 KB Output is correct
32 Correct 329 ms 16696 KB Output is correct
33 Correct 1131 ms 37624 KB Output is correct
34 Correct 1673 ms 45372 KB Output is correct
35 Correct 1431 ms 46884 KB Output is correct
36 Correct 1506 ms 45924 KB Output is correct
37 Correct 1051 ms 42104 KB Output is correct
38 Correct 1018 ms 42716 KB Output is correct
39 Correct 917 ms 39220 KB Output is correct
40 Correct 920 ms 39224 KB Output is correct
41 Correct 3 ms 384 KB Output is correct
42 Correct 1821 ms 54008 KB Output is correct
43 Correct 1366 ms 41976 KB Output is correct
44 Correct 1420 ms 49324 KB Output is correct
45 Correct 1465 ms 49908 KB Output is correct
46 Correct 4641 ms 151772 KB Output is correct
47 Correct 5000 ms 151576 KB Output is correct
48 Correct 4593 ms 149648 KB Output is correct
49 Correct 4396 ms 149772 KB Output is correct
50 Execution timed out 10026 ms 211784 KB Time limit exceeded
51 Halted 0 ms 0 KB -

Subtask #7
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1072 ms 33400 KB Output is correct
2 Correct 955 ms 32264 KB Output is correct
3 Correct 721 ms 10872 KB Output is correct
4 Correct 982 ms 23544 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 869 ms 39160 KB Output is correct
7 Correct 323 ms 12024 KB Output is correct
8 Correct 310 ms 12268 KB Output is correct
9 Correct 827 ms 22552 KB Output is correct
10 Correct 724 ms 37920 KB Output is correct
11 Correct 495 ms 17628 KB Output is correct
12 Correct 3 ms 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 3 ms 384 KB Output is correct
16 Correct 3 ms 384 KB Output is correct
17 Correct 3 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 3 ms 384 KB Output is correct
20 Correct 3 ms 384 KB Output is correct
21 Correct 2 ms 384 KB Output is correct
22 Correct 3 ms 384 KB Output is correct
23 Correct 3 ms 384 KB Output is correct
24 Correct 3 ms 512 KB Output is correct
25 Correct 3 ms 384 KB Output is correct
26 Correct 0 ms 384 KB Output is correct
27 Correct 2 ms 384 KB Output is correct
28 Correct 8 ms 640 KB Output is correct
29 Correct 9 ms 768 KB Output is correct
30 Correct 11 ms 896 KB Output is correct
31 Correct 13 ms 816 KB Output is correct
32 Correct 11 ms 768 KB Output is correct
33 Correct 12 ms 768 KB Output is correct
34 Correct 11 ms 768 KB Output is correct
35 Correct 799 ms 29748 KB Output is correct
36 Correct 869 ms 38576 KB Output is correct
37 Correct 797 ms 38776 KB Output is correct
38 Correct 833 ms 38716 KB Output is correct
39 Correct 900 ms 32524 KB Output is correct
40 Correct 590 ms 18808 KB Output is correct
41 Correct 1658 ms 50560 KB Output is correct
42 Correct 434 ms 24828 KB Output is correct
43 Correct 329 ms 16696 KB Output is correct
44 Correct 1131 ms 37624 KB Output is correct
45 Correct 1673 ms 45372 KB Output is correct
46 Correct 1431 ms 46884 KB Output is correct
47 Correct 1506 ms 45924 KB Output is correct
48 Correct 1051 ms 42104 KB Output is correct
49 Correct 1018 ms 42716 KB Output is correct
50 Correct 917 ms 39220 KB Output is correct
51 Correct 920 ms 39224 KB Output is correct
52 Correct 3 ms 384 KB Output is correct
53 Correct 1821 ms 54008 KB Output is correct
54 Correct 1366 ms 41976 KB Output is correct
55 Correct 1420 ms 49324 KB Output is correct
56 Correct 1465 ms 49908 KB Output is correct
57 Correct 903 ms 43444 KB Output is correct
58 Correct 948 ms 44736 KB Output is correct
59 Correct 893 ms 42248 KB Output is correct
60 Correct 916 ms 41640 KB Output is correct
61 Correct 1699 ms 52356 KB Output is correct
62 Correct 2 ms 384 KB Output is correct
63 Correct 2005 ms 55580 KB Output is correct
64 Correct 1213 ms 42920 KB Output is correct
65 Correct 1418 ms 50112 KB Output is correct
66 Correct 1403 ms 49240 KB Output is correct

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1072 ms 33400 KB Output is correct
2 Correct 955 ms 32264 KB Output is correct
3 Correct 721 ms 10872 KB Output is correct
4 Correct 982 ms 23544 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 869 ms 39160 KB Output is correct
7 Correct 323 ms 12024 KB Output is correct
8 Correct 310 ms 12268 KB Output is correct
9 Correct 827 ms 22552 KB Output is correct
10 Correct 724 ms 37920 KB Output is correct
11 Correct 495 ms 17628 KB Output is correct
12 Correct 3 ms 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 3 ms 384 KB Output is correct
16 Correct 3 ms 384 KB Output is correct
17 Correct 3 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 3 ms 384 KB Output is correct
20 Correct 3 ms 384 KB Output is correct
21 Correct 2 ms 384 KB Output is correct
22 Correct 3 ms 384 KB Output is correct
23 Correct 3 ms 384 KB Output is correct
24 Correct 3 ms 512 KB Output is correct
25 Correct 3 ms 384 KB Output is correct
26 Correct 0 ms 384 KB Output is correct
27 Correct 2 ms 384 KB Output is correct
28 Correct 8 ms 640 KB Output is correct
29 Correct 9 ms 768 KB Output is correct
30 Correct 11 ms 896 KB Output is correct
31 Correct 13 ms 816 KB Output is correct
32 Correct 11 ms 768 KB Output is correct
33 Correct 12 ms 768 KB Output is correct
34 Correct 11 ms 768 KB Output is correct
35 Correct 799 ms 29748 KB Output is correct
36 Correct 869 ms 38576 KB Output is correct
37 Correct 797 ms 38776 KB Output is correct
38 Correct 833 ms 38716 KB Output is correct
39 Correct 900 ms 32524 KB Output is correct
40 Correct 590 ms 18808 KB Output is correct
41 Correct 1658 ms 50560 KB Output is correct
42 Correct 434 ms 24828 KB Output is correct
43 Correct 329 ms 16696 KB Output is correct
44 Correct 1131 ms 37624 KB Output is correct
45 Correct 1673 ms 45372 KB Output is correct
46 Correct 1431 ms 46884 KB Output is correct
47 Correct 1506 ms 45924 KB Output is correct
48 Correct 1051 ms 42104 KB Output is correct
49 Correct 1018 ms 42716 KB Output is correct
50 Correct 917 ms 39220 KB Output is correct
51 Correct 920 ms 39224 KB Output is correct
52 Correct 3 ms 384 KB Output is correct
53 Correct 1821 ms 54008 KB Output is correct
54 Correct 1366 ms 41976 KB Output is correct
55 Correct 1420 ms 49324 KB Output is correct
56 Correct 1465 ms 49908 KB Output is correct
57 Correct 4641 ms 151772 KB Output is correct
58 Correct 5000 ms 151576 KB Output is correct
59 Correct 4593 ms 149648 KB Output is correct
60 Correct 4396 ms 149772 KB Output is correct
61 Execution timed out 10026 ms 211784 KB Time limit exceeded
62 Halted 0 ms 0 KB -