oj.uz

Submission #563892

# Submission time Handle Problem Language Result Execution time Memory
563892 2022-05-18T08:57:06 Z errorgorn Two Dishes (JOI19_dishes) C++17
74 / 100
 5209 ms 290284 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ii pair<int,int>
#define fi first
#define se second
#define endl '\n'

#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound

#define rep(x,s,e) for (int x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int INF=1e18;

int n,m;
int arr[2][1000005];
int brr[2][1000005];
int crr[2][1000005];
int drr[2][1000005];

struct node{
	int s,e,m;
	int val=0; //stores the max value
	int lazy=0;
	bool lazyt=false; //false = increment, true = set
	node *l,*r;
	
	node (int _s,int _e){
		s=_s,e=_e,m=s+e>>1;
		
		if (s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
		}
	}
	
	void propo(){
		if (lazyt){
			val=lazy;
			if (s!=e){
				l->lazy=r->lazy=lazy;
				l->lazyt=r->lazyt=true;
			}
		}
		else if (lazy){
			val+=lazy;
			if (s!=e){
				l->lazy+=lazy;
				r->lazy+=lazy;
			}
		}
		
		lazy=0;
		lazyt=false;
	}
	
	void update1(int i,int j,int k){
		propo();
		if (s==i && e==j) lazy+=k;
		else{
			if (j<=m) l->update1(i,j,k);
			else if (m<i) r->update1(i,j,k);
			else l->update1(i,m,k),r->update1(m+1,j,k);
			
			l->propo(),r->propo();
			val=max(l->val,r->val);
		}
	}
	
	void update2(int i,int j,int k){
		propo();
		if (s==i && e==j){
			lazy=k;
			lazyt=true;
		}
		else{
			if (j<=m) l->update2(i,j,k);
			else if (m<i) r->update2(i,j,k);
			else l->update2(i,m,k),r->update2(m+1,j,k);
			
			l->propo(),r->propo();
			val=max(l->val,r->val);
		}
	}
	
	int getr(int i,int k){
		propo();
		
		if (val<k) return -1;
		if (s==e) return s;
		if (m<i) return r->getr(i,k);
		else{
			int temp=l->getr(i,k);
			if (temp!=-1) return temp;
			else return r->getr(i,k);
		}
	}
	
	int query(int i){
		propo();
		
		if (s==e) return val;
		else if (i<=m) return l->query(i);
		else return r->query(i);
	}
} *root=new node(0,1000005);

void expand(int i){
	int val=root->query(i);
	int temp=root->getr(i+1,val);
	if (temp==-1) root->update2(i+1,1000005,val);
	else if (temp!=i+1) root->update2(i+1,temp-1,val);
}

signed main(){
	cin.tie(0);
	cout.tie(0);
	cin.sync_with_stdio(false);
	
	cin>>n>>m;
	
	rep(x,1,n+1) cin>>arr[0][x]>>brr[0][x]>>crr[0][x];
	rep(x,1,m+1) cin>>arr[1][x]>>brr[1][x]>>crr[1][x];
	
	rep(x,1,n+1) arr[0][x]+=arr[0][x-1];
	rep(x,1,m+1) arr[1][x]+=arr[1][x-1];
	
	//rep(x,0,n+1) cout<<arr[0][x]<<" "; cout<<endl;
	rep(x,1,n+1) drr[0][x]=ub(arr[1],arr[1]+m+1,brr[0][x]-arr[0][x])-arr[1];
	rep(x,1,m+1) drr[1][x]=ub(arr[0],arr[0]+n+1,brr[1][x]-arr[1][x])-arr[0];
	
	//rep(x,1,n+1) cout<<drr[0][x]<<" "; cout<<endl;
	//rep(x,1,m+1) cout<<drr[1][x]<<" "; cout<<endl;
	
	vector<int> idx;
	rep(x,1,m+1) if (drr[1][x]) idx.pub(x);
	sort(all(idx),[](int i,int j){
		return drr[1][i]>drr[1][j];
	});
	
	rep(x,1,n+2){
		while (!idx.empty() && drr[1][idx.back()]==x){
			int u=idx.back(); idx.pob();
			root->update1(u,1000005,crr[1][u]);
		}
		
		if (x!=n+1 && drr[0][x]){
			root->update1(0,drr[0][x]-1,crr[0][x]);
			expand(drr[0][x]-1);
		}
	}
	
	cout<<root->val<<endl;
}

Compilation message

dishes.cpp: In constructor 'node::node(long long int, long long int)':
dishes.cpp:39:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |   s=_s,e=_e,m=s+e>>1;
      |               ~^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 404 ms 171708 KB Output is correct
2 Correct 479 ms 171332 KB Output is correct
3 Correct 453 ms 171584 KB Output is correct
4 Correct 355 ms 170564 KB Output is correct
5 Correct 97 ms 156848 KB Output is correct
6 Correct 461 ms 171068 KB Output is correct
7 Correct 231 ms 165312 KB Output is correct
8 Correct 317 ms 163188 KB Output is correct
9 Correct 466 ms 171552 KB Output is correct
10 Correct 433 ms 171560 KB Output is correct
11 Correct 405 ms 171536 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 156876 KB Output is correct
2 Correct 110 ms 156852 KB Output is correct
3 Correct 103 ms 157048 KB Output is correct
4 Correct 98 ms 156868 KB Output is correct
5 Correct 97 ms 157020 KB Output is correct
6 Correct 98 ms 156844 KB Output is correct
7 Correct 107 ms 156948 KB Output is correct
8 Correct 98 ms 156876 KB Output is correct
9 Correct 100 ms 156812 KB Output is correct
10 Correct 99 ms 156876 KB Output is correct
11 Correct 112 ms 156856 KB Output is correct
12 Correct 98 ms 156848 KB Output is correct
13 Correct 98 ms 156880 KB Output is correct
14 Correct 111 ms 156932 KB Output is correct
15 Correct 96 ms 156808 KB Output is correct
16 Correct 98 ms 156968 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 156876 KB Output is correct
2 Correct 110 ms 156852 KB Output is correct
3 Correct 103 ms 157048 KB Output is correct
4 Correct 98 ms 156868 KB Output is correct
5 Correct 97 ms 157020 KB Output is correct
6 Correct 98 ms 156844 KB Output is correct
7 Correct 107 ms 156948 KB Output is correct
8 Correct 98 ms 156876 KB Output is correct
9 Correct 100 ms 156812 KB Output is correct
10 Correct 99 ms 156876 KB Output is correct
11 Correct 112 ms 156856 KB Output is correct
12 Correct 98 ms 156848 KB Output is correct
13 Correct 98 ms 156880 KB Output is correct
14 Correct 111 ms 156932 KB Output is correct
15 Correct 96 ms 156808 KB Output is correct
16 Correct 98 ms 156968 KB Output is correct
17 Correct 105 ms 157004 KB Output is correct
18 Correct 103 ms 157112 KB Output is correct
19 Correct 108 ms 157072 KB Output is correct
20 Correct 102 ms 157064 KB Output is correct
21 Correct 115 ms 157048 KB Output is correct
22 Correct 116 ms 156972 KB Output is correct
23 Correct 101 ms 157088 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 156876 KB Output is correct
2 Correct 110 ms 156852 KB Output is correct
3 Correct 103 ms 157048 KB Output is correct
4 Correct 98 ms 156868 KB Output is correct
5 Correct 97 ms 157020 KB Output is correct
6 Correct 98 ms 156844 KB Output is correct
7 Correct 107 ms 156948 KB Output is correct
8 Correct 98 ms 156876 KB Output is correct
9 Correct 100 ms 156812 KB Output is correct
10 Correct 99 ms 156876 KB Output is correct
11 Correct 112 ms 156856 KB Output is correct
12 Correct 98 ms 156848 KB Output is correct
13 Correct 98 ms 156880 KB Output is correct
14 Correct 111 ms 156932 KB Output is correct
15 Correct 96 ms 156808 KB Output is correct
16 Correct 98 ms 156968 KB Output is correct
17 Correct 105 ms 157004 KB Output is correct
18 Correct 103 ms 157112 KB Output is correct
19 Correct 108 ms 157072 KB Output is correct
20 Correct 102 ms 157064 KB Output is correct
21 Correct 115 ms 157048 KB Output is correct
22 Correct 116 ms 156972 KB Output is correct
23 Correct 101 ms 157088 KB Output is correct
24 Correct 403 ms 170544 KB Output is correct
25 Correct 343 ms 171584 KB Output is correct
26 Correct 414 ms 170624 KB Output is correct
27 Correct 388 ms 171564 KB Output is correct
28 Correct 544 ms 171556 KB Output is correct
29 Correct 437 ms 171620 KB Output is correct
30 Correct 886 ms 171628 KB Output is correct
31 Correct 243 ms 165380 KB Output is correct
32 Correct 299 ms 163312 KB Output is correct
33 Correct 553 ms 170524 KB Output is correct
34 Correct 729 ms 171392 KB Output is correct
35 Correct 825 ms 171576 KB Output is correct
36 Correct 800 ms 171560 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 156876 KB Output is correct
2 Correct 110 ms 156852 KB Output is correct
3 Correct 103 ms 157048 KB Output is correct
4 Correct 98 ms 156868 KB Output is correct
5 Correct 97 ms 157020 KB Output is correct
6 Correct 98 ms 156844 KB Output is correct
7 Correct 107 ms 156948 KB Output is correct
8 Correct 98 ms 156876 KB Output is correct
9 Correct 100 ms 156812 KB Output is correct
10 Correct 99 ms 156876 KB Output is correct
11 Correct 112 ms 156856 KB Output is correct
12 Correct 98 ms 156848 KB Output is correct
13 Correct 98 ms 156880 KB Output is correct
14 Correct 111 ms 156932 KB Output is correct
15 Correct 96 ms 156808 KB Output is correct
16 Correct 98 ms 156968 KB Output is correct
17 Correct 105 ms 157004 KB Output is correct
18 Correct 103 ms 157112 KB Output is correct
19 Correct 108 ms 157072 KB Output is correct
20 Correct 102 ms 157064 KB Output is correct
21 Correct 115 ms 157048 KB Output is correct
22 Correct 116 ms 156972 KB Output is correct
23 Correct 101 ms 157088 KB Output is correct
24 Correct 403 ms 170544 KB Output is correct
25 Correct 343 ms 171584 KB Output is correct
26 Correct 414 ms 170624 KB Output is correct
27 Correct 388 ms 171564 KB Output is correct
28 Correct 544 ms 171556 KB Output is correct
29 Correct 437 ms 171620 KB Output is correct
30 Correct 886 ms 171628 KB Output is correct
31 Correct 243 ms 165380 KB Output is correct
32 Correct 299 ms 163312 KB Output is correct
33 Correct 553 ms 170524 KB Output is correct
34 Correct 729 ms 171392 KB Output is correct
35 Correct 825 ms 171576 KB Output is correct
36 Correct 800 ms 171560 KB Output is correct
37 Correct 452 ms 170644 KB Output is correct
38 Correct 421 ms 171636 KB Output is correct
39 Correct 404 ms 171600 KB Output is correct
40 Correct 542 ms 171536 KB Output is correct
41 Correct 98 ms 156836 KB Output is correct
42 Correct 903 ms 171624 KB Output is correct
43 Correct 606 ms 170364 KB Output is correct
44 Correct 774 ms 171276 KB Output is correct
45 Correct 851 ms 171688 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 156876 KB Output is correct
2 Correct 110 ms 156852 KB Output is correct
3 Correct 103 ms 157048 KB Output is correct
4 Correct 98 ms 156868 KB Output is correct
5 Correct 97 ms 157020 KB Output is correct
6 Correct 98 ms 156844 KB Output is correct
7 Correct 107 ms 156948 KB Output is correct
8 Correct 98 ms 156876 KB Output is correct
9 Correct 100 ms 156812 KB Output is correct
10 Correct 99 ms 156876 KB Output is correct
11 Correct 112 ms 156856 KB Output is correct
12 Correct 98 ms 156848 KB Output is correct
13 Correct 98 ms 156880 KB Output is correct
14 Correct 111 ms 156932 KB Output is correct
15 Correct 96 ms 156808 KB Output is correct
16 Correct 98 ms 156968 KB Output is correct
17 Correct 105 ms 157004 KB Output is correct
18 Correct 103 ms 157112 KB Output is correct
19 Correct 108 ms 157072 KB Output is correct
20 Correct 102 ms 157064 KB Output is correct
21 Correct 115 ms 157048 KB Output is correct
22 Correct 116 ms 156972 KB Output is correct
23 Correct 101 ms 157088 KB Output is correct
24 Correct 403 ms 170544 KB Output is correct
25 Correct 343 ms 171584 KB Output is correct
26 Correct 414 ms 170624 KB Output is correct
27 Correct 388 ms 171564 KB Output is correct
28 Correct 544 ms 171556 KB Output is correct
29 Correct 437 ms 171620 KB Output is correct
30 Correct 886 ms 171628 KB Output is correct
31 Correct 243 ms 165380 KB Output is correct
32 Correct 299 ms 163312 KB Output is correct
33 Correct 553 ms 170524 KB Output is correct
34 Correct 729 ms 171392 KB Output is correct
35 Correct 825 ms 171576 KB Output is correct
36 Correct 800 ms 171560 KB Output is correct
37 Correct 452 ms 170644 KB Output is correct
38 Correct 421 ms 171636 KB Output is correct
39 Correct 404 ms 171600 KB Output is correct
40 Correct 542 ms 171536 KB Output is correct
41 Correct 98 ms 156836 KB Output is correct
42 Correct 903 ms 171624 KB Output is correct
43 Correct 606 ms 170364 KB Output is correct
44 Correct 774 ms 171276 KB Output is correct
45 Correct 851 ms 171688 KB Output is correct
46 Correct 1848 ms 223844 KB Output is correct
47 Correct 1688 ms 227832 KB Output is correct
48 Correct 1619 ms 227928 KB Output is correct
49 Correct 2608 ms 227856 KB Output is correct
50 Correct 5209 ms 227828 KB Output is correct
51 Correct 3034 ms 288860 KB Output is correct
52 Correct 3819 ms 290284 KB Output is correct
53 Correct 5034 ms 266636 KB Output is correct

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 404 ms 171708 KB Output is correct
2 Correct 479 ms 171332 KB Output is correct
3 Correct 453 ms 171584 KB Output is correct
4 Correct 355 ms 170564 KB Output is correct
5 Correct 97 ms 156848 KB Output is correct
6 Correct 461 ms 171068 KB Output is correct
7 Correct 231 ms 165312 KB Output is correct
8 Correct 317 ms 163188 KB Output is correct
9 Correct 466 ms 171552 KB Output is correct
10 Correct 433 ms 171560 KB Output is correct
11 Correct 405 ms 171536 KB Output is correct
12 Correct 100 ms 156876 KB Output is correct
13 Correct 110 ms 156852 KB Output is correct
14 Correct 103 ms 157048 KB Output is correct
15 Correct 98 ms 156868 KB Output is correct
16 Correct 97 ms 157020 KB Output is correct
17 Correct 98 ms 156844 KB Output is correct
18 Correct 107 ms 156948 KB Output is correct
19 Correct 98 ms 156876 KB Output is correct
20 Correct 100 ms 156812 KB Output is correct
21 Correct 99 ms 156876 KB Output is correct
22 Correct 112 ms 156856 KB Output is correct
23 Correct 98 ms 156848 KB Output is correct
24 Correct 98 ms 156880 KB Output is correct
25 Correct 111 ms 156932 KB Output is correct
26 Correct 96 ms 156808 KB Output is correct
27 Correct 98 ms 156968 KB Output is correct
28 Correct 105 ms 157004 KB Output is correct
29 Correct 103 ms 157112 KB Output is correct
30 Correct 108 ms 157072 KB Output is correct
31 Correct 102 ms 157064 KB Output is correct
32 Correct 115 ms 157048 KB Output is correct
33 Correct 116 ms 156972 KB Output is correct
34 Correct 101 ms 157088 KB Output is correct
35 Correct 403 ms 170544 KB Output is correct
36 Correct 343 ms 171584 KB Output is correct
37 Correct 414 ms 170624 KB Output is correct
38 Correct 388 ms 171564 KB Output is correct
39 Correct 544 ms 171556 KB Output is correct
40 Correct 437 ms 171620 KB Output is correct
41 Correct 886 ms 171628 KB Output is correct
42 Correct 243 ms 165380 KB Output is correct
43 Correct 299 ms 163312 KB Output is correct
44 Correct 553 ms 170524 KB Output is correct
45 Correct 729 ms 171392 KB Output is correct
46 Correct 825 ms 171576 KB Output is correct
47 Correct 800 ms 171560 KB Output is correct
48 Correct 452 ms 170644 KB Output is correct
49 Correct 421 ms 171636 KB Output is correct
50 Correct 404 ms 171600 KB Output is correct
51 Correct 542 ms 171536 KB Output is correct
52 Correct 98 ms 156836 KB Output is correct
53 Correct 903 ms 171624 KB Output is correct
54 Correct 606 ms 170364 KB Output is correct
55 Correct 774 ms 171276 KB Output is correct
56 Correct 851 ms 171688 KB Output is correct
57 Incorrect 405 ms 170596 KB Output isn't correct
58 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 404 ms 171708 KB Output is correct
2 Correct 479 ms 171332 KB Output is correct
3 Correct 453 ms 171584 KB Output is correct
4 Correct 355 ms 170564 KB Output is correct
5 Correct 97 ms 156848 KB Output is correct
6 Correct 461 ms 171068 KB Output is correct
7 Correct 231 ms 165312 KB Output is correct
8 Correct 317 ms 163188 KB Output is correct
9 Correct 466 ms 171552 KB Output is correct
10 Correct 433 ms 171560 KB Output is correct
11 Correct 405 ms 171536 KB Output is correct
12 Correct 100 ms 156876 KB Output is correct
13 Correct 110 ms 156852 KB Output is correct
14 Correct 103 ms 157048 KB Output is correct
15 Correct 98 ms 156868 KB Output is correct
16 Correct 97 ms 157020 KB Output is correct
17 Correct 98 ms 156844 KB Output is correct
18 Correct 107 ms 156948 KB Output is correct
19 Correct 98 ms 156876 KB Output is correct
20 Correct 100 ms 156812 KB Output is correct
21 Correct 99 ms 156876 KB Output is correct
22 Correct 112 ms 156856 KB Output is correct
23 Correct 98 ms 156848 KB Output is correct
24 Correct 98 ms 156880 KB Output is correct
25 Correct 111 ms 156932 KB Output is correct
26 Correct 96 ms 156808 KB Output is correct
27 Correct 98 ms 156968 KB Output is correct
28 Correct 105 ms 157004 KB Output is correct
29 Correct 103 ms 157112 KB Output is correct
30 Correct 108 ms 157072 KB Output is correct
31 Correct 102 ms 157064 KB Output is correct
32 Correct 115 ms 157048 KB Output is correct
33 Correct 116 ms 156972 KB Output is correct
34 Correct 101 ms 157088 KB Output is correct
35 Correct 403 ms 170544 KB Output is correct
36 Correct 343 ms 171584 KB Output is correct
37 Correct 414 ms 170624 KB Output is correct
38 Correct 388 ms 171564 KB Output is correct
39 Correct 544 ms 171556 KB Output is correct
40 Correct 437 ms 171620 KB Output is correct
41 Correct 886 ms 171628 KB Output is correct
42 Correct 243 ms 165380 KB Output is correct
43 Correct 299 ms 163312 KB Output is correct
44 Correct 553 ms 170524 KB Output is correct
45 Correct 729 ms 171392 KB Output is correct
46 Correct 825 ms 171576 KB Output is correct
47 Correct 800 ms 171560 KB Output is correct
48 Correct 452 ms 170644 KB Output is correct
49 Correct 421 ms 171636 KB Output is correct
50 Correct 404 ms 171600 KB Output is correct
51 Correct 542 ms 171536 KB Output is correct
52 Correct 98 ms 156836 KB Output is correct
53 Correct 903 ms 171624 KB Output is correct
54 Correct 606 ms 170364 KB Output is correct
55 Correct 774 ms 171276 KB Output is correct
56 Correct 851 ms 171688 KB Output is correct
57 Correct 1848 ms 223844 KB Output is correct
58 Correct 1688 ms 227832 KB Output is correct
59 Correct 1619 ms 227928 KB Output is correct
60 Correct 2608 ms 227856 KB Output is correct
61 Correct 5209 ms 227828 KB Output is correct
62 Correct 3034 ms 288860 KB Output is correct
63 Correct 3819 ms 290284 KB Output is correct
64 Correct 5034 ms 266636 KB Output is correct
65 Incorrect 405 ms 170596 KB Output isn't correct
66 Halted 0 ms 0 KB -