# | Submission time^{} |
Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|

1084152 | 2024-09-05T11:48:05 Z | yoav_s | Financial Report (JOI21_financial) | C++17 | 428 ms | 102996 KB |

#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll,ll> p; typedef pair<ll, p> tri; typedef vector<ll> v; typedef vector<v> vv; typedef vector<p> vp; typedef vector<tri> vtri; typedef vector<vtri> vvtri; typedef vector<vvtri> vvvtri; typedef vector<vv> vvv; typedef vector<bool> vb; typedef vector<vb> vvb; typedef vector<vvb> vvvb; typedef vector<p> vp; typedef vector<vp> vvp; typedef vector<vvp> vvvp; typedef vector<vvvp> vvvvp; #define double long double typedef vector<double> vd; typedef vector<vd> vvd; typedef vector<vvd> vvvd; const ll mod = 1e9 + 7; const ll INF = 1e18; #define f first #define s second #define pb push_back #define eb emplace_back #define loop(a) for (ll i = 0; i < a; i++) #define setmin(a, b) a = min(a, b) #define setmax(a, b) a = max(a, b) #define all(v) v.begin(), v.end() void update(v &st, ll i, ll val) { ll n = st.size() / 2; i += n; st[i] = val; i /= 2; while (i > 0) { st[i] = min(st[2 * i], st[2 * i + 1]); i /= 2; } } ll query(v &st, ll l, ll r) { ll n= st.size() / 2; l += n; r += n; ll res = INF; while (l <= r) { if (l % 2 == 1) { res = min(res, st[l]); l++; } if (r % 2 == 0) { res = min(res, st[r]); r--; } l /= 2; r /= 2; } return res; } ll lastSmaller(v &st, ll x) { ll i = 1; ll n = st.size() / 2; if (st[1] >= x) return -1; while (i < n) { if (st[2 * i + 1] < x) i = 2 * i + 1; else i *= 2; } return i - n; } int main() { ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); ll N, D; cin >> N >> D; v A(N); for (ll i =0; i < N; i++) cin >> A[i]; multiset<ll> vals; v mini(N, -1); for (ll i = 0; i < N; i++) { vals.insert(A[i]); if (i >= D) vals.erase(vals.find(A[i - D])); mini[i] = *vals.begin(); } v expire(N, -1); multiset<p> curVals; for (ll i = 0; i < N; i++) { curVals.emplace(A[i], i); while ((*curVals.begin()).f < mini[i]) { expire[(*curVals.begin()).s] = i; curVals.erase(curVals.begin()); } } vv expiringIn(N); for (ll i =0; i < N; i++) if (expire[i] != -1) expiringIn[expire[i]].pb(i); ll n = pow(2, ceil(log2(N + 1))); v st(2 * n, INF); update(st, 0, -INF); vector<multiset<ll>> endings(N + 1); endings[0].insert(-INF); for (ll i = 1; i <= N; i++) endings[i].insert(INF); v res(N, -1); ll best = 0; for (ll i = 0; i < N; i++) { ll add = lastSmaller(st, A[i]); if (add != -1) { endings[add + 1].insert(A[i]); best = max(best, add + 1); update(st, add + 1, *endings[add + 1].begin()); res[i] = add + 1; } for (ll x : expiringIn[i]) { if (res[x] == -1) continue; endings[res[x]].erase(endings[res[x]].find(A[x])); update(st, res[x], *endings[res[x]].begin()); } } cout << best << "\n"; return 0; }

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 0 ms | 344 KB | Output is correct |

2 | Correct | 0 ms | 344 KB | Output is correct |

3 | Correct | 0 ms | 348 KB | Output is correct |

4 | Correct | 0 ms | 348 KB | Output is correct |

5 | Correct | 0 ms | 348 KB | Output is correct |

6 | Correct | 0 ms | 348 KB | Output is correct |

7 | Correct | 0 ms | 348 KB | Output is correct |

8 | Correct | 0 ms | 348 KB | Output is correct |

9 | Correct | 0 ms | 348 KB | Output is correct |

10 | Correct | 0 ms | 348 KB | Output is correct |

11 | Correct | 0 ms | 604 KB | Output is correct |

12 | Correct | 0 ms | 348 KB | Output is correct |

13 | Correct | 0 ms | 348 KB | Output is correct |

14 | Correct | 0 ms | 348 KB | Output is correct |

15 | Correct | 0 ms | 348 KB | Output is correct |

16 | Correct | 0 ms | 344 KB | Output is correct |

17 | Correct | 0 ms | 348 KB | Output is correct |

18 | Correct | 0 ms | 348 KB | Output is correct |

19 | Correct | 0 ms | 348 KB | Output is correct |

20 | Correct | 0 ms | 348 KB | Output is correct |

21 | Correct | 0 ms | 348 KB | Output is correct |

22 | Correct | 0 ms | 348 KB | Output is correct |

23 | Correct | 0 ms | 344 KB | Output is correct |

24 | Correct | 0 ms | 348 KB | Output is correct |

25 | Correct | 0 ms | 348 KB | Output is correct |

26 | Correct | 0 ms | 348 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 0 ms | 344 KB | Output is correct |

2 | Correct | 0 ms | 344 KB | Output is correct |

3 | Correct | 0 ms | 348 KB | Output is correct |

4 | Correct | 0 ms | 348 KB | Output is correct |

5 | Correct | 0 ms | 348 KB | Output is correct |

6 | Correct | 0 ms | 348 KB | Output is correct |

7 | Correct | 0 ms | 348 KB | Output is correct |

8 | Correct | 0 ms | 348 KB | Output is correct |

9 | Correct | 0 ms | 348 KB | Output is correct |

10 | Correct | 0 ms | 348 KB | Output is correct |

11 | Correct | 0 ms | 604 KB | Output is correct |

12 | Correct | 0 ms | 348 KB | Output is correct |

13 | Correct | 0 ms | 348 KB | Output is correct |

14 | Correct | 0 ms | 348 KB | Output is correct |

15 | Correct | 0 ms | 348 KB | Output is correct |

16 | Correct | 0 ms | 344 KB | Output is correct |

17 | Correct | 0 ms | 348 KB | Output is correct |

18 | Correct | 0 ms | 348 KB | Output is correct |

19 | Correct | 0 ms | 348 KB | Output is correct |

20 | Correct | 0 ms | 348 KB | Output is correct |

21 | Correct | 0 ms | 348 KB | Output is correct |

22 | Correct | 0 ms | 348 KB | Output is correct |

23 | Correct | 0 ms | 344 KB | Output is correct |

24 | Correct | 0 ms | 348 KB | Output is correct |

25 | Correct | 0 ms | 348 KB | Output is correct |

26 | Correct | 0 ms | 348 KB | Output is correct |

27 | Correct | 1 ms | 348 KB | Output is correct |

28 | Correct | 1 ms | 344 KB | Output is correct |

29 | Correct | 1 ms | 348 KB | Output is correct |

30 | Correct | 1 ms | 348 KB | Output is correct |

31 | Correct | 0 ms | 352 KB | Output is correct |

32 | Correct | 1 ms | 352 KB | Output is correct |

33 | Correct | 1 ms | 352 KB | Output is correct |

34 | Correct | 1 ms | 360 KB | Output is correct |

35 | Correct | 1 ms | 352 KB | Output is correct |

36 | Correct | 1 ms | 348 KB | Output is correct |

37 | Correct | 1 ms | 356 KB | Output is correct |

38 | Correct | 0 ms | 348 KB | Output is correct |

39 | Correct | 1 ms | 356 KB | Output is correct |

40 | Correct | 0 ms | 348 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 0 ms | 344 KB | Output is correct |

2 | Correct | 0 ms | 344 KB | Output is correct |

3 | Correct | 0 ms | 348 KB | Output is correct |

4 | Correct | 0 ms | 348 KB | Output is correct |

5 | Correct | 0 ms | 348 KB | Output is correct |

6 | Correct | 0 ms | 348 KB | Output is correct |

7 | Correct | 0 ms | 348 KB | Output is correct |

8 | Correct | 0 ms | 348 KB | Output is correct |

9 | Correct | 0 ms | 348 KB | Output is correct |

10 | Correct | 0 ms | 348 KB | Output is correct |

11 | Correct | 0 ms | 604 KB | Output is correct |

12 | Correct | 0 ms | 348 KB | Output is correct |

13 | Correct | 0 ms | 348 KB | Output is correct |

14 | Correct | 0 ms | 348 KB | Output is correct |

15 | Correct | 0 ms | 348 KB | Output is correct |

16 | Correct | 0 ms | 344 KB | Output is correct |

17 | Correct | 0 ms | 348 KB | Output is correct |

18 | Correct | 0 ms | 348 KB | Output is correct |

19 | Correct | 0 ms | 348 KB | Output is correct |

20 | Correct | 0 ms | 348 KB | Output is correct |

21 | Correct | 0 ms | 348 KB | Output is correct |

22 | Correct | 0 ms | 348 KB | Output is correct |

23 | Correct | 0 ms | 344 KB | Output is correct |

24 | Correct | 0 ms | 348 KB | Output is correct |

25 | Correct | 0 ms | 348 KB | Output is correct |

26 | Correct | 0 ms | 348 KB | Output is correct |

27 | Correct | 1 ms | 348 KB | Output is correct |

28 | Correct | 1 ms | 344 KB | Output is correct |

29 | Correct | 1 ms | 348 KB | Output is correct |

30 | Correct | 1 ms | 348 KB | Output is correct |

31 | Correct | 0 ms | 352 KB | Output is correct |

32 | Correct | 1 ms | 352 KB | Output is correct |

33 | Correct | 1 ms | 352 KB | Output is correct |

34 | Correct | 1 ms | 360 KB | Output is correct |

35 | Correct | 1 ms | 352 KB | Output is correct |

36 | Correct | 1 ms | 348 KB | Output is correct |

37 | Correct | 1 ms | 356 KB | Output is correct |

38 | Correct | 0 ms | 348 KB | Output is correct |

39 | Correct | 1 ms | 356 KB | Output is correct |

40 | Correct | 0 ms | 348 KB | Output is correct |

41 | Correct | 3 ms | 1636 KB | Output is correct |

42 | Correct | 3 ms | 1628 KB | Output is correct |

43 | Correct | 4 ms | 1892 KB | Output is correct |

44 | Correct | 4 ms | 1884 KB | Output is correct |

45 | Correct | 5 ms | 2256 KB | Output is correct |

46 | Correct | 5 ms | 2652 KB | Output is correct |

47 | Correct | 3 ms | 1636 KB | Output is correct |

48 | Correct | 4 ms | 1952 KB | Output is correct |

49 | Correct | 5 ms | 1884 KB | Output is correct |

50 | Correct | 4 ms | 1884 KB | Output is correct |

51 | Correct | 3 ms | 1628 KB | Output is correct |

52 | Correct | 3 ms | 1628 KB | Output is correct |

53 | Correct | 3 ms | 1628 KB | Output is correct |

54 | Correct | 4 ms | 1628 KB | Output is correct |

55 | Correct | 6 ms | 2184 KB | Output is correct |

56 | Correct | 6 ms | 2396 KB | Output is correct |

57 | Correct | 4 ms | 2396 KB | Output is correct |

58 | Correct | 5 ms | 2812 KB | Output is correct |

59 | Correct | 5 ms | 2648 KB | Output is correct |

60 | Correct | 3 ms | 2208 KB | Output is correct |

61 | Correct | 3 ms | 2396 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 195 ms | 88568 KB | Output is correct |

2 | Correct | 174 ms | 64852 KB | Output is correct |

3 | Correct | 159 ms | 61524 KB | Output is correct |

4 | Correct | 145 ms | 61780 KB | Output is correct |

5 | Correct | 144 ms | 62544 KB | Output is correct |

6 | Correct | 155 ms | 61812 KB | Output is correct |

7 | Correct | 128 ms | 65104 KB | Output is correct |

8 | Correct | 200 ms | 88692 KB | Output is correct |

9 | Correct | 129 ms | 62944 KB | Output is correct |

10 | Correct | 181 ms | 75860 KB | Output is correct |

11 | Correct | 161 ms | 61776 KB | Output is correct |

12 | Correct | 149 ms | 61780 KB | Output is correct |

13 | Correct | 130 ms | 65360 KB | Output is correct |

14 | Correct | 147 ms | 58712 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 248 ms | 102996 KB | Output is correct |

2 | Correct | 326 ms | 102780 KB | Output is correct |

3 | Correct | 428 ms | 102560 KB | Output is correct |

4 | Correct | 372 ms | 102752 KB | Output is correct |

5 | Correct | 318 ms | 102672 KB | Output is correct |

6 | Correct | 362 ms | 102736 KB | Output is correct |

7 | Correct | 212 ms | 102676 KB | Output is correct |

8 | Correct | 268 ms | 102632 KB | Output is correct |

9 | Correct | 176 ms | 101968 KB | Output is correct |

10 | Correct | 279 ms | 102452 KB | Output is correct |

11 | Correct | 384 ms | 102740 KB | Output is correct |

12 | Correct | 262 ms | 102604 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 0 ms | 344 KB | Output is correct |

2 | Correct | 0 ms | 344 KB | Output is correct |

3 | Correct | 0 ms | 348 KB | Output is correct |

4 | Correct | 0 ms | 348 KB | Output is correct |

5 | Correct | 0 ms | 348 KB | Output is correct |

6 | Correct | 0 ms | 348 KB | Output is correct |

7 | Correct | 0 ms | 348 KB | Output is correct |

8 | Correct | 0 ms | 348 KB | Output is correct |

9 | Correct | 0 ms | 348 KB | Output is correct |

10 | Correct | 0 ms | 348 KB | Output is correct |

11 | Correct | 0 ms | 604 KB | Output is correct |

12 | Correct | 0 ms | 348 KB | Output is correct |

13 | Correct | 0 ms | 348 KB | Output is correct |

14 | Correct | 0 ms | 348 KB | Output is correct |

15 | Correct | 0 ms | 348 KB | Output is correct |

16 | Correct | 0 ms | 344 KB | Output is correct |

17 | Correct | 0 ms | 348 KB | Output is correct |

18 | Correct | 0 ms | 348 KB | Output is correct |

19 | Correct | 0 ms | 348 KB | Output is correct |

20 | Correct | 0 ms | 348 KB | Output is correct |

21 | Correct | 0 ms | 348 KB | Output is correct |

22 | Correct | 0 ms | 348 KB | Output is correct |

23 | Correct | 0 ms | 344 KB | Output is correct |

24 | Correct | 0 ms | 348 KB | Output is correct |

25 | Correct | 0 ms | 348 KB | Output is correct |

26 | Correct | 0 ms | 348 KB | Output is correct |

27 | Correct | 1 ms | 348 KB | Output is correct |

28 | Correct | 1 ms | 344 KB | Output is correct |

29 | Correct | 1 ms | 348 KB | Output is correct |

30 | Correct | 1 ms | 348 KB | Output is correct |

31 | Correct | 0 ms | 352 KB | Output is correct |

32 | Correct | 1 ms | 352 KB | Output is correct |

33 | Correct | 1 ms | 352 KB | Output is correct |

34 | Correct | 1 ms | 360 KB | Output is correct |

35 | Correct | 1 ms | 352 KB | Output is correct |

36 | Correct | 1 ms | 348 KB | Output is correct |

37 | Correct | 1 ms | 356 KB | Output is correct |

38 | Correct | 0 ms | 348 KB | Output is correct |

39 | Correct | 1 ms | 356 KB | Output is correct |

40 | Correct | 0 ms | 348 KB | Output is correct |

41 | Correct | 3 ms | 1636 KB | Output is correct |

42 | Correct | 3 ms | 1628 KB | Output is correct |

43 | Correct | 4 ms | 1892 KB | Output is correct |

44 | Correct | 4 ms | 1884 KB | Output is correct |

45 | Correct | 5 ms | 2256 KB | Output is correct |

46 | Correct | 5 ms | 2652 KB | Output is correct |

47 | Correct | 3 ms | 1636 KB | Output is correct |

48 | Correct | 4 ms | 1952 KB | Output is correct |

49 | Correct | 5 ms | 1884 KB | Output is correct |

50 | Correct | 4 ms | 1884 KB | Output is correct |

51 | Correct | 3 ms | 1628 KB | Output is correct |

52 | Correct | 3 ms | 1628 KB | Output is correct |

53 | Correct | 3 ms | 1628 KB | Output is correct |

54 | Correct | 4 ms | 1628 KB | Output is correct |

55 | Correct | 6 ms | 2184 KB | Output is correct |

56 | Correct | 6 ms | 2396 KB | Output is correct |

57 | Correct | 4 ms | 2396 KB | Output is correct |

58 | Correct | 5 ms | 2812 KB | Output is correct |

59 | Correct | 5 ms | 2648 KB | Output is correct |

60 | Correct | 3 ms | 2208 KB | Output is correct |

61 | Correct | 3 ms | 2396 KB | Output is correct |

62 | Correct | 195 ms | 88568 KB | Output is correct |

63 | Correct | 174 ms | 64852 KB | Output is correct |

64 | Correct | 159 ms | 61524 KB | Output is correct |

65 | Correct | 145 ms | 61780 KB | Output is correct |

66 | Correct | 144 ms | 62544 KB | Output is correct |

67 | Correct | 155 ms | 61812 KB | Output is correct |

68 | Correct | 128 ms | 65104 KB | Output is correct |

69 | Correct | 200 ms | 88692 KB | Output is correct |

70 | Correct | 129 ms | 62944 KB | Output is correct |

71 | Correct | 181 ms | 75860 KB | Output is correct |

72 | Correct | 161 ms | 61776 KB | Output is correct |

73 | Correct | 149 ms | 61780 KB | Output is correct |

74 | Correct | 130 ms | 65360 KB | Output is correct |

75 | Correct | 147 ms | 58712 KB | Output is correct |

76 | Correct | 248 ms | 102996 KB | Output is correct |

77 | Correct | 326 ms | 102780 KB | Output is correct |

78 | Correct | 428 ms | 102560 KB | Output is correct |

79 | Correct | 372 ms | 102752 KB | Output is correct |

80 | Correct | 318 ms | 102672 KB | Output is correct |

81 | Correct | 362 ms | 102736 KB | Output is correct |

82 | Correct | 212 ms | 102676 KB | Output is correct |

83 | Correct | 268 ms | 102632 KB | Output is correct |

84 | Correct | 176 ms | 101968 KB | Output is correct |

85 | Correct | 279 ms | 102452 KB | Output is correct |

86 | Correct | 384 ms | 102740 KB | Output is correct |

87 | Correct | 262 ms | 102604 KB | Output is correct |

88 | Correct | 166 ms | 61012 KB | Output is correct |

89 | Correct | 185 ms | 61012 KB | Output is correct |

90 | Correct | 238 ms | 67552 KB | Output is correct |

91 | Correct | 321 ms | 85604 KB | Output is correct |

92 | Correct | 273 ms | 88988 KB | Output is correct |

93 | Correct | 390 ms | 89472 KB | Output is correct |

94 | Correct | 413 ms | 98900 KB | Output is correct |

95 | Correct | 162 ms | 61420 KB | Output is correct |

96 | Correct | 217 ms | 63348 KB | Output is correct |

97 | Correct | 262 ms | 65400 KB | Output is correct |

98 | Correct | 286 ms | 85332 KB | Output is correct |

99 | Correct | 332 ms | 88652 KB | Output is correct |

100 | Correct | 316 ms | 88660 KB | Output is correct |

101 | Correct | 145 ms | 61524 KB | Output is correct |

102 | Correct | 173 ms | 59812 KB | Output is correct |

103 | Correct | 191 ms | 59476 KB | Output is correct |

104 | Correct | 231 ms | 60248 KB | Output is correct |

105 | Correct | 335 ms | 67992 KB | Output is correct |

106 | Correct | 234 ms | 87652 KB | Output is correct |

107 | Correct | 288 ms | 88912 KB | Output is correct |

108 | Correct | 333 ms | 89172 KB | Output is correct |

109 | Correct | 137 ms | 65616 KB | Output is correct |

110 | Correct | 250 ms | 79580 KB | Output is correct |

111 | Correct | 295 ms | 84560 KB | Output is correct |

112 | Correct | 186 ms | 84952 KB | Output is correct |

113 | Correct | 332 ms | 89176 KB | Output is correct |

114 | Correct | 300 ms | 89172 KB | Output is correct |

115 | Correct | 259 ms | 102980 KB | Output is correct |

116 | Correct | 250 ms | 102992 KB | Output is correct |

117 | Correct | 238 ms | 95984 KB | Output is correct |

118 | Correct | 227 ms | 96032 KB | Output is correct |

119 | Correct | 147 ms | 88656 KB | Output is correct |

120 | Correct | 152 ms | 88940 KB | Output is correct |