oj.uz

답안 #563884

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
563884 2022-05-18T08:42:10 Z errorgorn Two Dishes (JOI19_dishes) C++17
65 / 100
 10000 ms 297908 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 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);

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]);
			
			int val=root->query(drr[0][x]-1);
			
			int lo=drr[0][x]-1,hi=1000006,mi;
			while (hi-lo>1){
				mi=hi+lo>>1;
				
				if (val<=root->query(mi)) hi=mi;
				else lo=mi;
			}
			if (lo!=drr[0][x]-1) root->update2(drr[0][x],lo,val);
		}
	}
	
	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;
      |               ~^~
dishes.cpp: In function 'int main()':
dishes.cpp:144:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  144 |     mi=hi+lo>>1;
      |        ~~^~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 852 ms 171584 KB Output is correct
2 Correct 964 ms 171528 KB Output is correct
3 Correct 946 ms 171612 KB Output is correct
4 Correct 663 ms 170488 KB Output is correct
5 Correct 104 ms 156876 KB Output is correct
6 Correct 921 ms 171100 KB Output is correct
7 Correct 232 ms 165400 KB Output is correct
8 Correct 778 ms 163208 KB Output is correct
9 Correct 947 ms 171560 KB Output is correct
10 Correct 925 ms 171584 KB Output is correct
11 Correct 906 ms 171584 KB Output is correct

Subtask #2
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 108 ms 156904 KB Output is correct
2 Correct 109 ms 156892 KB Output is correct
3 Correct 117 ms 156804 KB Output is correct
4 Correct 102 ms 156812 KB Output is correct
5 Correct 104 ms 156916 KB Output is correct
6 Correct 109 ms 156916 KB Output is correct
7 Correct 105 ms 156824 KB Output is correct
8 Correct 109 ms 156928 KB Output is correct
9 Correct 107 ms 156840 KB Output is correct
10 Correct 106 ms 156844 KB Output is correct
11 Correct 106 ms 156844 KB Output is correct
12 Correct 104 ms 156840 KB Output is correct
13 Correct 108 ms 156832 KB Output is correct
14 Correct 105 ms 156916 KB Output is correct
15 Correct 105 ms 156808 KB Output is correct
16 Correct 104 ms 156904 KB Output is correct

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 108 ms 156904 KB Output is correct
2 Correct 109 ms 156892 KB Output is correct
3 Correct 117 ms 156804 KB Output is correct
4 Correct 102 ms 156812 KB Output is correct
5 Correct 104 ms 156916 KB Output is correct
6 Correct 109 ms 156916 KB Output is correct
7 Correct 105 ms 156824 KB Output is correct
8 Correct 109 ms 156928 KB Output is correct
9 Correct 107 ms 156840 KB Output is correct
10 Correct 106 ms 156844 KB Output is correct
11 Correct 106 ms 156844 KB Output is correct
12 Correct 104 ms 156840 KB Output is correct
13 Correct 108 ms 156832 KB Output is correct
14 Correct 105 ms 156916 KB Output is correct
15 Correct 105 ms 156808 KB Output is correct
16 Correct 104 ms 156904 KB Output is correct
17 Correct 113 ms 156988 KB Output is correct
18 Correct 121 ms 157072 KB Output is correct
19 Correct 114 ms 157004 KB Output is correct
20 Correct 111 ms 157164 KB Output is correct
21 Correct 112 ms 157056 KB Output is correct
22 Correct 114 ms 157036 KB Output is correct
23 Correct 114 ms 156984 KB Output is correct

Subtask #4
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 108 ms 156904 KB Output is correct
2 Correct 109 ms 156892 KB Output is correct
3 Correct 117 ms 156804 KB Output is correct
4 Correct 102 ms 156812 KB Output is correct
5 Correct 104 ms 156916 KB Output is correct
6 Correct 109 ms 156916 KB Output is correct
7 Correct 105 ms 156824 KB Output is correct
8 Correct 109 ms 156928 KB Output is correct
9 Correct 107 ms 156840 KB Output is correct
10 Correct 106 ms 156844 KB Output is correct
11 Correct 106 ms 156844 KB Output is correct
12 Correct 104 ms 156840 KB Output is correct
13 Correct 108 ms 156832 KB Output is correct
14 Correct 105 ms 156916 KB Output is correct
15 Correct 105 ms 156808 KB Output is correct
16 Correct 104 ms 156904 KB Output is correct
17 Correct 113 ms 156988 KB Output is correct
18 Correct 121 ms 157072 KB Output is correct
19 Correct 114 ms 157004 KB Output is correct
20 Correct 111 ms 157164 KB Output is correct
21 Correct 112 ms 157056 KB Output is correct
22 Correct 114 ms 157036 KB Output is correct
23 Correct 114 ms 156984 KB Output is correct
24 Correct 887 ms 170616 KB Output is correct
25 Correct 620 ms 182196 KB Output is correct
26 Correct 911 ms 181224 KB Output is correct
27 Correct 658 ms 182288 KB Output is correct
28 Correct 1359 ms 182464 KB Output is correct
29 Correct 948 ms 182972 KB Output is correct
30 Correct 2621 ms 182344 KB Output is correct
31 Correct 253 ms 170692 KB Output is correct
32 Correct 780 ms 168436 KB Output is correct
33 Correct 1445 ms 180992 KB Output is correct
34 Correct 1822 ms 181952 KB Output is correct
35 Correct 2629 ms 176064 KB Output is correct
36 Correct 2535 ms 176064 KB Output is correct

Subtask #5
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 108 ms 156904 KB Output is correct
2 Correct 109 ms 156892 KB Output is correct
3 Correct 117 ms 156804 KB Output is correct
4 Correct 102 ms 156812 KB Output is correct
5 Correct 104 ms 156916 KB Output is correct
6 Correct 109 ms 156916 KB Output is correct
7 Correct 105 ms 156824 KB Output is correct
8 Correct 109 ms 156928 KB Output is correct
9 Correct 107 ms 156840 KB Output is correct
10 Correct 106 ms 156844 KB Output is correct
11 Correct 106 ms 156844 KB Output is correct
12 Correct 104 ms 156840 KB Output is correct
13 Correct 108 ms 156832 KB Output is correct
14 Correct 105 ms 156916 KB Output is correct
15 Correct 105 ms 156808 KB Output is correct
16 Correct 104 ms 156904 KB Output is correct
17 Correct 113 ms 156988 KB Output is correct
18 Correct 121 ms 157072 KB Output is correct
19 Correct 114 ms 157004 KB Output is correct
20 Correct 111 ms 157164 KB Output is correct
21 Correct 112 ms 157056 KB Output is correct
22 Correct 114 ms 157036 KB Output is correct
23 Correct 114 ms 156984 KB Output is correct
24 Correct 887 ms 170616 KB Output is correct
25 Correct 620 ms 182196 KB Output is correct
26 Correct 911 ms 181224 KB Output is correct
27 Correct 658 ms 182288 KB Output is correct
28 Correct 1359 ms 182464 KB Output is correct
29 Correct 948 ms 182972 KB Output is correct
30 Correct 2621 ms 182344 KB Output is correct
31 Correct 253 ms 170692 KB Output is correct
32 Correct 780 ms 168436 KB Output is correct
33 Correct 1445 ms 180992 KB Output is correct
34 Correct 1822 ms 181952 KB Output is correct
35 Correct 2629 ms 176064 KB Output is correct
36 Correct 2535 ms 176064 KB Output is correct
37 Correct 947 ms 184244 KB Output is correct
38 Correct 684 ms 185356 KB Output is correct
39 Correct 933 ms 182568 KB Output is correct
40 Correct 1012 ms 182700 KB Output is correct
41 Correct 101 ms 156928 KB Output is correct
42 Correct 2701 ms 185452 KB Output is correct
43 Correct 1434 ms 183876 KB Output is correct
44 Correct 1801 ms 184960 KB Output is correct
45 Correct 2618 ms 179008 KB Output is correct

Subtask #6
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 108 ms 156904 KB Output is correct
2 Correct 109 ms 156892 KB Output is correct
3 Correct 117 ms 156804 KB Output is correct
4 Correct 102 ms 156812 KB Output is correct
5 Correct 104 ms 156916 KB Output is correct
6 Correct 109 ms 156916 KB Output is correct
7 Correct 105 ms 156824 KB Output is correct
8 Correct 109 ms 156928 KB Output is correct
9 Correct 107 ms 156840 KB Output is correct
10 Correct 106 ms 156844 KB Output is correct
11 Correct 106 ms 156844 KB Output is correct
12 Correct 104 ms 156840 KB Output is correct
13 Correct 108 ms 156832 KB Output is correct
14 Correct 105 ms 156916 KB Output is correct
15 Correct 105 ms 156808 KB Output is correct
16 Correct 104 ms 156904 KB Output is correct
17 Correct 113 ms 156988 KB Output is correct
18 Correct 121 ms 157072 KB Output is correct
19 Correct 114 ms 157004 KB Output is correct
20 Correct 111 ms 157164 KB Output is correct
21 Correct 112 ms 157056 KB Output is correct
22 Correct 114 ms 157036 KB Output is correct
23 Correct 114 ms 156984 KB Output is correct
24 Correct 887 ms 170616 KB Output is correct
25 Correct 620 ms 182196 KB Output is correct
26 Correct 911 ms 181224 KB Output is correct
27 Correct 658 ms 182288 KB Output is correct
28 Correct 1359 ms 182464 KB Output is correct
29 Correct 948 ms 182972 KB Output is correct
30 Correct 2621 ms 182344 KB Output is correct
31 Correct 253 ms 170692 KB Output is correct
32 Correct 780 ms 168436 KB Output is correct
33 Correct 1445 ms 180992 KB Output is correct
34 Correct 1822 ms 181952 KB Output is correct
35 Correct 2629 ms 176064 KB Output is correct
36 Correct 2535 ms 176064 KB Output is correct
37 Correct 947 ms 184244 KB Output is correct
38 Correct 684 ms 185356 KB Output is correct
39 Correct 933 ms 182568 KB Output is correct
40 Correct 1012 ms 182700 KB Output is correct
41 Correct 101 ms 156928 KB Output is correct
42 Correct 2701 ms 185452 KB Output is correct
43 Correct 1434 ms 183876 KB Output is correct
44 Correct 1801 ms 184960 KB Output is correct
45 Correct 2618 ms 179008 KB Output is correct
46 Correct 4228 ms 293732 KB Output is correct
47 Correct 1846 ms 297884 KB Output is correct
48 Correct 3941 ms 284116 KB Output is correct
49 Correct 4446 ms 284148 KB Output is correct
50 Execution timed out 10052 ms 297908 KB Time limit exceeded
51 Halted 0 ms 0 KB -

Subtask #7
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 852 ms 171584 KB Output is correct
2 Correct 964 ms 171528 KB Output is correct
3 Correct 946 ms 171612 KB Output is correct
4 Correct 663 ms 170488 KB Output is correct
5 Correct 104 ms 156876 KB Output is correct
6 Correct 921 ms 171100 KB Output is correct
7 Correct 232 ms 165400 KB Output is correct
8 Correct 778 ms 163208 KB Output is correct
9 Correct 947 ms 171560 KB Output is correct
10 Correct 925 ms 171584 KB Output is correct
11 Correct 906 ms 171584 KB Output is correct
12 Correct 108 ms 156904 KB Output is correct
13 Correct 109 ms 156892 KB Output is correct
14 Correct 117 ms 156804 KB Output is correct
15 Correct 102 ms 156812 KB Output is correct
16 Correct 104 ms 156916 KB Output is correct
17 Correct 109 ms 156916 KB Output is correct
18 Correct 105 ms 156824 KB Output is correct
19 Correct 109 ms 156928 KB Output is correct
20 Correct 107 ms 156840 KB Output is correct
21 Correct 106 ms 156844 KB Output is correct
22 Correct 106 ms 156844 KB Output is correct
23 Correct 104 ms 156840 KB Output is correct
24 Correct 108 ms 156832 KB Output is correct
25 Correct 105 ms 156916 KB Output is correct
26 Correct 105 ms 156808 KB Output is correct
27 Correct 104 ms 156904 KB Output is correct
28 Correct 113 ms 156988 KB Output is correct
29 Correct 121 ms 157072 KB Output is correct
30 Correct 114 ms 157004 KB Output is correct
31 Correct 111 ms 157164 KB Output is correct
32 Correct 112 ms 157056 KB Output is correct
33 Correct 114 ms 157036 KB Output is correct
34 Correct 114 ms 156984 KB Output is correct
35 Correct 887 ms 170616 KB Output is correct
36 Correct 620 ms 182196 KB Output is correct
37 Correct 911 ms 181224 KB Output is correct
38 Correct 658 ms 182288 KB Output is correct
39 Correct 1359 ms 182464 KB Output is correct
40 Correct 948 ms 182972 KB Output is correct
41 Correct 2621 ms 182344 KB Output is correct
42 Correct 253 ms 170692 KB Output is correct
43 Correct 780 ms 168436 KB Output is correct
44 Correct 1445 ms 180992 KB Output is correct
45 Correct 1822 ms 181952 KB Output is correct
46 Correct 2629 ms 176064 KB Output is correct
47 Correct 2535 ms 176064 KB Output is correct
48 Correct 947 ms 184244 KB Output is correct
49 Correct 684 ms 185356 KB Output is correct
50 Correct 933 ms 182568 KB Output is correct
51 Correct 1012 ms 182700 KB Output is correct
52 Correct 101 ms 156928 KB Output is correct
53 Correct 2701 ms 185452 KB Output is correct
54 Correct 1434 ms 183876 KB Output is correct
55 Correct 1801 ms 184960 KB Output is correct
56 Correct 2618 ms 179008 KB Output is correct
57 Incorrect 820 ms 184744 KB Output isn't correct
58 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 852 ms 171584 KB Output is correct
2 Correct 964 ms 171528 KB Output is correct
3 Correct 946 ms 171612 KB Output is correct
4 Correct 663 ms 170488 KB Output is correct
5 Correct 104 ms 156876 KB Output is correct
6 Correct 921 ms 171100 KB Output is correct
7 Correct 232 ms 165400 KB Output is correct
8 Correct 778 ms 163208 KB Output is correct
9 Correct 947 ms 171560 KB Output is correct
10 Correct 925 ms 171584 KB Output is correct
11 Correct 906 ms 171584 KB Output is correct
12 Correct 108 ms 156904 KB Output is correct
13 Correct 109 ms 156892 KB Output is correct
14 Correct 117 ms 156804 KB Output is correct
15 Correct 102 ms 156812 KB Output is correct
16 Correct 104 ms 156916 KB Output is correct
17 Correct 109 ms 156916 KB Output is correct
18 Correct 105 ms 156824 KB Output is correct
19 Correct 109 ms 156928 KB Output is correct
20 Correct 107 ms 156840 KB Output is correct
21 Correct 106 ms 156844 KB Output is correct
22 Correct 106 ms 156844 KB Output is correct
23 Correct 104 ms 156840 KB Output is correct
24 Correct 108 ms 156832 KB Output is correct
25 Correct 105 ms 156916 KB Output is correct
26 Correct 105 ms 156808 KB Output is correct
27 Correct 104 ms 156904 KB Output is correct
28 Correct 113 ms 156988 KB Output is correct
29 Correct 121 ms 157072 KB Output is correct
30 Correct 114 ms 157004 KB Output is correct
31 Correct 111 ms 157164 KB Output is correct
32 Correct 112 ms 157056 KB Output is correct
33 Correct 114 ms 157036 KB Output is correct
34 Correct 114 ms 156984 KB Output is correct
35 Correct 887 ms 170616 KB Output is correct
36 Correct 620 ms 182196 KB Output is correct
37 Correct 911 ms 181224 KB Output is correct
38 Correct 658 ms 182288 KB Output is correct
39 Correct 1359 ms 182464 KB Output is correct
40 Correct 948 ms 182972 KB Output is correct
41 Correct 2621 ms 182344 KB Output is correct
42 Correct 253 ms 170692 KB Output is correct
43 Correct 780 ms 168436 KB Output is correct
44 Correct 1445 ms 180992 KB Output is correct
45 Correct 1822 ms 181952 KB Output is correct
46 Correct 2629 ms 176064 KB Output is correct
47 Correct 2535 ms 176064 KB Output is correct
48 Correct 947 ms 184244 KB Output is correct
49 Correct 684 ms 185356 KB Output is correct
50 Correct 933 ms 182568 KB Output is correct
51 Correct 1012 ms 182700 KB Output is correct
52 Correct 101 ms 156928 KB Output is correct
53 Correct 2701 ms 185452 KB Output is correct
54 Correct 1434 ms 183876 KB Output is correct
55 Correct 1801 ms 184960 KB Output is correct
56 Correct 2618 ms 179008 KB Output is correct
57 Correct 4228 ms 293732 KB Output is correct
58 Correct 1846 ms 297884 KB Output is correct
59 Correct 3941 ms 284116 KB Output is correct
60 Correct 4446 ms 284148 KB Output is correct
61 Execution timed out 10052 ms 297908 KB Time limit exceeded
62 Halted 0 ms 0 KB -