oj.uz

Submission #401010

# Submission time Handle Problem Language Result Execution time Memory
401010 2021-05-09T06:49:00 Z errorgorn The short shank; Redemption (BOI21_prison) C++17
100 / 100
 1390 ms 460556 KB 
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ii pair<int,int>
#define fi first
#define se second

#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back

#define rep(x,s,e) for (auto 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()

struct node{
	int s,e,m;
	ii val;
	int lazy=0;
	node *l,*r;
	
	node (int _s,int _e){
		s=_s,e=_e,m=s+e>>1;
		val=ii(0,s);
		
		if (s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
		}
	}
	
	void propo(){
		if (lazy){
			val.fi+=lazy;
			if (s!=e){
				l->lazy+=lazy;
				r->lazy+=lazy;
			}
			lazy=0;
		}
	}
	
	void update(int i,int j,int k){
		if (s==i && e==j) lazy+=k;
		else{
			if (j<=m) l->update(i,j,k);
			else if (m<i) r->update(i,j,k);
			else l->update(i,m,k),r->update(m+1,j,k);
			
			l->propo(),r->propo();
			val=max(l->val,r->val);
		}
	}
	
	ii query(int i,int j){
		propo();
		
		if (s==i && e==j) return val;
		else if (j<=m) return l->query(i,j);
		else if (m<i) return r->query(i,j);
		else return max(l->query(i,m),r->query(m+1,j));
	}
} *root=new node(0,4000005);

int n,d,t;
int arr[2000005];
int nxt[2000005];

vector<ii> brac;

int dist[4000005];
int ptr[4000005];
int range[4000005];

inline void read(int& x) {
    x = 0;
    char ch = getchar_unlocked();
    while (ch&16){ 
		//this will break when ‘\n’ or ‘ ‘ is encountered
		x = (x << 3) + (x << 1) + (ch&15);
		ch = getchar_unlocked();
	}
}

main(){
	cin.tie(0);
	cout.tie(0);
	cin.sync_with_stdio(false);
	
	read(n),read(d),read(t);
	rep(x,0,n) read(arr[x]);
	
	arr[n]=-1;
	vector<int> stk={n};
	
	rep(x,n,0){
		while (arr[x]-x<arr[stk.back()]-stk.back()) stk.pob();
		nxt[x]=min(stk.back()-x,max(t-arr[x]+1,0));
		stk.pub(x);
	}
	
	//rep(x,0,n) cout<<nxt[x]<<" "; cout<<endl;
	
	rep(x,0,n) if (nxt[x]){
		brac.pub(ii(x,1));
		brac.pub(ii(x+nxt[x],0));
	}
	
	sort(all(brac));
	
	/*
	for (auto &it:brac){
		cout<<it.fi<<" "<<it.se<<endl;
	}
	*/
	
	stk.clear();
	int p=0;
	int IDX=0;
	bool pc=false;
	int s=0;
	
	memset(ptr,-1,sizeof(ptr));
	
	int ans=0;
	for (auto &it:brac){
		range[IDX]=IDX;
		
		if (pc && !stk.empty()){
			ptr[stk.back()]=IDX;
			stk.pob();
			range[IDX]=range[stk.back()];
			ptr[stk.back()]=IDX;
			stk.pob();
		}
	
		if (it.se==1){
			ans++;
			
			if (s){
				dist[IDX]=it.fi-p;
				stk.pub(IDX);
				IDX++;
			}
			p=it.fi+1;
			pc=false;
			
			s++;
		}
		else{
			dist[IDX]=it.fi-p;
			p=it.fi;
			pc=true;
			
			stk.pub(IDX);
			IDX++;
			
			s--;
		}
		if (s==0) stk.pob();
		
		//cout<<it.fi<<" "<<it.se<<" "<<IDX<<endl;
	}
	
	//rep(x,0,IDX) cout<<dist[x]<<" "; cout<<endl;
	//rep(x,0,IDX) cout<<ptr[x]<<" "; cout<<endl;
	//rep(x,0,IDX) cout<<range[x]<<" "; cout<<endl;
	
	rep(x,0,IDX) ans+=dist[x];
	rep(x,0,IDX) root->update(range[x],x,dist[x]);
	
	
	rep(zzz,0,d){
		auto temp=root->query(0,4000005);
		if (temp.fi==0) break;
		
		ans-=temp.fi;
		while (temp.se!=-1){
			if (dist[temp.se]==-1) break;
			root->update(range[temp.se],temp.se,-dist[temp.se]);
			dist[temp.se]=-1;
			
			temp.se=ptr[temp.se];
		}
	}
	
	cout<<ans<<endl;
}

Compilation message

prison.cpp: In constructor 'node::node(int, int)':
prison.cpp:29:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |   s=_s,e=_e,m=s+e>>1;
      |               ~^~
prison.cpp: At global scope:
prison.cpp:91:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   91 | main(){
      |      ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 420 ms 391652 KB Output is correct
2 Correct 404 ms 391620 KB Output is correct
3 Correct 410 ms 391748 KB Output is correct
4 Correct 410 ms 391816 KB Output is correct
5 Correct 418 ms 391744 KB Output is correct
6 Correct 398 ms 391684 KB Output is correct
7 Correct 407 ms 391620 KB Output is correct
8 Correct 398 ms 391668 KB Output is correct
9 Correct 406 ms 391708 KB Output is correct
10 Correct 409 ms 391752 KB Output is correct
11 Correct 401 ms 391780 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 404 ms 391672 KB Output is correct
2 Correct 608 ms 408496 KB Output is correct
3 Correct 672 ms 410920 KB Output is correct
4 Correct 706 ms 407148 KB Output is correct
5 Correct 547 ms 402596 KB Output is correct
6 Correct 496 ms 402848 KB Output is correct
7 Correct 436 ms 399512 KB Output is correct
8 Correct 503 ms 403568 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 420 ms 391652 KB Output is correct
2 Correct 404 ms 391620 KB Output is correct
3 Correct 410 ms 391748 KB Output is correct
4 Correct 410 ms 391816 KB Output is correct
5 Correct 418 ms 391744 KB Output is correct
6 Correct 398 ms 391684 KB Output is correct
7 Correct 407 ms 391620 KB Output is correct
8 Correct 398 ms 391668 KB Output is correct
9 Correct 406 ms 391708 KB Output is correct
10 Correct 409 ms 391752 KB Output is correct
11 Correct 401 ms 391780 KB Output is correct
12 Correct 410 ms 391744 KB Output is correct
13 Correct 403 ms 391752 KB Output is correct
14 Correct 406 ms 391776 KB Output is correct
15 Correct 401 ms 391748 KB Output is correct
16 Correct 402 ms 391820 KB Output is correct
17 Correct 422 ms 391620 KB Output is correct
18 Correct 411 ms 391656 KB Output is correct
19 Correct 406 ms 391672 KB Output is correct
20 Correct 408 ms 391804 KB Output is correct
21 Correct 399 ms 391652 KB Output is correct
22 Correct 409 ms 391640 KB Output is correct
23 Correct 407 ms 391864 KB Output is correct
24 Correct 422 ms 391876 KB Output is correct
25 Correct 413 ms 392004 KB Output is correct
26 Correct 406 ms 391876 KB Output is correct
27 Correct 409 ms 391876 KB Output is correct
28 Correct 405 ms 391804 KB Output is correct
29 Correct 406 ms 391840 KB Output is correct
30 Correct 406 ms 391876 KB Output is correct
31 Correct 404 ms 391796 KB Output is correct
32 Correct 407 ms 391844 KB Output is correct
33 Correct 407 ms 391748 KB Output is correct
34 Correct 413 ms 391876 KB Output is correct
35 Correct 413 ms 391780 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 405 ms 391644 KB Output is correct
2 Correct 432 ms 394032 KB Output is correct
3 Correct 441 ms 394280 KB Output is correct
4 Correct 430 ms 393540 KB Output is correct
5 Correct 432 ms 393872 KB Output is correct
6 Correct 431 ms 393768 KB Output is correct
7 Correct 411 ms 393348 KB Output is correct
8 Correct 422 ms 393368 KB Output is correct
9 Correct 411 ms 392772 KB Output is correct
10 Correct 424 ms 393924 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 420 ms 391652 KB Output is correct
2 Correct 404 ms 391620 KB Output is correct
3 Correct 410 ms 391748 KB Output is correct
4 Correct 410 ms 391816 KB Output is correct
5 Correct 418 ms 391744 KB Output is correct
6 Correct 398 ms 391684 KB Output is correct
7 Correct 407 ms 391620 KB Output is correct
8 Correct 398 ms 391668 KB Output is correct
9 Correct 406 ms 391708 KB Output is correct
10 Correct 409 ms 391752 KB Output is correct
11 Correct 401 ms 391780 KB Output is correct
12 Correct 410 ms 391744 KB Output is correct
13 Correct 403 ms 391752 KB Output is correct
14 Correct 406 ms 391776 KB Output is correct
15 Correct 401 ms 391748 KB Output is correct
16 Correct 402 ms 391820 KB Output is correct
17 Correct 422 ms 391620 KB Output is correct
18 Correct 411 ms 391656 KB Output is correct
19 Correct 406 ms 391672 KB Output is correct
20 Correct 408 ms 391804 KB Output is correct
21 Correct 399 ms 391652 KB Output is correct
22 Correct 409 ms 391640 KB Output is correct
23 Correct 407 ms 391864 KB Output is correct
24 Correct 422 ms 391876 KB Output is correct
25 Correct 413 ms 392004 KB Output is correct
26 Correct 406 ms 391876 KB Output is correct
27 Correct 409 ms 391876 KB Output is correct
28 Correct 405 ms 391804 KB Output is correct
29 Correct 406 ms 391840 KB Output is correct
30 Correct 406 ms 391876 KB Output is correct
31 Correct 404 ms 391796 KB Output is correct
32 Correct 407 ms 391844 KB Output is correct
33 Correct 407 ms 391748 KB Output is correct
34 Correct 413 ms 391876 KB Output is correct
35 Correct 413 ms 391780 KB Output is correct
36 Correct 405 ms 391644 KB Output is correct
37 Correct 432 ms 394032 KB Output is correct
38 Correct 441 ms 394280 KB Output is correct
39 Correct 430 ms 393540 KB Output is correct
40 Correct 432 ms 393872 KB Output is correct
41 Correct 431 ms 393768 KB Output is correct
42 Correct 411 ms 393348 KB Output is correct
43 Correct 422 ms 393368 KB Output is correct
44 Correct 411 ms 392772 KB Output is correct
45 Correct 424 ms 393924 KB Output is correct
46 Correct 406 ms 391688 KB Output is correct
47 Correct 398 ms 391620 KB Output is correct
48 Correct 411 ms 391752 KB Output is correct
49 Correct 402 ms 391620 KB Output is correct
50 Correct 409 ms 391632 KB Output is correct
51 Correct 402 ms 391660 KB Output is correct
52 Correct 408 ms 391876 KB Output is correct
53 Correct 408 ms 391624 KB Output is correct
54 Correct 408 ms 391744 KB Output is correct
55 Correct 401 ms 391620 KB Output is correct
56 Correct 400 ms 391620 KB Output is correct
57 Correct 409 ms 391872 KB Output is correct
58 Correct 404 ms 391860 KB Output is correct
59 Correct 419 ms 391948 KB Output is correct
60 Correct 411 ms 391768 KB Output is correct
61 Correct 408 ms 391928 KB Output is correct
62 Correct 403 ms 391876 KB Output is correct
63 Correct 409 ms 391868 KB Output is correct
64 Correct 404 ms 391748 KB Output is correct
65 Correct 401 ms 391780 KB Output is correct
66 Correct 402 ms 391852 KB Output is correct
67 Correct 411 ms 391876 KB Output is correct
68 Correct 409 ms 391876 KB Output is correct
69 Correct 403 ms 391800 KB Output is correct
70 Correct 405 ms 391676 KB Output is correct
71 Correct 429 ms 394008 KB Output is correct
72 Correct 442 ms 394348 KB Output is correct
73 Correct 427 ms 393580 KB Output is correct
74 Correct 429 ms 393904 KB Output is correct
75 Correct 428 ms 393832 KB Output is correct
76 Correct 416 ms 393360 KB Output is correct
77 Correct 424 ms 393432 KB Output is correct
78 Correct 404 ms 392876 KB Output is correct
79 Correct 413 ms 394132 KB Output is correct
80 Correct 440 ms 394300 KB Output is correct
81 Correct 436 ms 394044 KB Output is correct
82 Correct 448 ms 394372 KB Output is correct
83 Correct 435 ms 393568 KB Output is correct
84 Correct 427 ms 393568 KB Output is correct
85 Correct 424 ms 393536 KB Output is correct
86 Correct 420 ms 393592 KB Output is correct
87 Correct 416 ms 393476 KB Output is correct
88 Correct 413 ms 392900 KB Output is correct
89 Correct 421 ms 392900 KB Output is correct
90 Correct 421 ms 393348 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 420 ms 391652 KB Output is correct
2 Correct 404 ms 391620 KB Output is correct
3 Correct 410 ms 391748 KB Output is correct
4 Correct 410 ms 391816 KB Output is correct
5 Correct 418 ms 391744 KB Output is correct
6 Correct 398 ms 391684 KB Output is correct
7 Correct 407 ms 391620 KB Output is correct
8 Correct 398 ms 391668 KB Output is correct
9 Correct 406 ms 391708 KB Output is correct
10 Correct 409 ms 391752 KB Output is correct
11 Correct 401 ms 391780 KB Output is correct
12 Correct 404 ms 391672 KB Output is correct
13 Correct 608 ms 408496 KB Output is correct
14 Correct 672 ms 410920 KB Output is correct
15 Correct 706 ms 407148 KB Output is correct
16 Correct 547 ms 402596 KB Output is correct
17 Correct 496 ms 402848 KB Output is correct
18 Correct 436 ms 399512 KB Output is correct
19 Correct 503 ms 403568 KB Output is correct
20 Correct 410 ms 391744 KB Output is correct
21 Correct 403 ms 391752 KB Output is correct
22 Correct 406 ms 391776 KB Output is correct
23 Correct 401 ms 391748 KB Output is correct
24 Correct 402 ms 391820 KB Output is correct
25 Correct 422 ms 391620 KB Output is correct
26 Correct 411 ms 391656 KB Output is correct
27 Correct 406 ms 391672 KB Output is correct
28 Correct 408 ms 391804 KB Output is correct
29 Correct 399 ms 391652 KB Output is correct
30 Correct 409 ms 391640 KB Output is correct
31 Correct 407 ms 391864 KB Output is correct
32 Correct 422 ms 391876 KB Output is correct
33 Correct 413 ms 392004 KB Output is correct
34 Correct 406 ms 391876 KB Output is correct
35 Correct 409 ms 391876 KB Output is correct
36 Correct 405 ms 391804 KB Output is correct
37 Correct 406 ms 391840 KB Output is correct
38 Correct 406 ms 391876 KB Output is correct
39 Correct 404 ms 391796 KB Output is correct
40 Correct 407 ms 391844 KB Output is correct
41 Correct 407 ms 391748 KB Output is correct
42 Correct 413 ms 391876 KB Output is correct
43 Correct 413 ms 391780 KB Output is correct
44 Correct 405 ms 391644 KB Output is correct
45 Correct 432 ms 394032 KB Output is correct
46 Correct 441 ms 394280 KB Output is correct
47 Correct 430 ms 393540 KB Output is correct
48 Correct 432 ms 393872 KB Output is correct
49 Correct 431 ms 393768 KB Output is correct
50 Correct 411 ms 393348 KB Output is correct
51 Correct 422 ms 393368 KB Output is correct
52 Correct 411 ms 392772 KB Output is correct
53 Correct 424 ms 393924 KB Output is correct
54 Correct 406 ms 391688 KB Output is correct
55 Correct 398 ms 391620 KB Output is correct
56 Correct 411 ms 391752 KB Output is correct
57 Correct 402 ms 391620 KB Output is correct
58 Correct 409 ms 391632 KB Output is correct
59 Correct 402 ms 391660 KB Output is correct
60 Correct 408 ms 391876 KB Output is correct
61 Correct 408 ms 391624 KB Output is correct
62 Correct 408 ms 391744 KB Output is correct
63 Correct 401 ms 391620 KB Output is correct
64 Correct 400 ms 391620 KB Output is correct
65 Correct 409 ms 391872 KB Output is correct
66 Correct 404 ms 391860 KB Output is correct
67 Correct 419 ms 391948 KB Output is correct
68 Correct 411 ms 391768 KB Output is correct
69 Correct 408 ms 391928 KB Output is correct
70 Correct 403 ms 391876 KB Output is correct
71 Correct 409 ms 391868 KB Output is correct
72 Correct 404 ms 391748 KB Output is correct
73 Correct 401 ms 391780 KB Output is correct
74 Correct 402 ms 391852 KB Output is correct
75 Correct 411 ms 391876 KB Output is correct
76 Correct 409 ms 391876 KB Output is correct
77 Correct 403 ms 391800 KB Output is correct
78 Correct 405 ms 391676 KB Output is correct
79 Correct 429 ms 394008 KB Output is correct
80 Correct 442 ms 394348 KB Output is correct
81 Correct 427 ms 393580 KB Output is correct
82 Correct 429 ms 393904 KB Output is correct
83 Correct 428 ms 393832 KB Output is correct
84 Correct 416 ms 393360 KB Output is correct
85 Correct 424 ms 393432 KB Output is correct
86 Correct 404 ms 392876 KB Output is correct
87 Correct 413 ms 394132 KB Output is correct
88 Correct 440 ms 394300 KB Output is correct
89 Correct 436 ms 394044 KB Output is correct
90 Correct 448 ms 394372 KB Output is correct
91 Correct 435 ms 393568 KB Output is correct
92 Correct 427 ms 393568 KB Output is correct
93 Correct 424 ms 393536 KB Output is correct
94 Correct 420 ms 393592 KB Output is correct
95 Correct 416 ms 393476 KB Output is correct
96 Correct 413 ms 392900 KB Output is correct
97 Correct 421 ms 392900 KB Output is correct
98 Correct 421 ms 393348 KB Output is correct
99 Correct 407 ms 391712 KB Output is correct
100 Correct 421 ms 391656 KB Output is correct
101 Correct 411 ms 391696 KB Output is correct
102 Correct 416 ms 391620 KB Output is correct
103 Correct 405 ms 391620 KB Output is correct
104 Correct 409 ms 391620 KB Output is correct
105 Correct 409 ms 391676 KB Output is correct
106 Correct 411 ms 391668 KB Output is correct
107 Correct 410 ms 391636 KB Output is correct
108 Correct 408 ms 391712 KB Output is correct
109 Correct 414 ms 391620 KB Output is correct
110 Correct 412 ms 391748 KB Output is correct
111 Correct 621 ms 408408 KB Output is correct
112 Correct 678 ms 411036 KB Output is correct
113 Correct 693 ms 407140 KB Output is correct
114 Correct 551 ms 402636 KB Output is correct
115 Correct 500 ms 402848 KB Output is correct
116 Correct 435 ms 399500 KB Output is correct
117 Correct 500 ms 403512 KB Output is correct
118 Correct 432 ms 391852 KB Output is correct
119 Correct 413 ms 391816 KB Output is correct
120 Correct 409 ms 391980 KB Output is correct
121 Correct 408 ms 391836 KB Output is correct
122 Correct 417 ms 391772 KB Output is correct
123 Correct 429 ms 391868 KB Output is correct
124 Correct 409 ms 391764 KB Output is correct
125 Correct 420 ms 391740 KB Output is correct
126 Correct 409 ms 391816 KB Output is correct
127 Correct 410 ms 391832 KB Output is correct
128 Correct 412 ms 391748 KB Output is correct
129 Correct 417 ms 391824 KB Output is correct
130 Correct 409 ms 391876 KB Output is correct
131 Correct 417 ms 391620 KB Output is correct
132 Correct 444 ms 394044 KB Output is correct
133 Correct 439 ms 394424 KB Output is correct
134 Correct 421 ms 393568 KB Output is correct
135 Correct 420 ms 393788 KB Output is correct
136 Correct 454 ms 393788 KB Output is correct
137 Correct 409 ms 393384 KB Output is correct
138 Correct 406 ms 393420 KB Output is correct
139 Correct 393 ms 392772 KB Output is correct
140 Correct 427 ms 393788 KB Output is correct
141 Correct 440 ms 394368 KB Output is correct
142 Correct 458 ms 394032 KB Output is correct
143 Correct 461 ms 394356 KB Output is correct
144 Correct 434 ms 393560 KB Output is correct
145 Correct 436 ms 393324 KB Output is correct
146 Correct 423 ms 393548 KB Output is correct
147 Correct 437 ms 393440 KB Output is correct
148 Correct 434 ms 393412 KB Output is correct
149 Correct 411 ms 392824 KB Output is correct
150 Correct 407 ms 392880 KB Output is correct
151 Correct 434 ms 393348 KB Output is correct
152 Correct 1339 ms 441812 KB Output is correct
153 Correct 1186 ms 455100 KB Output is correct
154 Correct 1346 ms 460556 KB Output is correct
155 Correct 1390 ms 443716 KB Output is correct
156 Correct 1103 ms 434868 KB Output is correct
157 Correct 664 ms 434192 KB Output is correct
158 Correct 674 ms 434632 KB Output is correct
159 Correct 755 ms 431992 KB Output is correct
160 Correct 931 ms 437632 KB Output is correct
161 Correct 992 ms 444496 KB Output is correct
162 Correct 1043 ms 445876 KB Output is correct