oj.uz

Submission #768892

# Submission time Handle Problem Language Result Execution time Memory
768892 2023-06-28T20:25:12 Z stefdasca Financial Report (JOI21_financial) C++14
100 / 100
 2519 ms 33276 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
int n, d, aint[1200002];
 
void update(int nod, int st, int dr, int poz, int val)
{
	if(st == dr)
	{
		aint[nod] = val;
		return;
	}
	
	int mid = (st + dr) / 2;
	
	if(poz <= mid)	
		update(nod << 1, st, mid, poz, val);
	else
		update(nod << 1|1, mid+1, dr, poz, val);
		
	aint[nod] = max(aint[nod << 1], aint[nod << 1|1]);
}
 
int query(int nod, int st, int dr, int L, int R)
{
	if(dr < L || st > R)
		return 0;
	if(L <= st && dr <= R)
		return aint[nod];
	
	int mid = (st + dr) / 2;
	
	return max(query(nod << 1, st, mid, L, R), query(nod << 1|1, mid+1, dr, L, R));
}
 
 
int lz[1200002], aint2[1200002];
 
void lazy(int nod, int st, int dr)
{
	aint2[nod] -= lz[nod];
	if(st != dr)
	{
		lz[nod << 1] += lz[nod];
		lz[nod << 1|1] += lz[nod];
	}
	lz[nod] = 0;
}
 
void build(int nod, int st, int dr)
{
	if(st == dr)
	{
		aint2[nod] = n - st + 1;
		return;
	}
	
	int mid = (st + dr) / 2;
	
	build(nod << 1, st, mid);
	build(nod << 1|1, mid+1, dr);
	
	aint2[nod] = max(aint2[nod << 1], aint2[nod << 1|1]);
}
void update2(int nod, int st, int dr, int L, int R, int val)
{
	lazy(nod, st, dr);
	
	if(dr < L || st > R)
		return;
	
	if(L <= st && dr <= R)
	{
		lz[nod] += val;
		lazy(nod, st, dr);
		return;
	}
	
	int mid = (st + dr) / 2;
	
	update2(nod << 1, st, mid, L, R, val);
	update2(nod << 1|1, mid+1, dr, L, R, val);
	
	aint2[nod] = max(aint2[nod << 1], aint2[nod << 1|1]);
}
 
int query2(int nod, int st, int dr, int L, int R)
{
	lazy(nod, st, dr);
	
	if(dr < L || st > R)
		return -1;
	if(L <= st && dr <= R)
		return aint2[nod];
	
	int mid = (st + dr) / 2;
	
	return max(query2(nod << 1, st, mid, L, R), query2(nod << 1|1, mid+1, dr, L, R));
}
 
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> n >> d;
	
	vector<pair<int, int> > v(n+1);
	
	for(int i = 1; i <= n; i++)
	{
		cin >> v[i].first;
		v[i].second = i;
	}
	
	sort(v.begin() + 1, v.begin() + n + 1);
	
	int ans = 0;
	
	vector<int> dp(n+1);
	vector<int> updates;
	
	build(1, 1, n);
	
	set<int> prv;
	
	for(int i = 1; i <= n; i++)
	{
		if(i != 1 && v[i].first > v[i-1].first)
		{
			for(auto x : updates)
			{
				update(1, 1, n, x, dp[x]);
			}
			updates.clear();
		}
		
		// binsearch
		
		set<int> :: iterator it = prv.lower_bound(v[i].second);
		
		int nxt = 1;
		
		if(it != prv.begin())
		{
			it--;
			nxt = *it;
		}
		
		int xx = query2(1, 1, n, v[i].second, v[i].second);
		
	//	cout << nxt << " " << v[i].second << '\n';
		
		update2(1, 1, n, nxt + 1, v[i].second, xx);
		
		prv.insert(v[i].second);
		
		int stx = 1;
		int drx = max(1, v[i].second - d);
		int L = drx;
		int R = v[i].second - 1;
		
	//	cout << L << " " << R << " " << v[i].second << '\n';
		while(stx <= drx)
		{
			int mid = (stx + drx) / 2;
			if(query2(1, 1, n, mid, max(1, v[i].second - d)) >= d)
			{
				L = mid;
				stx = mid + 1;
			}
			else
			{
				drx = mid - 1;
			}
		}
		
	//	cout << L << " " << R << " " << v[i].second << " " << query2(1, 1, n, 4, 4) << '\n';
		
		dp[v[i].second] = 1;
		
		if(R > 0)
			dp[v[i].second] += query(1, 1, n, L, R);
			
		//cout << dp[v[i].second] << '\n';
			
		//cout << dp[v[i].second] << '\n';
		
		updates.push_back(v[i].second);
		ans = max(ans, dp[v[i].second]);
	}
	
	cout << ans << '\n';
	
	return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 336 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 368 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 340 KB Output is correct
21 Correct 0 ms 340 KB Output is correct
22 Correct 0 ms 340 KB Output is correct
23 Correct 0 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 0 ms 340 KB Output is correct
26 Correct 0 ms 340 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 336 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 368 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 340 KB Output is correct
21 Correct 0 ms 340 KB Output is correct
22 Correct 0 ms 340 KB Output is correct
23 Correct 0 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 0 ms 340 KB Output is correct
26 Correct 0 ms 340 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 2 ms 324 KB Output is correct
31 Correct 1 ms 324 KB Output is correct
32 Correct 1 ms 340 KB Output is correct
33 Correct 1 ms 340 KB Output is correct
34 Correct 1 ms 340 KB Output is correct
35 Correct 1 ms 340 KB Output is correct
36 Correct 1 ms 340 KB Output is correct
37 Correct 2 ms 340 KB Output is correct
38 Correct 1 ms 332 KB Output is correct
39 Correct 1 ms 336 KB Output is correct
40 Correct 1 ms 340 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 336 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 368 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 340 KB Output is correct
21 Correct 0 ms 340 KB Output is correct
22 Correct 0 ms 340 KB Output is correct
23 Correct 0 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 0 ms 340 KB Output is correct
26 Correct 0 ms 340 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 2 ms 324 KB Output is correct
31 Correct 1 ms 324 KB Output is correct
32 Correct 1 ms 340 KB Output is correct
33 Correct 1 ms 340 KB Output is correct
34 Correct 1 ms 340 KB Output is correct
35 Correct 1 ms 340 KB Output is correct
36 Correct 1 ms 340 KB Output is correct
37 Correct 2 ms 340 KB Output is correct
38 Correct 1 ms 332 KB Output is correct
39 Correct 1 ms 336 KB Output is correct
40 Correct 1 ms 340 KB Output is correct
41 Correct 26 ms 972 KB Output is correct
42 Correct 25 ms 960 KB Output is correct
43 Correct 24 ms 876 KB Output is correct
44 Correct 22 ms 852 KB Output is correct
45 Correct 26 ms 912 KB Output is correct
46 Correct 8 ms 980 KB Output is correct
47 Correct 24 ms 940 KB Output is correct
48 Correct 25 ms 956 KB Output is correct
49 Correct 26 ms 964 KB Output is correct
50 Correct 25 ms 988 KB Output is correct
51 Correct 24 ms 976 KB Output is correct
52 Correct 25 ms 980 KB Output is correct
53 Correct 23 ms 996 KB Output is correct
54 Correct 24 ms 980 KB Output is correct
55 Correct 29 ms 1024 KB Output is correct
56 Correct 26 ms 916 KB Output is correct
57 Correct 26 ms 880 KB Output is correct
58 Correct 8 ms 980 KB Output is correct
59 Correct 7 ms 964 KB Output is correct
60 Correct 24 ms 880 KB Output is correct
61 Correct 24 ms 872 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1858 ms 27328 KB Output is correct
2 Correct 1834 ms 30380 KB Output is correct
3 Correct 2100 ms 30332 KB Output is correct
4 Correct 2218 ms 30216 KB Output is correct
5 Correct 2081 ms 30248 KB Output is correct
6 Correct 2330 ms 30196 KB Output is correct
7 Correct 1864 ms 30148 KB Output is correct
8 Correct 1755 ms 30132 KB Output is correct
9 Correct 1811 ms 30208 KB Output is correct
10 Correct 1777 ms 30152 KB Output is correct
11 Correct 1989 ms 30152 KB Output is correct
12 Correct 2074 ms 30352 KB Output is correct
13 Correct 2253 ms 30248 KB Output is correct
14 Correct 2288 ms 30232 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 354 ms 27280 KB Output is correct
2 Correct 463 ms 30188 KB Output is correct
3 Correct 560 ms 30188 KB Output is correct
4 Correct 672 ms 30252 KB Output is correct
5 Correct 518 ms 30436 KB Output is correct
6 Correct 553 ms 30144 KB Output is correct
7 Correct 353 ms 30160 KB Output is correct
8 Correct 469 ms 30156 KB Output is correct
9 Correct 356 ms 30240 KB Output is correct
10 Correct 466 ms 30080 KB Output is correct
11 Correct 551 ms 30348 KB Output is correct
12 Correct 555 ms 30252 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 336 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 368 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 340 KB Output is correct
21 Correct 0 ms 340 KB Output is correct
22 Correct 0 ms 340 KB Output is correct
23 Correct 0 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 0 ms 340 KB Output is correct
26 Correct 0 ms 340 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 2 ms 324 KB Output is correct
31 Correct 1 ms 324 KB Output is correct
32 Correct 1 ms 340 KB Output is correct
33 Correct 1 ms 340 KB Output is correct
34 Correct 1 ms 340 KB Output is correct
35 Correct 1 ms 340 KB Output is correct
36 Correct 1 ms 340 KB Output is correct
37 Correct 2 ms 340 KB Output is correct
38 Correct 1 ms 332 KB Output is correct
39 Correct 1 ms 336 KB Output is correct
40 Correct 1 ms 340 KB Output is correct
41 Correct 26 ms 972 KB Output is correct
42 Correct 25 ms 960 KB Output is correct
43 Correct 24 ms 876 KB Output is correct
44 Correct 22 ms 852 KB Output is correct
45 Correct 26 ms 912 KB Output is correct
46 Correct 8 ms 980 KB Output is correct
47 Correct 24 ms 940 KB Output is correct
48 Correct 25 ms 956 KB Output is correct
49 Correct 26 ms 964 KB Output is correct
50 Correct 25 ms 988 KB Output is correct
51 Correct 24 ms 976 KB Output is correct
52 Correct 25 ms 980 KB Output is correct
53 Correct 23 ms 996 KB Output is correct
54 Correct 24 ms 980 KB Output is correct
55 Correct 29 ms 1024 KB Output is correct
56 Correct 26 ms 916 KB Output is correct
57 Correct 26 ms 880 KB Output is correct
58 Correct 8 ms 980 KB Output is correct
59 Correct 7 ms 964 KB Output is correct
60 Correct 24 ms 880 KB Output is correct
61 Correct 24 ms 872 KB Output is correct
62 Correct 1858 ms 27328 KB Output is correct
63 Correct 1834 ms 30380 KB Output is correct
64 Correct 2100 ms 30332 KB Output is correct
65 Correct 2218 ms 30216 KB Output is correct
66 Correct 2081 ms 30248 KB Output is correct
67 Correct 2330 ms 30196 KB Output is correct
68 Correct 1864 ms 30148 KB Output is correct
69 Correct 1755 ms 30132 KB Output is correct
70 Correct 1811 ms 30208 KB Output is correct
71 Correct 1777 ms 30152 KB Output is correct
72 Correct 1989 ms 30152 KB Output is correct
73 Correct 2074 ms 30352 KB Output is correct
74 Correct 2253 ms 30248 KB Output is correct
75 Correct 2288 ms 30232 KB Output is correct
76 Correct 354 ms 27280 KB Output is correct
77 Correct 463 ms 30188 KB Output is correct
78 Correct 560 ms 30188 KB Output is correct
79 Correct 672 ms 30252 KB Output is correct
80 Correct 518 ms 30436 KB Output is correct
81 Correct 553 ms 30144 KB Output is correct
82 Correct 353 ms 30160 KB Output is correct
83 Correct 469 ms 30156 KB Output is correct
84 Correct 356 ms 30240 KB Output is correct
85 Correct 466 ms 30080 KB Output is correct
86 Correct 551 ms 30348 KB Output is correct
87 Correct 555 ms 30252 KB Output is correct
88 Correct 2261 ms 33112 KB Output is correct
89 Correct 2396 ms 33176 KB Output is correct
90 Correct 2335 ms 33112 KB Output is correct
91 Correct 2501 ms 33144 KB Output is correct
92 Correct 2142 ms 33224 KB Output is correct
93 Correct 2350 ms 33132 KB Output is correct
94 Correct 1103 ms 33276 KB Output is correct
95 Correct 2113 ms 33112 KB Output is correct
96 Correct 2342 ms 33100 KB Output is correct
97 Correct 2471 ms 33140 KB Output is correct
98 Correct 2519 ms 33128 KB Output is correct
99 Correct 2452 ms 33064 KB Output is correct
100 Correct 2423 ms 33160 KB Output is correct
101 Correct 1959 ms 33068 KB Output is correct
102 Correct 1974 ms 33084 KB Output is correct
103 Correct 1970 ms 33032 KB Output is correct
104 Correct 2085 ms 33080 KB Output is correct
105 Correct 2033 ms 33140 KB Output is correct
106 Correct 2001 ms 33092 KB Output is correct
107 Correct 2251 ms 33196 KB Output is correct
108 Correct 2413 ms 33144 KB Output is correct
109 Correct 2186 ms 33172 KB Output is correct
110 Correct 2308 ms 33188 KB Output is correct
111 Correct 2462 ms 33096 KB Output is correct
112 Correct 2102 ms 33088 KB Output is correct
113 Correct 2352 ms 33100 KB Output is correct
114 Correct 2438 ms 33068 KB Output is correct
115 Correct 428 ms 33168 KB Output is correct
116 Correct 424 ms 33088 KB Output is correct
117 Correct 1154 ms 33136 KB Output is correct
118 Correct 1169 ms 33136 KB Output is correct
119 Correct 2114 ms 33168 KB Output is correct
120 Correct 2127 ms 33120 KB Output is correct