답안 #530651

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
530651	2022-02-26T07:17:04 Z	huangqr	Financial Report (JOI21_financial)	C++14	100 / 100	990 ms	65808 KB

Main

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ld,ld> pd;
typedef pair<ll,ll> pl;
typedef pair<ll,pl> ppl;
const ll lim=3e5+5,mod=1e9+7;
ll par[lim],a[lim],dp[lim]; //Calced vals can be updated later. In a strict DP sense it would be dp(pos, time) rather than just dp(pos)

ll fs(ll x){
	if(x==par[x])return x;
	else return par[x]=fs(par[x]);
}

void mergeset(ll a,ll b){
	a=fs(a),b=fs(b);
	if(a==b)return;
	par[a]=b;
}

struct node{
	ll s,e,m,v=0,tomaxify=0;
	bool lazyflag=0,active=0;
	node *l,*r;
	node(ll ss,ll ee){
		s=ss,e=ee,m=(s+e)/2;
		if(s==e)l=r=NULL;
		else l=new node(s,m),r=new node(m+1,e);
	}
	ll push(){
		if(!active){
			tomaxify=lazyflag=0;
			return v;
		}
		if(lazyflag){
			v=max(v,tomaxify);
			if(s!=e){
				if(l->active){
					l->lazyflag=1;
					l->tomaxify=max(l->tomaxify,tomaxify);
				}
				if(r->active){
					r->lazyflag=1;
					r->tomaxify=max(r->tomaxify,tomaxify);
				}
			}
			lazyflag=0;
			tomaxify=0;
		}
		return v;
	}
	void activate(ll pos,ll dpv){
		push();
		active=1;
		if(s==e&&s==pos)v=dpv;
		else if(pos<=m)l->activate(pos,dpv);
		else r->activate(pos,dpv);
		if(s!=e){
			v=max(l->v,r->v);
		}
	}
	void maxify(ll a,ll b,ll maxifyval){
		push();
		if(!active)return;
		if(s==a&&e==b){
			lazyflag=1;
			tomaxify=maxifyval;
			push();
		}
		else if(b<=m)l->maxify(a,b,maxifyval);
		else if(a>m)r->maxify(a,b,maxifyval);
		else l->maxify(a,m,maxifyval),r->maxify(m+1,b,maxifyval);
		if(s!=e){
			push();
			v=max(l->push(),r->push());
		}
	}
	ll query(ll a,ll b){
		if(!active)return 0;
		push();
		if(s==a&&e==b)return v;
		else if(b<=m)return l->query(a,b);
		else if(a>m)return r->query(a,b);
		else return max(l->query(a,m),r->query(m+1,b));
	}
}*root;

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	ll n,d;
	cin>>n>>d;
	vector<pl>v;
	root=new node(0,n);
	for(int i=0;i<n;i++){
		cin>>a[i];
		par[i]=i;
		v.emplace_back(a[i],-i);
	}
	sort(v.begin(),v.end());
	for(auto p:v){
		ll i=-p.second;
		
		//dp[i]=max(1ll,dp[i]);
		//for(int j=max(i-d,0ll);j<i;j++)dp[i]=max(dp[i],dp[j]+1);
		if(i>0)dp[i]=1+root->query(max(i-d,0ll),i-1);
		else dp[i]=1;
		root->activate(i,dp[i]);
		
		ll t = fs(i); //t is the rightmost node to which we can push a dp-val update
		while(t < min(i+d,n-1)){
			mergeset(t, t+1);
			t = fs(t);
		}
		
		if(i<n-1)root->maxify(i+1,t,dp[i]);
		//for(int j=i+1;j<=t;j++){
		//	if(dp[j])dp[j]=max(dp[j],dp[i]);
		//}
		
		//cout<<"after "<<i<<" (val "<<p.first<<"):\n";
		//for(int i=0;i<n;i++)cout<<dp[i]<<" ";
		//cout<<"\n";
	}
	
	cout<<root->query(n-1,n-1);
	
	return 0;
}

Subtask #1
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	332 KB	Output is correct
2	Correct	0 ms	332 KB	Output is correct
3	Correct	0 ms	332 KB	Output is correct
4	Correct	0 ms	332 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	0 ms	332 KB	Output is correct
8	Correct	0 ms	204 KB	Output is correct
9	Correct	0 ms	332 KB	Output is correct
10	Correct	0 ms	332 KB	Output is correct
11	Correct	0 ms	332 KB	Output is correct
12	Correct	1 ms	204 KB	Output is correct
13	Correct	0 ms	204 KB	Output is correct
14	Correct	0 ms	332 KB	Output is correct
15	Correct	1 ms	332 KB	Output is correct
16	Correct	0 ms	332 KB	Output is correct
17	Correct	0 ms	332 KB	Output is correct
18	Correct	0 ms	332 KB	Output is correct
19	Correct	0 ms	332 KB	Output is correct
20	Correct	0 ms	332 KB	Output is correct
21	Correct	0 ms	332 KB	Output is correct
22	Correct	0 ms	332 KB	Output is correct
23	Correct	0 ms	332 KB	Output is correct
24	Correct	0 ms	332 KB	Output is correct
25	Correct	1 ms	332 KB	Output is correct
26	Correct	1 ms	332 KB	Output is correct

Subtask #2
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	332 KB	Output is correct
2	Correct	0 ms	332 KB	Output is correct
3	Correct	0 ms	332 KB	Output is correct
4	Correct	0 ms	332 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	0 ms	332 KB	Output is correct
8	Correct	0 ms	204 KB	Output is correct
9	Correct	0 ms	332 KB	Output is correct
10	Correct	0 ms	332 KB	Output is correct
11	Correct	0 ms	332 KB	Output is correct
12	Correct	1 ms	204 KB	Output is correct
13	Correct	0 ms	204 KB	Output is correct
14	Correct	0 ms	332 KB	Output is correct
15	Correct	1 ms	332 KB	Output is correct
16	Correct	0 ms	332 KB	Output is correct
17	Correct	0 ms	332 KB	Output is correct
18	Correct	0 ms	332 KB	Output is correct
19	Correct	0 ms	332 KB	Output is correct
20	Correct	0 ms	332 KB	Output is correct
21	Correct	0 ms	332 KB	Output is correct
22	Correct	0 ms	332 KB	Output is correct
23	Correct	0 ms	332 KB	Output is correct
24	Correct	0 ms	332 KB	Output is correct
25	Correct	1 ms	332 KB	Output is correct
26	Correct	1 ms	332 KB	Output is correct
27	Correct	1 ms	332 KB	Output is correct
28	Correct	1 ms	332 KB	Output is correct
29	Correct	1 ms	332 KB	Output is correct
30	Correct	1 ms	332 KB	Output is correct
31	Correct	1 ms	332 KB	Output is correct
32	Correct	1 ms	332 KB	Output is correct
33	Correct	1 ms	332 KB	Output is correct
34	Correct	1 ms	332 KB	Output is correct
35	Correct	1 ms	460 KB	Output is correct
36	Correct	1 ms	332 KB	Output is correct
37	Correct	1 ms	332 KB	Output is correct
38	Correct	1 ms	332 KB	Output is correct
39	Correct	1 ms	332 KB	Output is correct
40	Correct	1 ms	332 KB	Output is correct

Subtask #3
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	332 KB	Output is correct
2	Correct	0 ms	332 KB	Output is correct
3	Correct	0 ms	332 KB	Output is correct
4	Correct	0 ms	332 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	0 ms	332 KB	Output is correct
8	Correct	0 ms	204 KB	Output is correct
9	Correct	0 ms	332 KB	Output is correct
10	Correct	0 ms	332 KB	Output is correct
11	Correct	0 ms	332 KB	Output is correct
12	Correct	1 ms	204 KB	Output is correct
13	Correct	0 ms	204 KB	Output is correct
14	Correct	0 ms	332 KB	Output is correct
15	Correct	1 ms	332 KB	Output is correct
16	Correct	0 ms	332 KB	Output is correct
17	Correct	0 ms	332 KB	Output is correct
18	Correct	0 ms	332 KB	Output is correct
19	Correct	0 ms	332 KB	Output is correct
20	Correct	0 ms	332 KB	Output is correct
21	Correct	0 ms	332 KB	Output is correct
22	Correct	0 ms	332 KB	Output is correct
23	Correct	0 ms	332 KB	Output is correct
24	Correct	0 ms	332 KB	Output is correct
25	Correct	1 ms	332 KB	Output is correct
26	Correct	1 ms	332 KB	Output is correct
27	Correct	1 ms	332 KB	Output is correct
28	Correct	1 ms	332 KB	Output is correct
29	Correct	1 ms	332 KB	Output is correct
30	Correct	1 ms	332 KB	Output is correct
31	Correct	1 ms	332 KB	Output is correct
32	Correct	1 ms	332 KB	Output is correct
33	Correct	1 ms	332 KB	Output is correct
34	Correct	1 ms	332 KB	Output is correct
35	Correct	1 ms	460 KB	Output is correct
36	Correct	1 ms	332 KB	Output is correct
37	Correct	1 ms	332 KB	Output is correct
38	Correct	1 ms	332 KB	Output is correct
39	Correct	1 ms	332 KB	Output is correct
40	Correct	1 ms	332 KB	Output is correct
41	Correct	6 ms	1740 KB	Output is correct
42	Correct	6 ms	1808 KB	Output is correct
43	Correct	6 ms	1740 KB	Output is correct
44	Correct	7 ms	1612 KB	Output is correct
45	Correct	9 ms	1740 KB	Output is correct
46	Correct	9 ms	1868 KB	Output is correct
47	Correct	6 ms	1740 KB	Output is correct
48	Correct	7 ms	1740 KB	Output is correct
49	Correct	8 ms	1740 KB	Output is correct
50	Correct	8 ms	1840 KB	Output is correct
51	Correct	5 ms	1740 KB	Output is correct
52	Correct	5 ms	1740 KB	Output is correct
53	Correct	4 ms	1740 KB	Output is correct
54	Correct	6 ms	1740 KB	Output is correct
55	Correct	11 ms	1740 KB	Output is correct
56	Correct	10 ms	1740 KB	Output is correct
57	Correct	9 ms	1740 KB	Output is correct
58	Correct	7 ms	1740 KB	Output is correct
59	Correct	7 ms	1740 KB	Output is correct
60	Correct	9 ms	1740 KB	Output is correct
61	Correct	8 ms	1868 KB	Output is correct

Subtask #4
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	377 ms	59680 KB	Output is correct
2	Correct	290 ms	59700 KB	Output is correct
3	Correct	415 ms	59656 KB	Output is correct
4	Correct	446 ms	59664 KB	Output is correct
5	Correct	309 ms	59700 KB	Output is correct
6	Correct	447 ms	59632 KB	Output is correct
7	Correct	165 ms	59316 KB	Output is correct
8	Correct	372 ms	59568 KB	Output is correct
9	Correct	171 ms	59664 KB	Output is correct
10	Correct	275 ms	59700 KB	Output is correct
11	Correct	273 ms	59640 KB	Output is correct
12	Correct	311 ms	59672 KB	Output is correct
13	Correct	266 ms	59724 KB	Output is correct
14	Correct	549 ms	59824 KB	Output is correct

Subtask #5
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	402 ms	59696 KB	Output is correct
2	Correct	648 ms	59668 KB	Output is correct
3	Correct	724 ms	59840 KB	Output is correct
4	Correct	822 ms	60492 KB	Output is correct
5	Correct	623 ms	60204 KB	Output is correct
6	Correct	731 ms	61608 KB	Output is correct
7	Correct	194 ms	63032 KB	Output is correct
8	Correct	389 ms	59628 KB	Output is correct
9	Correct	223 ms	62648 KB	Output is correct
10	Correct	358 ms	62740 KB	Output is correct
11	Correct	668 ms	60336 KB	Output is correct
12	Correct	540 ms	61764 KB	Output is correct

Subtask #6
35.0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	332 KB	Output is correct
2	Correct	0 ms	332 KB	Output is correct
3	Correct	0 ms	332 KB	Output is correct
4	Correct	0 ms	332 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	0 ms	332 KB	Output is correct
8	Correct	0 ms	204 KB	Output is correct
9	Correct	0 ms	332 KB	Output is correct
10	Correct	0 ms	332 KB	Output is correct
11	Correct	0 ms	332 KB	Output is correct
12	Correct	1 ms	204 KB	Output is correct
13	Correct	0 ms	204 KB	Output is correct
14	Correct	0 ms	332 KB	Output is correct
15	Correct	1 ms	332 KB	Output is correct
16	Correct	0 ms	332 KB	Output is correct
17	Correct	0 ms	332 KB	Output is correct
18	Correct	0 ms	332 KB	Output is correct
19	Correct	0 ms	332 KB	Output is correct
20	Correct	0 ms	332 KB	Output is correct
21	Correct	0 ms	332 KB	Output is correct
22	Correct	0 ms	332 KB	Output is correct
23	Correct	0 ms	332 KB	Output is correct
24	Correct	0 ms	332 KB	Output is correct
25	Correct	1 ms	332 KB	Output is correct
26	Correct	1 ms	332 KB	Output is correct
27	Correct	1 ms	332 KB	Output is correct
28	Correct	1 ms	332 KB	Output is correct
29	Correct	1 ms	332 KB	Output is correct
30	Correct	1 ms	332 KB	Output is correct
31	Correct	1 ms	332 KB	Output is correct
32	Correct	1 ms	332 KB	Output is correct
33	Correct	1 ms	332 KB	Output is correct
34	Correct	1 ms	332 KB	Output is correct
35	Correct	1 ms	460 KB	Output is correct
36	Correct	1 ms	332 KB	Output is correct
37	Correct	1 ms	332 KB	Output is correct
38	Correct	1 ms	332 KB	Output is correct
39	Correct	1 ms	332 KB	Output is correct
40	Correct	1 ms	332 KB	Output is correct
41	Correct	6 ms	1740 KB	Output is correct
42	Correct	6 ms	1808 KB	Output is correct
43	Correct	6 ms	1740 KB	Output is correct
44	Correct	7 ms	1612 KB	Output is correct
45	Correct	9 ms	1740 KB	Output is correct
46	Correct	9 ms	1868 KB	Output is correct
47	Correct	6 ms	1740 KB	Output is correct
48	Correct	7 ms	1740 KB	Output is correct
49	Correct	8 ms	1740 KB	Output is correct
50	Correct	8 ms	1840 KB	Output is correct
51	Correct	5 ms	1740 KB	Output is correct
52	Correct	5 ms	1740 KB	Output is correct
53	Correct	4 ms	1740 KB	Output is correct
54	Correct	6 ms	1740 KB	Output is correct
55	Correct	11 ms	1740 KB	Output is correct
56	Correct	10 ms	1740 KB	Output is correct
57	Correct	9 ms	1740 KB	Output is correct
58	Correct	7 ms	1740 KB	Output is correct
59	Correct	7 ms	1740 KB	Output is correct
60	Correct	9 ms	1740 KB	Output is correct
61	Correct	8 ms	1868 KB	Output is correct
62	Correct	377 ms	59680 KB	Output is correct
63	Correct	290 ms	59700 KB	Output is correct
64	Correct	415 ms	59656 KB	Output is correct
65	Correct	446 ms	59664 KB	Output is correct
66	Correct	309 ms	59700 KB	Output is correct
67	Correct	447 ms	59632 KB	Output is correct
68	Correct	165 ms	59316 KB	Output is correct
69	Correct	372 ms	59568 KB	Output is correct
70	Correct	171 ms	59664 KB	Output is correct
71	Correct	275 ms	59700 KB	Output is correct
72	Correct	273 ms	59640 KB	Output is correct
73	Correct	311 ms	59672 KB	Output is correct
74	Correct	266 ms	59724 KB	Output is correct
75	Correct	549 ms	59824 KB	Output is correct
76	Correct	402 ms	59696 KB	Output is correct
77	Correct	648 ms	59668 KB	Output is correct
78	Correct	724 ms	59840 KB	Output is correct
79	Correct	822 ms	60492 KB	Output is correct
80	Correct	623 ms	60204 KB	Output is correct
81	Correct	731 ms	61608 KB	Output is correct
82	Correct	194 ms	63032 KB	Output is correct
83	Correct	389 ms	59628 KB	Output is correct
84	Correct	223 ms	62648 KB	Output is correct
85	Correct	358 ms	62740 KB	Output is correct
86	Correct	668 ms	60336 KB	Output is correct
87	Correct	540 ms	61764 KB	Output is correct
88	Correct	512 ms	62296 KB	Output is correct
89	Correct	564 ms	62344 KB	Output is correct
90	Correct	724 ms	62384 KB	Output is correct
91	Correct	914 ms	62376 KB	Output is correct
92	Correct	672 ms	62324 KB	Output is correct
93	Correct	990 ms	62380 KB	Output is correct
94	Correct	826 ms	65184 KB	Output is correct
95	Correct	413 ms	62312 KB	Output is correct
96	Correct	583 ms	62324 KB	Output is correct
97	Correct	799 ms	62324 KB	Output is correct
98	Correct	868 ms	62316 KB	Output is correct
99	Correct	942 ms	62384 KB	Output is correct
100	Correct	943 ms	62304 KB	Output is correct
101	Correct	193 ms	62492 KB	Output is correct
102	Correct	250 ms	62376 KB	Output is correct
103	Correct	322 ms	62384 KB	Output is correct
104	Correct	390 ms	62364 KB	Output is correct
105	Correct	613 ms	62380 KB	Output is correct
106	Correct	513 ms	62508 KB	Output is correct
107	Correct	615 ms	62508 KB	Output is correct
108	Correct	917 ms	62448 KB	Output is correct
109	Correct	262 ms	62420 KB	Output is correct
110	Correct	705 ms	62320 KB	Output is correct
111	Correct	821 ms	62360 KB	Output is correct
112	Correct	367 ms	62380 KB	Output is correct
113	Correct	897 ms	62380 KB	Output is correct
114	Correct	949 ms	62384 KB	Output is correct
115	Correct	396 ms	62468 KB	Output is correct
116	Correct	377 ms	62428 KB	Output is correct
117	Correct	444 ms	63940 KB	Output is correct
118	Correct	434 ms	64040 KB	Output is correct
119	Correct	592 ms	62280 KB	Output is correct
120	Correct	569 ms	65808 KB	Output is correct

답안 #530651

Compilation message

Subtask #1 14.0 / 14.0

Subtask #2 14.0 / 14.0

Subtask #3 20.0 / 20.0

Subtask #4 12.0 / 12.0

Subtask #5 5.0 / 5.0

Subtask #6 35.0 / 35.0

Subtask #1
14.0 / 14.0

Subtask #2
14.0 / 14.0

Subtask #3
20.0 / 20.0

Subtask #4
12.0 / 12.0

Subtask #5
5.0 / 5.0

Subtask #6
35.0 / 35.0