oj.uz

Submission #563894

# Submission time Handle Problem Language Result Execution time Memory
563894 2022-05-18T09:00:55 Z errorgorn Two Dishes (JOI19_dishes) C++17
74 / 100
 6186 ms 229764 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){
		vector<int> pos;
		while (!idx.empty() && drr[1][idx.back()]==x){
			int u=idx.back(); idx.pob();
			root->update1(u,1000005,crr[1][u]); //we cannot expand here
			pos.pub(u-1);
		}
		
		if (x!=n+1 && drr[0][x]){
			root->update1(0,drr[0][x]-1,crr[0][x]);
			pos.pub(drr[0][x]-1);
		}
		
		sort(all(pos));
		for (auto it:pos) expand(it);
	}
	
	cout<<root->query(m)<<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 452 ms 171684 KB Output is correct
2 Correct 532 ms 171348 KB Output is correct
3 Correct 512 ms 174112 KB Output is correct
4 Correct 392 ms 170340 KB Output is correct
5 Correct 97 ms 156872 KB Output is correct
6 Correct 509 ms 171184 KB Output is correct
7 Correct 277 ms 167608 KB Output is correct
8 Correct 307 ms 163168 KB Output is correct
9 Correct 524 ms 174164 KB Output is correct
10 Correct 467 ms 171580 KB Output is correct
11 Correct 462 ms 174100 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 156904 KB Output is correct
2 Correct 104 ms 156828 KB Output is correct
3 Correct 101 ms 156840 KB Output is correct
4 Correct 104 ms 156836 KB Output is correct
5 Correct 102 ms 156864 KB Output is correct
6 Correct 101 ms 156824 KB Output is correct
7 Correct 102 ms 156872 KB Output is correct
8 Correct 100 ms 156824 KB Output is correct
9 Correct 98 ms 156916 KB Output is correct
10 Correct 100 ms 156800 KB Output is correct
11 Correct 105 ms 156856 KB Output is correct
12 Correct 101 ms 156800 KB Output is correct
13 Correct 103 ms 156872 KB Output is correct
14 Correct 104 ms 156816 KB Output is correct
15 Correct 101 ms 156816 KB Output is correct
16 Correct 105 ms 156876 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 156904 KB Output is correct
2 Correct 104 ms 156828 KB Output is correct
3 Correct 101 ms 156840 KB Output is correct
4 Correct 104 ms 156836 KB Output is correct
5 Correct 102 ms 156864 KB Output is correct
6 Correct 101 ms 156824 KB Output is correct
7 Correct 102 ms 156872 KB Output is correct
8 Correct 100 ms 156824 KB Output is correct
9 Correct 98 ms 156916 KB Output is correct
10 Correct 100 ms 156800 KB Output is correct
11 Correct 105 ms 156856 KB Output is correct
12 Correct 101 ms 156800 KB Output is correct
13 Correct 103 ms 156872 KB Output is correct
14 Correct 104 ms 156816 KB Output is correct
15 Correct 101 ms 156816 KB Output is correct
16 Correct 105 ms 156876 KB Output is correct
17 Correct 104 ms 156968 KB Output is correct
18 Correct 103 ms 157028 KB Output is correct
19 Correct 103 ms 156972 KB Output is correct
20 Correct 104 ms 156960 KB Output is correct
21 Correct 106 ms 157092 KB Output is correct
22 Correct 104 ms 157136 KB Output is correct
23 Correct 106 ms 157068 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 156904 KB Output is correct
2 Correct 104 ms 156828 KB Output is correct
3 Correct 101 ms 156840 KB Output is correct
4 Correct 104 ms 156836 KB Output is correct
5 Correct 102 ms 156864 KB Output is correct
6 Correct 101 ms 156824 KB Output is correct
7 Correct 102 ms 156872 KB Output is correct
8 Correct 100 ms 156824 KB Output is correct
9 Correct 98 ms 156916 KB Output is correct
10 Correct 100 ms 156800 KB Output is correct
11 Correct 105 ms 156856 KB Output is correct
12 Correct 101 ms 156800 KB Output is correct
13 Correct 103 ms 156872 KB Output is correct
14 Correct 104 ms 156816 KB Output is correct
15 Correct 101 ms 156816 KB Output is correct
16 Correct 105 ms 156876 KB Output is correct
17 Correct 104 ms 156968 KB Output is correct
18 Correct 103 ms 157028 KB Output is correct
19 Correct 103 ms 156972 KB Output is correct
20 Correct 104 ms 156960 KB Output is correct
21 Correct 106 ms 157092 KB Output is correct
22 Correct 104 ms 157136 KB Output is correct
23 Correct 106 ms 157068 KB Output is correct
24 Correct 439 ms 171724 KB Output is correct
25 Correct 407 ms 174008 KB Output is correct
26 Correct 484 ms 171788 KB Output is correct
27 Correct 453 ms 171608 KB Output is correct
28 Correct 610 ms 172768 KB Output is correct
29 Correct 500 ms 174024 KB Output is correct
30 Correct 962 ms 171604 KB Output is correct
31 Correct 303 ms 166552 KB Output is correct
32 Correct 306 ms 163144 KB Output is correct
33 Correct 586 ms 170444 KB Output is correct
34 Correct 814 ms 171288 KB Output is correct
35 Correct 917 ms 171552 KB Output is correct
36 Correct 988 ms 171628 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 156904 KB Output is correct
2 Correct 104 ms 156828 KB Output is correct
3 Correct 101 ms 156840 KB Output is correct
4 Correct 104 ms 156836 KB Output is correct
5 Correct 102 ms 156864 KB Output is correct
6 Correct 101 ms 156824 KB Output is correct
7 Correct 102 ms 156872 KB Output is correct
8 Correct 100 ms 156824 KB Output is correct
9 Correct 98 ms 156916 KB Output is correct
10 Correct 100 ms 156800 KB Output is correct
11 Correct 105 ms 156856 KB Output is correct
12 Correct 101 ms 156800 KB Output is correct
13 Correct 103 ms 156872 KB Output is correct
14 Correct 104 ms 156816 KB Output is correct
15 Correct 101 ms 156816 KB Output is correct
16 Correct 105 ms 156876 KB Output is correct
17 Correct 104 ms 156968 KB Output is correct
18 Correct 103 ms 157028 KB Output is correct
19 Correct 103 ms 156972 KB Output is correct
20 Correct 104 ms 156960 KB Output is correct
21 Correct 106 ms 157092 KB Output is correct
22 Correct 104 ms 157136 KB Output is correct
23 Correct 106 ms 157068 KB Output is correct
24 Correct 439 ms 171724 KB Output is correct
25 Correct 407 ms 174008 KB Output is correct
26 Correct 484 ms 171788 KB Output is correct
27 Correct 453 ms 171608 KB Output is correct
28 Correct 610 ms 172768 KB Output is correct
29 Correct 500 ms 174024 KB Output is correct
30 Correct 962 ms 171604 KB Output is correct
31 Correct 303 ms 166552 KB Output is correct
32 Correct 306 ms 163144 KB Output is correct
33 Correct 586 ms 170444 KB Output is correct
34 Correct 814 ms 171288 KB Output is correct
35 Correct 917 ms 171552 KB Output is correct
36 Correct 988 ms 171628 KB Output is correct
37 Correct 522 ms 171788 KB Output is correct
38 Correct 516 ms 171552 KB Output is correct
39 Correct 511 ms 171964 KB Output is correct
40 Correct 651 ms 171916 KB Output is correct
41 Correct 107 ms 156816 KB Output is correct
42 Correct 1153 ms 171940 KB Output is correct
43 Correct 705 ms 170784 KB Output is correct
44 Correct 899 ms 171588 KB Output is correct
45 Correct 992 ms 171992 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 156904 KB Output is correct
2 Correct 104 ms 156828 KB Output is correct
3 Correct 101 ms 156840 KB Output is correct
4 Correct 104 ms 156836 KB Output is correct
5 Correct 102 ms 156864 KB Output is correct
6 Correct 101 ms 156824 KB Output is correct
7 Correct 102 ms 156872 KB Output is correct
8 Correct 100 ms 156824 KB Output is correct
9 Correct 98 ms 156916 KB Output is correct
10 Correct 100 ms 156800 KB Output is correct
11 Correct 105 ms 156856 KB Output is correct
12 Correct 101 ms 156800 KB Output is correct
13 Correct 103 ms 156872 KB Output is correct
14 Correct 104 ms 156816 KB Output is correct
15 Correct 101 ms 156816 KB Output is correct
16 Correct 105 ms 156876 KB Output is correct
17 Correct 104 ms 156968 KB Output is correct
18 Correct 103 ms 157028 KB Output is correct
19 Correct 103 ms 156972 KB Output is correct
20 Correct 104 ms 156960 KB Output is correct
21 Correct 106 ms 157092 KB Output is correct
22 Correct 104 ms 157136 KB Output is correct
23 Correct 106 ms 157068 KB Output is correct
24 Correct 439 ms 171724 KB Output is correct
25 Correct 407 ms 174008 KB Output is correct
26 Correct 484 ms 171788 KB Output is correct
27 Correct 453 ms 171608 KB Output is correct
28 Correct 610 ms 172768 KB Output is correct
29 Correct 500 ms 174024 KB Output is correct
30 Correct 962 ms 171604 KB Output is correct
31 Correct 303 ms 166552 KB Output is correct
32 Correct 306 ms 163144 KB Output is correct
33 Correct 586 ms 170444 KB Output is correct
34 Correct 814 ms 171288 KB Output is correct
35 Correct 917 ms 171552 KB Output is correct
36 Correct 988 ms 171628 KB Output is correct
37 Correct 522 ms 171788 KB Output is correct
38 Correct 516 ms 171552 KB Output is correct
39 Correct 511 ms 171964 KB Output is correct
40 Correct 651 ms 171916 KB Output is correct
41 Correct 107 ms 156816 KB Output is correct
42 Correct 1153 ms 171940 KB Output is correct
43 Correct 705 ms 170784 KB Output is correct
44 Correct 899 ms 171588 KB Output is correct
45 Correct 992 ms 171992 KB Output is correct
46 Correct 2222 ms 229764 KB Output is correct
47 Correct 2089 ms 227972 KB Output is correct
48 Correct 1924 ms 228204 KB Output is correct
49 Correct 3000 ms 227992 KB Output is correct
50 Correct 6186 ms 228060 KB Output is correct
51 Correct 3941 ms 222232 KB Output is correct
52 Correct 4918 ms 225968 KB Output is correct
53 Correct 6173 ms 227828 KB Output is correct

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 452 ms 171684 KB Output is correct
2 Correct 532 ms 171348 KB Output is correct
3 Correct 512 ms 174112 KB Output is correct
4 Correct 392 ms 170340 KB Output is correct
5 Correct 97 ms 156872 KB Output is correct
6 Correct 509 ms 171184 KB Output is correct
7 Correct 277 ms 167608 KB Output is correct
8 Correct 307 ms 163168 KB Output is correct
9 Correct 524 ms 174164 KB Output is correct
10 Correct 467 ms 171580 KB Output is correct
11 Correct 462 ms 174100 KB Output is correct
12 Correct 108 ms 156904 KB Output is correct
13 Correct 104 ms 156828 KB Output is correct
14 Correct 101 ms 156840 KB Output is correct
15 Correct 104 ms 156836 KB Output is correct
16 Correct 102 ms 156864 KB Output is correct
17 Correct 101 ms 156824 KB Output is correct
18 Correct 102 ms 156872 KB Output is correct
19 Correct 100 ms 156824 KB Output is correct
20 Correct 98 ms 156916 KB Output is correct
21 Correct 100 ms 156800 KB Output is correct
22 Correct 105 ms 156856 KB Output is correct
23 Correct 101 ms 156800 KB Output is correct
24 Correct 103 ms 156872 KB Output is correct
25 Correct 104 ms 156816 KB Output is correct
26 Correct 101 ms 156816 KB Output is correct
27 Correct 105 ms 156876 KB Output is correct
28 Correct 104 ms 156968 KB Output is correct
29 Correct 103 ms 157028 KB Output is correct
30 Correct 103 ms 156972 KB Output is correct
31 Correct 104 ms 156960 KB Output is correct
32 Correct 106 ms 157092 KB Output is correct
33 Correct 104 ms 157136 KB Output is correct
34 Correct 106 ms 157068 KB Output is correct
35 Correct 439 ms 171724 KB Output is correct
36 Correct 407 ms 174008 KB Output is correct
37 Correct 484 ms 171788 KB Output is correct
38 Correct 453 ms 171608 KB Output is correct
39 Correct 610 ms 172768 KB Output is correct
40 Correct 500 ms 174024 KB Output is correct
41 Correct 962 ms 171604 KB Output is correct
42 Correct 303 ms 166552 KB Output is correct
43 Correct 306 ms 163144 KB Output is correct
44 Correct 586 ms 170444 KB Output is correct
45 Correct 814 ms 171288 KB Output is correct
46 Correct 917 ms 171552 KB Output is correct
47 Correct 988 ms 171628 KB Output is correct
48 Correct 522 ms 171788 KB Output is correct
49 Correct 516 ms 171552 KB Output is correct
50 Correct 511 ms 171964 KB Output is correct
51 Correct 651 ms 171916 KB Output is correct
52 Correct 107 ms 156816 KB Output is correct
53 Correct 1153 ms 171940 KB Output is correct
54 Correct 705 ms 170784 KB Output is correct
55 Correct 899 ms 171588 KB Output is correct
56 Correct 992 ms 171992 KB Output is correct
57 Incorrect 460 ms 172296 KB Output isn't correct
58 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 452 ms 171684 KB Output is correct
2 Correct 532 ms 171348 KB Output is correct
3 Correct 512 ms 174112 KB Output is correct
4 Correct 392 ms 170340 KB Output is correct
5 Correct 97 ms 156872 KB Output is correct
6 Correct 509 ms 171184 KB Output is correct
7 Correct 277 ms 167608 KB Output is correct
8 Correct 307 ms 163168 KB Output is correct
9 Correct 524 ms 174164 KB Output is correct
10 Correct 467 ms 171580 KB Output is correct
11 Correct 462 ms 174100 KB Output is correct
12 Correct 108 ms 156904 KB Output is correct
13 Correct 104 ms 156828 KB Output is correct
14 Correct 101 ms 156840 KB Output is correct
15 Correct 104 ms 156836 KB Output is correct
16 Correct 102 ms 156864 KB Output is correct
17 Correct 101 ms 156824 KB Output is correct
18 Correct 102 ms 156872 KB Output is correct
19 Correct 100 ms 156824 KB Output is correct
20 Correct 98 ms 156916 KB Output is correct
21 Correct 100 ms 156800 KB Output is correct
22 Correct 105 ms 156856 KB Output is correct
23 Correct 101 ms 156800 KB Output is correct
24 Correct 103 ms 156872 KB Output is correct
25 Correct 104 ms 156816 KB Output is correct
26 Correct 101 ms 156816 KB Output is correct
27 Correct 105 ms 156876 KB Output is correct
28 Correct 104 ms 156968 KB Output is correct
29 Correct 103 ms 157028 KB Output is correct
30 Correct 103 ms 156972 KB Output is correct
31 Correct 104 ms 156960 KB Output is correct
32 Correct 106 ms 157092 KB Output is correct
33 Correct 104 ms 157136 KB Output is correct
34 Correct 106 ms 157068 KB Output is correct
35 Correct 439 ms 171724 KB Output is correct
36 Correct 407 ms 174008 KB Output is correct
37 Correct 484 ms 171788 KB Output is correct
38 Correct 453 ms 171608 KB Output is correct
39 Correct 610 ms 172768 KB Output is correct
40 Correct 500 ms 174024 KB Output is correct
41 Correct 962 ms 171604 KB Output is correct
42 Correct 303 ms 166552 KB Output is correct
43 Correct 306 ms 163144 KB Output is correct
44 Correct 586 ms 170444 KB Output is correct
45 Correct 814 ms 171288 KB Output is correct
46 Correct 917 ms 171552 KB Output is correct
47 Correct 988 ms 171628 KB Output is correct
48 Correct 522 ms 171788 KB Output is correct
49 Correct 516 ms 171552 KB Output is correct
50 Correct 511 ms 171964 KB Output is correct
51 Correct 651 ms 171916 KB Output is correct
52 Correct 107 ms 156816 KB Output is correct
53 Correct 1153 ms 171940 KB Output is correct
54 Correct 705 ms 170784 KB Output is correct
55 Correct 899 ms 171588 KB Output is correct
56 Correct 992 ms 171992 KB Output is correct
57 Correct 2222 ms 229764 KB Output is correct
58 Correct 2089 ms 227972 KB Output is correct
59 Correct 1924 ms 228204 KB Output is correct
60 Correct 3000 ms 227992 KB Output is correct
61 Correct 6186 ms 228060 KB Output is correct
62 Correct 3941 ms 222232 KB Output is correct
63 Correct 4918 ms 225968 KB Output is correct
64 Correct 6173 ms 227828 KB Output is correct
65 Incorrect 460 ms 172296 KB Output isn't correct
66 Halted 0 ms 0 KB -