oj.uz

Submission #425111

# Submission time Handle Problem Language Result Execution time Memory
425111 2021-06-12T13:30:57 Z CSQ31 Financial Report (JOI21_financial) C++14
100 / 100
 1066 ms 72704 KB 
#pragma GCC optimize("Ofast") 
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) a.size()
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define MOD (ll)(998244353)
#define INF (ll)(1e18)
#define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\
debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> VII;
ll gcd(ll a,ll b){if(!b)return a;else return gcd(b,a%b);}
const int MAXN = 3e5+55;
vector<int>par(MAXN),rg(MAXN);
vector<multiset<int>>has(MAXN);
int n,d;
int find(int x){
	if(par[x] == x)return x;
	else return par[x] = find(par[x]);
}
multiset<int>cur;
void add(int x){
	cur.insert(x);
	auto p = cur.ub(x);
	if(p != cur.end() && *p - x <=d)par[x] = *p;
	else par[x] = x;
	p = cur.lb(x);
	if(p != cur.begin()){
		p--;
		if(x - *p <= d){
			par[*p] = x;
		}
	}
}
vector<int>t(4*MAXN,-1e9);
void update(int v,int l,int r,int pos){
	if(l == r){
		if(has[pos].empty())t[v] = -1e9;
		else {
			auto it = has[pos].end();
			it--;
			t[v] = *it;
		}
		return;
	}
	int tm = (l+r)/2;
	if(pos<=tm)update(2*v,l,tm,pos);
	else update(2*v+1,tm+1,r,pos);
	t[v] = max(t[2*v],t[2*v+1]);
}
int query(int v,int l,int r,int tl,int tr){
	if(l > r)return -1e9;
	if(l == tl && r == tr){
		return t[v];
	}
	int tm = (tl+tr)/2;
	return max(query(2*v,l,min(r,tm),tl,tm),query(2*v+1,max(l,tm+1),r,tm+1,tr));
}
int main()
{
	owo
	cin>>n>>d;
	vector<int>a(n),crd;
	for(int i=0;i<n;i++){
		cin>>a[i];
		crd.pb(a[i]);
	}
	sort(all(crd));
	crd.resize(unique(all(crd)) - crd.begin());
	for(int i=0;i<n;i++)a[i] = lb(all(crd),a[i]) - crd.begin()+1;
	vector<pii>b;
	for(int i=0;i<n;i++)b.pb({a[i],i});
	sort(all(b));
	for(int i=0;i<n;){
		int j = i;
		while(j<n && b[j].fi ==b[i].fi){
			add(b[j].se);
			j++;
		}  
		while(i<j){
			rg[b[i].se] = find(b[i].se)+d-1;
			i++;
		}
	}
	/*
	for(int i=0;i<n;i++)cout<<a[i]<<" ";
	cout<<'\n';
	for(int i=0;i<n;i++)cout<<rg[i]<<" ";
	cout<<'\n';*/
	multiset<pii>can;
	int ans = 0,m = sz(crd);
	if(n==1)ans=1;
	vector<int>dp(n);
	for(int i=0;i<n;i++){
		if(can.empty()){
			dp[i] = 1;
		}else{
			while(!can.empty()){
				auto it = can.ub(make_pair(i-1,-1));
				if(it == can.begin())break;
				it--;
				if(it->fi <= i-1){
					int idx = it->se;
					has[a[idx]].erase(dp[idx]);
					can.erase(it);
					update(1,1,m,a[idx]);
				}
				else break;
			}
			if(a[i] == 1)dp[i] = 1;
			else dp[i] = query(1,1,a[i]-1,1,m) + 1;
			dp[i] = max(dp[i],query(1,a[i],a[i],1,m));
			dp[i] = max(dp[i],1);
		}
	    has[a[i]].insert(dp[i]);
		can.insert({rg[i],i});
		update(1,1,m,a[i]);
		ans = max(ans,dp[i]);
	}
	cout<<ans<<'\n';
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 21452 KB Output is correct
2 Correct 16 ms 21396 KB Output is correct
3 Correct 16 ms 21452 KB Output is correct
4 Correct 15 ms 21408 KB Output is correct
5 Correct 16 ms 21452 KB Output is correct
6 Correct 16 ms 21452 KB Output is correct
7 Correct 14 ms 21368 KB Output is correct
8 Correct 14 ms 21452 KB Output is correct
9 Correct 13 ms 21452 KB Output is correct
10 Correct 14 ms 21440 KB Output is correct
11 Correct 15 ms 21452 KB Output is correct
12 Correct 13 ms 21420 KB Output is correct
13 Correct 13 ms 21452 KB Output is correct
14 Correct 14 ms 21372 KB Output is correct
15 Correct 13 ms 21448 KB Output is correct
16 Correct 15 ms 21416 KB Output is correct
17 Correct 14 ms 21452 KB Output is correct
18 Correct 14 ms 21440 KB Output is correct
19 Correct 13 ms 21452 KB Output is correct
20 Correct 14 ms 21452 KB Output is correct
21 Correct 14 ms 21396 KB Output is correct
22 Correct 15 ms 21452 KB Output is correct
23 Correct 15 ms 21444 KB Output is correct
24 Correct 15 ms 21432 KB Output is correct
25 Correct 14 ms 21452 KB Output is correct
26 Correct 14 ms 21360 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 21452 KB Output is correct
2 Correct 16 ms 21396 KB Output is correct
3 Correct 16 ms 21452 KB Output is correct
4 Correct 15 ms 21408 KB Output is correct
5 Correct 16 ms 21452 KB Output is correct
6 Correct 16 ms 21452 KB Output is correct
7 Correct 14 ms 21368 KB Output is correct
8 Correct 14 ms 21452 KB Output is correct
9 Correct 13 ms 21452 KB Output is correct
10 Correct 14 ms 21440 KB Output is correct
11 Correct 15 ms 21452 KB Output is correct
12 Correct 13 ms 21420 KB Output is correct
13 Correct 13 ms 21452 KB Output is correct
14 Correct 14 ms 21372 KB Output is correct
15 Correct 13 ms 21448 KB Output is correct
16 Correct 15 ms 21416 KB Output is correct
17 Correct 14 ms 21452 KB Output is correct
18 Correct 14 ms 21440 KB Output is correct
19 Correct 13 ms 21452 KB Output is correct
20 Correct 14 ms 21452 KB Output is correct
21 Correct 14 ms 21396 KB Output is correct
22 Correct 15 ms 21452 KB Output is correct
23 Correct 15 ms 21444 KB Output is correct
24 Correct 15 ms 21432 KB Output is correct
25 Correct 14 ms 21452 KB Output is correct
26 Correct 14 ms 21360 KB Output is correct
27 Correct 14 ms 21452 KB Output is correct
28 Correct 14 ms 21480 KB Output is correct
29 Correct 14 ms 21520 KB Output is correct
30 Correct 16 ms 21624 KB Output is correct
31 Correct 14 ms 21516 KB Output is correct
32 Correct 14 ms 21500 KB Output is correct
33 Correct 14 ms 21504 KB Output is correct
34 Correct 16 ms 21508 KB Output is correct
35 Correct 16 ms 21472 KB Output is correct
36 Correct 14 ms 21520 KB Output is correct
37 Correct 16 ms 21428 KB Output is correct
38 Correct 15 ms 21436 KB Output is correct
39 Correct 14 ms 21536 KB Output is correct
40 Correct 14 ms 21452 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 21452 KB Output is correct
2 Correct 16 ms 21396 KB Output is correct
3 Correct 16 ms 21452 KB Output is correct
4 Correct 15 ms 21408 KB Output is correct
5 Correct 16 ms 21452 KB Output is correct
6 Correct 16 ms 21452 KB Output is correct
7 Correct 14 ms 21368 KB Output is correct
8 Correct 14 ms 21452 KB Output is correct
9 Correct 13 ms 21452 KB Output is correct
10 Correct 14 ms 21440 KB Output is correct
11 Correct 15 ms 21452 KB Output is correct
12 Correct 13 ms 21420 KB Output is correct
13 Correct 13 ms 21452 KB Output is correct
14 Correct 14 ms 21372 KB Output is correct
15 Correct 13 ms 21448 KB Output is correct
16 Correct 15 ms 21416 KB Output is correct
17 Correct 14 ms 21452 KB Output is correct
18 Correct 14 ms 21440 KB Output is correct
19 Correct 13 ms 21452 KB Output is correct
20 Correct 14 ms 21452 KB Output is correct
21 Correct 14 ms 21396 KB Output is correct
22 Correct 15 ms 21452 KB Output is correct
23 Correct 15 ms 21444 KB Output is correct
24 Correct 15 ms 21432 KB Output is correct
25 Correct 14 ms 21452 KB Output is correct
26 Correct 14 ms 21360 KB Output is correct
27 Correct 14 ms 21452 KB Output is correct
28 Correct 14 ms 21480 KB Output is correct
29 Correct 14 ms 21520 KB Output is correct
30 Correct 16 ms 21624 KB Output is correct
31 Correct 14 ms 21516 KB Output is correct
32 Correct 14 ms 21500 KB Output is correct
33 Correct 14 ms 21504 KB Output is correct
34 Correct 16 ms 21508 KB Output is correct
35 Correct 16 ms 21472 KB Output is correct
36 Correct 14 ms 21520 KB Output is correct
37 Correct 16 ms 21428 KB Output is correct
38 Correct 15 ms 21436 KB Output is correct
39 Correct 14 ms 21536 KB Output is correct
40 Correct 14 ms 21452 KB Output is correct
41 Correct 24 ms 21952 KB Output is correct
42 Correct 25 ms 21864 KB Output is correct
43 Correct 19 ms 22080 KB Output is correct
44 Correct 23 ms 22220 KB Output is correct
45 Correct 23 ms 22412 KB Output is correct
46 Correct 24 ms 22532 KB Output is correct
47 Correct 29 ms 21944 KB Output is correct
48 Correct 25 ms 21988 KB Output is correct
49 Correct 25 ms 22212 KB Output is correct
50 Correct 26 ms 22092 KB Output is correct
51 Correct 24 ms 21956 KB Output is correct
52 Correct 25 ms 21960 KB Output is correct
53 Correct 22 ms 21852 KB Output is correct
54 Correct 25 ms 21960 KB Output is correct
55 Correct 25 ms 22476 KB Output is correct
56 Correct 24 ms 22528 KB Output is correct
57 Correct 30 ms 22452 KB Output is correct
58 Correct 21 ms 22556 KB Output is correct
59 Correct 21 ms 22584 KB Output is correct
60 Correct 22 ms 22476 KB Output is correct
61 Correct 22 ms 22484 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 386 ms 72648 KB Output is correct
2 Correct 337 ms 46992 KB Output is correct
3 Correct 472 ms 41964 KB Output is correct
4 Correct 869 ms 41356 KB Output is correct
5 Correct 691 ms 41400 KB Output is correct
6 Correct 899 ms 41332 KB Output is correct
7 Correct 454 ms 41272 KB Output is correct
8 Correct 505 ms 69444 KB Output is correct
9 Correct 422 ms 41400 KB Output is correct
10 Correct 476 ms 55252 KB Output is correct
11 Correct 664 ms 41324 KB Output is correct
12 Correct 721 ms 41408 KB Output is correct
13 Correct 726 ms 41384 KB Output is correct
14 Correct 871 ms 41344 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 396 ms 72704 KB Output is correct
2 Correct 612 ms 69620 KB Output is correct
3 Correct 894 ms 69560 KB Output is correct
4 Correct 947 ms 69708 KB Output is correct
5 Correct 851 ms 69560 KB Output is correct
6 Correct 1000 ms 69572 KB Output is correct
7 Correct 514 ms 69564 KB Output is correct
8 Correct 501 ms 69560 KB Output is correct
9 Correct 484 ms 69272 KB Output is correct
10 Correct 686 ms 69384 KB Output is correct
11 Correct 968 ms 69568 KB Output is correct
12 Correct 809 ms 69484 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 21452 KB Output is correct
2 Correct 16 ms 21396 KB Output is correct
3 Correct 16 ms 21452 KB Output is correct
4 Correct 15 ms 21408 KB Output is correct
5 Correct 16 ms 21452 KB Output is correct
6 Correct 16 ms 21452 KB Output is correct
7 Correct 14 ms 21368 KB Output is correct
8 Correct 14 ms 21452 KB Output is correct
9 Correct 13 ms 21452 KB Output is correct
10 Correct 14 ms 21440 KB Output is correct
11 Correct 15 ms 21452 KB Output is correct
12 Correct 13 ms 21420 KB Output is correct
13 Correct 13 ms 21452 KB Output is correct
14 Correct 14 ms 21372 KB Output is correct
15 Correct 13 ms 21448 KB Output is correct
16 Correct 15 ms 21416 KB Output is correct
17 Correct 14 ms 21452 KB Output is correct
18 Correct 14 ms 21440 KB Output is correct
19 Correct 13 ms 21452 KB Output is correct
20 Correct 14 ms 21452 KB Output is correct
21 Correct 14 ms 21396 KB Output is correct
22 Correct 15 ms 21452 KB Output is correct
23 Correct 15 ms 21444 KB Output is correct
24 Correct 15 ms 21432 KB Output is correct
25 Correct 14 ms 21452 KB Output is correct
26 Correct 14 ms 21360 KB Output is correct
27 Correct 14 ms 21452 KB Output is correct
28 Correct 14 ms 21480 KB Output is correct
29 Correct 14 ms 21520 KB Output is correct
30 Correct 16 ms 21624 KB Output is correct
31 Correct 14 ms 21516 KB Output is correct
32 Correct 14 ms 21500 KB Output is correct
33 Correct 14 ms 21504 KB Output is correct
34 Correct 16 ms 21508 KB Output is correct
35 Correct 16 ms 21472 KB Output is correct
36 Correct 14 ms 21520 KB Output is correct
37 Correct 16 ms 21428 KB Output is correct
38 Correct 15 ms 21436 KB Output is correct
39 Correct 14 ms 21536 KB Output is correct
40 Correct 14 ms 21452 KB Output is correct
41 Correct 24 ms 21952 KB Output is correct
42 Correct 25 ms 21864 KB Output is correct
43 Correct 19 ms 22080 KB Output is correct
44 Correct 23 ms 22220 KB Output is correct
45 Correct 23 ms 22412 KB Output is correct
46 Correct 24 ms 22532 KB Output is correct
47 Correct 29 ms 21944 KB Output is correct
48 Correct 25 ms 21988 KB Output is correct
49 Correct 25 ms 22212 KB Output is correct
50 Correct 26 ms 22092 KB Output is correct
51 Correct 24 ms 21956 KB Output is correct
52 Correct 25 ms 21960 KB Output is correct
53 Correct 22 ms 21852 KB Output is correct
54 Correct 25 ms 21960 KB Output is correct
55 Correct 25 ms 22476 KB Output is correct
56 Correct 24 ms 22528 KB Output is correct
57 Correct 30 ms 22452 KB Output is correct
58 Correct 21 ms 22556 KB Output is correct
59 Correct 21 ms 22584 KB Output is correct
60 Correct 22 ms 22476 KB Output is correct
61 Correct 22 ms 22484 KB Output is correct
62 Correct 386 ms 72648 KB Output is correct
63 Correct 337 ms 46992 KB Output is correct
64 Correct 472 ms 41964 KB Output is correct
65 Correct 869 ms 41356 KB Output is correct
66 Correct 691 ms 41400 KB Output is correct
67 Correct 899 ms 41332 KB Output is correct
68 Correct 454 ms 41272 KB Output is correct
69 Correct 505 ms 69444 KB Output is correct
70 Correct 422 ms 41400 KB Output is correct
71 Correct 476 ms 55252 KB Output is correct
72 Correct 664 ms 41324 KB Output is correct
73 Correct 721 ms 41408 KB Output is correct
74 Correct 726 ms 41384 KB Output is correct
75 Correct 871 ms 41344 KB Output is correct
76 Correct 396 ms 72704 KB Output is correct
77 Correct 612 ms 69620 KB Output is correct
78 Correct 894 ms 69560 KB Output is correct
79 Correct 947 ms 69708 KB Output is correct
80 Correct 851 ms 69560 KB Output is correct
81 Correct 1000 ms 69572 KB Output is correct
82 Correct 514 ms 69564 KB Output is correct
83 Correct 501 ms 69560 KB Output is correct
84 Correct 484 ms 69272 KB Output is correct
85 Correct 686 ms 69384 KB Output is correct
86 Correct 968 ms 69568 KB Output is correct
87 Correct 809 ms 69484 KB Output is correct
88 Correct 684 ms 41732 KB Output is correct
89 Correct 947 ms 42028 KB Output is correct
90 Correct 822 ms 48824 KB Output is correct
91 Correct 906 ms 66472 KB Output is correct
92 Correct 519 ms 69688 KB Output is correct
93 Correct 914 ms 69580 KB Output is correct
94 Correct 953 ms 69536 KB Output is correct
95 Correct 780 ms 41448 KB Output is correct
96 Correct 928 ms 45460 KB Output is correct
97 Correct 1066 ms 51116 KB Output is correct
98 Correct 927 ms 66156 KB Output is correct
99 Correct 904 ms 69220 KB Output is correct
100 Correct 955 ms 69244 KB Output is correct
101 Correct 446 ms 41404 KB Output is correct
102 Correct 538 ms 41360 KB Output is correct
103 Correct 573 ms 41520 KB Output is correct
104 Correct 670 ms 42284 KB Output is correct
105 Correct 821 ms 49912 KB Output is correct
106 Correct 595 ms 68324 KB Output is correct
107 Correct 665 ms 69420 KB Output is correct
108 Correct 853 ms 69568 KB Output is correct
109 Correct 799 ms 41644 KB Output is correct
110 Correct 982 ms 59708 KB Output is correct
111 Correct 993 ms 65280 KB Output is correct
112 Correct 764 ms 64628 KB Output is correct
113 Correct 998 ms 69588 KB Output is correct
114 Correct 853 ms 69576 KB Output is correct
115 Correct 517 ms 69516 KB Output is correct
116 Correct 526 ms 69724 KB Output is correct
117 Correct 600 ms 69636 KB Output is correct
118 Correct 625 ms 69508 KB Output is correct
119 Correct 621 ms 69364 KB Output is correct
120 Correct 623 ms 69424 KB Output is correct