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

490088 | 2021-11-25T13:54:01 Z | fcmalkcin | Financial Report (JOI21_financial) | C++17 | 1864 ms | 43516 KB |

/*#pragma GCC optimize("Ofast") #pragma GCC optimization("unroll-loops, no-stack-protector") #pragma GCC target("avx,avx2,fma") */ #include <bits/stdc++.h> using namespace std; #define ll long long #define pll pair<ll,ll> #define ff first #define ss second #define pb push_back #define endl "\n" mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count()); const ll maxn=3e5+50; const ll mod=1e9+7 ; const ll base=2e18; /// you will be the best but now you just are trash /// goal 1/7 ll a[maxn]; struct stmx { ll st[4*maxn]; stmx() { memset(st,0,sizeof(st)); } ll get(ll id,ll left,ll right,ll x,ll y) { if (left>y||right<x) return 0; if (x<=left&&right<=y) { return st[id]; } ll mid =(left+right)/2; return max(get(id*2,left,mid,x,y),get(id*2+1,mid+1,right,x,y)); } void update(ll id,ll left,ll right, ll pos,ll diff) { if (pos<left||pos>right) return ; if (left==right) { st[id]=diff; return; } ll mid =(left+right)/2; update(id*2,left,mid,pos,diff); update(id*2+1,mid+1,right,pos,diff); st[id]=max(st[id*2],st[id*2+1]); } }man,man1; set<ll> st; ll n; void add(ll x) { auto it=st.lower_bound(x); if (it!=st.end()) { ll h=(*it); man.update(1,1,n,x,h-x); } if (it!=st.begin()) { it--; ll h=(*it); man.update(1,1,n,h,x-h); } st.insert(x); } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); if (fopen("t.inp", "r")) { freopen("test.inp", "r", stdin); freopen("test.out", "w", stdout); } ll d; cin>> n>> d; vector<pll> vt; for (int i=1;i<=n;i++) { cin>>a[i]; vt.pb(make_pair(a[i],-i)); } sort(vt.begin(),vt.end()); ll ans=0; for (auto p:vt) { ll pos=p.ss; pos=-pos; add(pos); ll l=1,h=pos-1; while (l<=h) { ll mid=(l+h)/2; if (man.get(1,1,n,mid,pos-1)<=d) h=mid-1; else l=mid+1; } ll nw=man1.get(1,1,n,l,pos-1)+1; // cout <<nw<<" "<<l<<" "<<pos<<endl; ans=max(ans,nw); man1.update(1,1,n,pos,nw); } cout <<ans<<endl; }

### Compilation message

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

1 | Correct | 8 ms | 19020 KB | Output is correct |

2 | Correct | 8 ms | 19068 KB | Output is correct |

3 | Correct | 8 ms | 19088 KB | Output is correct |

4 | Correct | 8 ms | 19020 KB | Output is correct |

5 | Correct | 8 ms | 19020 KB | Output is correct |

6 | Correct | 9 ms | 19020 KB | Output is correct |

7 | Correct | 8 ms | 19020 KB | Output is correct |

8 | Correct | 9 ms | 19116 KB | Output is correct |

9 | Correct | 7 ms | 19020 KB | Output is correct |

10 | Correct | 9 ms | 19068 KB | Output is correct |

11 | Correct | 7 ms | 19088 KB | Output is correct |

12 | Correct | 8 ms | 19020 KB | Output is correct |

13 | Correct | 8 ms | 19020 KB | Output is correct |

14 | Correct | 9 ms | 19020 KB | Output is correct |

15 | Correct | 8 ms | 19016 KB | Output is correct |

16 | Correct | 8 ms | 19036 KB | Output is correct |

17 | Correct | 8 ms | 19108 KB | Output is correct |

18 | Correct | 8 ms | 19116 KB | Output is correct |

19 | Correct | 8 ms | 19156 KB | Output is correct |

20 | Correct | 8 ms | 19068 KB | Output is correct |

21 | Correct | 8 ms | 19020 KB | Output is correct |

22 | Correct | 8 ms | 19020 KB | Output is correct |

23 | Correct | 7 ms | 19016 KB | Output is correct |

24 | Correct | 8 ms | 19020 KB | Output is correct |

25 | Correct | 7 ms | 19020 KB | Output is correct |

26 | Correct | 7 ms | 19124 KB | Output is correct |

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

1 | Correct | 8 ms | 19020 KB | Output is correct |

2 | Correct | 8 ms | 19068 KB | Output is correct |

3 | Correct | 8 ms | 19088 KB | Output is correct |

4 | Correct | 8 ms | 19020 KB | Output is correct |

5 | Correct | 8 ms | 19020 KB | Output is correct |

6 | Correct | 9 ms | 19020 KB | Output is correct |

7 | Correct | 8 ms | 19020 KB | Output is correct |

8 | Correct | 9 ms | 19116 KB | Output is correct |

9 | Correct | 7 ms | 19020 KB | Output is correct |

10 | Correct | 9 ms | 19068 KB | Output is correct |

11 | Correct | 7 ms | 19088 KB | Output is correct |

12 | Correct | 8 ms | 19020 KB | Output is correct |

13 | Correct | 8 ms | 19020 KB | Output is correct |

14 | Correct | 9 ms | 19020 KB | Output is correct |

15 | Correct | 8 ms | 19016 KB | Output is correct |

16 | Correct | 8 ms | 19036 KB | Output is correct |

17 | Correct | 8 ms | 19108 KB | Output is correct |

18 | Correct | 8 ms | 19116 KB | Output is correct |

19 | Correct | 8 ms | 19156 KB | Output is correct |

20 | Correct | 8 ms | 19068 KB | Output is correct |

21 | Correct | 8 ms | 19020 KB | Output is correct |

22 | Correct | 8 ms | 19020 KB | Output is correct |

23 | Correct | 7 ms | 19016 KB | Output is correct |

24 | Correct | 8 ms | 19020 KB | Output is correct |

25 | Correct | 7 ms | 19020 KB | Output is correct |

26 | Correct | 7 ms | 19124 KB | Output is correct |

27 | Correct | 8 ms | 19120 KB | Output is correct |

28 | Correct | 9 ms | 19148 KB | Output is correct |

29 | Correct | 9 ms | 19092 KB | Output is correct |

30 | Correct | 9 ms | 19148 KB | Output is correct |

31 | Correct | 9 ms | 19120 KB | Output is correct |

32 | Correct | 8 ms | 19148 KB | Output is correct |

33 | Correct | 8 ms | 19148 KB | Output is correct |

34 | Correct | 8 ms | 19116 KB | Output is correct |

35 | Correct | 9 ms | 19036 KB | Output is correct |

36 | Correct | 8 ms | 19116 KB | Output is correct |

37 | Correct | 9 ms | 19148 KB | Output is correct |

38 | Correct | 8 ms | 19096 KB | Output is correct |

39 | Correct | 11 ms | 19124 KB | Output is correct |

40 | Correct | 9 ms | 19148 KB | Output is correct |

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

1 | Correct | 8 ms | 19020 KB | Output is correct |

2 | Correct | 8 ms | 19068 KB | Output is correct |

3 | Correct | 8 ms | 19088 KB | Output is correct |

4 | Correct | 8 ms | 19020 KB | Output is correct |

5 | Correct | 8 ms | 19020 KB | Output is correct |

6 | Correct | 9 ms | 19020 KB | Output is correct |

7 | Correct | 8 ms | 19020 KB | Output is correct |

8 | Correct | 9 ms | 19116 KB | Output is correct |

9 | Correct | 7 ms | 19020 KB | Output is correct |

10 | Correct | 9 ms | 19068 KB | Output is correct |

11 | Correct | 7 ms | 19088 KB | Output is correct |

12 | Correct | 8 ms | 19020 KB | Output is correct |

13 | Correct | 8 ms | 19020 KB | Output is correct |

14 | Correct | 9 ms | 19020 KB | Output is correct |

15 | Correct | 8 ms | 19016 KB | Output is correct |

16 | Correct | 8 ms | 19036 KB | Output is correct |

17 | Correct | 8 ms | 19108 KB | Output is correct |

18 | Correct | 8 ms | 19116 KB | Output is correct |

19 | Correct | 8 ms | 19156 KB | Output is correct |

20 | Correct | 8 ms | 19068 KB | Output is correct |

21 | Correct | 8 ms | 19020 KB | Output is correct |

22 | Correct | 8 ms | 19020 KB | Output is correct |

23 | Correct | 7 ms | 19016 KB | Output is correct |

24 | Correct | 8 ms | 19020 KB | Output is correct |

25 | Correct | 7 ms | 19020 KB | Output is correct |

26 | Correct | 7 ms | 19124 KB | Output is correct |

27 | Correct | 8 ms | 19120 KB | Output is correct |

28 | Correct | 9 ms | 19148 KB | Output is correct |

29 | Correct | 9 ms | 19092 KB | Output is correct |

30 | Correct | 9 ms | 19148 KB | Output is correct |

31 | Correct | 9 ms | 19120 KB | Output is correct |

32 | Correct | 8 ms | 19148 KB | Output is correct |

33 | Correct | 8 ms | 19148 KB | Output is correct |

34 | Correct | 8 ms | 19116 KB | Output is correct |

35 | Correct | 9 ms | 19036 KB | Output is correct |

36 | Correct | 8 ms | 19116 KB | Output is correct |

37 | Correct | 9 ms | 19148 KB | Output is correct |

38 | Correct | 8 ms | 19096 KB | Output is correct |

39 | Correct | 11 ms | 19124 KB | Output is correct |

40 | Correct | 9 ms | 19148 KB | Output is correct |

41 | Correct | 26 ms | 19652 KB | Output is correct |

42 | Correct | 26 ms | 19592 KB | Output is correct |

43 | Correct | 25 ms | 19576 KB | Output is correct |

44 | Correct | 23 ms | 19604 KB | Output is correct |

45 | Correct | 24 ms | 19600 KB | Output is correct |

46 | Correct | 25 ms | 19616 KB | Output is correct |

47 | Correct | 23 ms | 19600 KB | Output is correct |

48 | Correct | 26 ms | 19652 KB | Output is correct |

49 | Correct | 26 ms | 19612 KB | Output is correct |

50 | Correct | 26 ms | 19652 KB | Output is correct |

51 | Correct | 23 ms | 19660 KB | Output is correct |

52 | Correct | 26 ms | 19588 KB | Output is correct |

53 | Correct | 20 ms | 19660 KB | Output is correct |

54 | Correct | 22 ms | 19660 KB | Output is correct |

55 | Correct | 27 ms | 19660 KB | Output is correct |

56 | Correct | 26 ms | 19596 KB | Output is correct |

57 | Correct | 24 ms | 19680 KB | Output is correct |

58 | Correct | 20 ms | 19676 KB | Output is correct |

59 | Correct | 20 ms | 19676 KB | Output is correct |

60 | Correct | 24 ms | 19640 KB | Output is correct |

61 | Correct | 22 ms | 19616 KB | Output is correct |

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

1 | Correct | 961 ms | 43180 KB | Output is correct |

2 | Correct | 1123 ms | 42684 KB | Output is correct |

3 | Correct | 1496 ms | 43280 KB | Output is correct |

4 | Correct | 1838 ms | 43092 KB | Output is correct |

5 | Correct | 1448 ms | 43240 KB | Output is correct |

6 | Correct | 1790 ms | 43308 KB | Output is correct |

7 | Correct | 928 ms | 43068 KB | Output is correct |

8 | Correct | 927 ms | 43128 KB | Output is correct |

9 | Correct | 975 ms | 43100 KB | Output is correct |

10 | Correct | 983 ms | 43212 KB | Output is correct |

11 | Correct | 1321 ms | 43112 KB | Output is correct |

12 | Correct | 1511 ms | 43132 KB | Output is correct |

13 | Correct | 1648 ms | 43256 KB | Output is correct |

14 | Correct | 1864 ms | 43256 KB | Output is correct |

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

1 | Correct | 942 ms | 43516 KB | Output is correct |

2 | Correct | 1263 ms | 43120 KB | Output is correct |

3 | Correct | 1527 ms | 43104 KB | Output is correct |

4 | Correct | 1575 ms | 43124 KB | Output is correct |

5 | Correct | 1403 ms | 43096 KB | Output is correct |

6 | Correct | 1606 ms | 43156 KB | Output is correct |

7 | Correct | 941 ms | 43108 KB | Output is correct |

8 | Correct | 931 ms | 43080 KB | Output is correct |

9 | Correct | 948 ms | 43080 KB | Output is correct |

10 | Correct | 1239 ms | 43208 KB | Output is correct |

11 | Correct | 1598 ms | 43120 KB | Output is correct |

12 | Correct | 1457 ms | 43144 KB | Output is correct |

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

1 | Correct | 8 ms | 19020 KB | Output is correct |

2 | Correct | 8 ms | 19068 KB | Output is correct |

3 | Correct | 8 ms | 19088 KB | Output is correct |

4 | Correct | 8 ms | 19020 KB | Output is correct |

5 | Correct | 8 ms | 19020 KB | Output is correct |

6 | Correct | 9 ms | 19020 KB | Output is correct |

7 | Correct | 8 ms | 19020 KB | Output is correct |

8 | Correct | 9 ms | 19116 KB | Output is correct |

9 | Correct | 7 ms | 19020 KB | Output is correct |

10 | Correct | 9 ms | 19068 KB | Output is correct |

11 | Correct | 7 ms | 19088 KB | Output is correct |

12 | Correct | 8 ms | 19020 KB | Output is correct |

13 | Correct | 8 ms | 19020 KB | Output is correct |

14 | Correct | 9 ms | 19020 KB | Output is correct |

15 | Correct | 8 ms | 19016 KB | Output is correct |

16 | Correct | 8 ms | 19036 KB | Output is correct |

17 | Correct | 8 ms | 19108 KB | Output is correct |

18 | Correct | 8 ms | 19116 KB | Output is correct |

19 | Correct | 8 ms | 19156 KB | Output is correct |

20 | Correct | 8 ms | 19068 KB | Output is correct |

21 | Correct | 8 ms | 19020 KB | Output is correct |

22 | Correct | 8 ms | 19020 KB | Output is correct |

23 | Correct | 7 ms | 19016 KB | Output is correct |

24 | Correct | 8 ms | 19020 KB | Output is correct |

25 | Correct | 7 ms | 19020 KB | Output is correct |

26 | Correct | 7 ms | 19124 KB | Output is correct |

27 | Correct | 8 ms | 19120 KB | Output is correct |

28 | Correct | 9 ms | 19148 KB | Output is correct |

29 | Correct | 9 ms | 19092 KB | Output is correct |

30 | Correct | 9 ms | 19148 KB | Output is correct |

31 | Correct | 9 ms | 19120 KB | Output is correct |

32 | Correct | 8 ms | 19148 KB | Output is correct |

33 | Correct | 8 ms | 19148 KB | Output is correct |

34 | Correct | 8 ms | 19116 KB | Output is correct |

35 | Correct | 9 ms | 19036 KB | Output is correct |

36 | Correct | 8 ms | 19116 KB | Output is correct |

37 | Correct | 9 ms | 19148 KB | Output is correct |

38 | Correct | 8 ms | 19096 KB | Output is correct |

39 | Correct | 11 ms | 19124 KB | Output is correct |

40 | Correct | 9 ms | 19148 KB | Output is correct |

41 | Correct | 26 ms | 19652 KB | Output is correct |

42 | Correct | 26 ms | 19592 KB | Output is correct |

43 | Correct | 25 ms | 19576 KB | Output is correct |

44 | Correct | 23 ms | 19604 KB | Output is correct |

45 | Correct | 24 ms | 19600 KB | Output is correct |

46 | Correct | 25 ms | 19616 KB | Output is correct |

47 | Correct | 23 ms | 19600 KB | Output is correct |

48 | Correct | 26 ms | 19652 KB | Output is correct |

49 | Correct | 26 ms | 19612 KB | Output is correct |

50 | Correct | 26 ms | 19652 KB | Output is correct |

51 | Correct | 23 ms | 19660 KB | Output is correct |

52 | Correct | 26 ms | 19588 KB | Output is correct |

53 | Correct | 20 ms | 19660 KB | Output is correct |

54 | Correct | 22 ms | 19660 KB | Output is correct |

55 | Correct | 27 ms | 19660 KB | Output is correct |

56 | Correct | 26 ms | 19596 KB | Output is correct |

57 | Correct | 24 ms | 19680 KB | Output is correct |

58 | Correct | 20 ms | 19676 KB | Output is correct |

59 | Correct | 20 ms | 19676 KB | Output is correct |

60 | Correct | 24 ms | 19640 KB | Output is correct |

61 | Correct | 22 ms | 19616 KB | Output is correct |

62 | Correct | 961 ms | 43180 KB | Output is correct |

63 | Correct | 1123 ms | 42684 KB | Output is correct |

64 | Correct | 1496 ms | 43280 KB | Output is correct |

65 | Correct | 1838 ms | 43092 KB | Output is correct |

66 | Correct | 1448 ms | 43240 KB | Output is correct |

67 | Correct | 1790 ms | 43308 KB | Output is correct |

68 | Correct | 928 ms | 43068 KB | Output is correct |

69 | Correct | 927 ms | 43128 KB | Output is correct |

70 | Correct | 975 ms | 43100 KB | Output is correct |

71 | Correct | 983 ms | 43212 KB | Output is correct |

72 | Correct | 1321 ms | 43112 KB | Output is correct |

73 | Correct | 1511 ms | 43132 KB | Output is correct |

74 | Correct | 1648 ms | 43256 KB | Output is correct |

75 | Correct | 1864 ms | 43256 KB | Output is correct |

76 | Correct | 942 ms | 43516 KB | Output is correct |

77 | Correct | 1263 ms | 43120 KB | Output is correct |

78 | Correct | 1527 ms | 43104 KB | Output is correct |

79 | Correct | 1575 ms | 43124 KB | Output is correct |

80 | Correct | 1403 ms | 43096 KB | Output is correct |

81 | Correct | 1606 ms | 43156 KB | Output is correct |

82 | Correct | 941 ms | 43108 KB | Output is correct |

83 | Correct | 931 ms | 43080 KB | Output is correct |

84 | Correct | 948 ms | 43080 KB | Output is correct |

85 | Correct | 1239 ms | 43208 KB | Output is correct |

86 | Correct | 1598 ms | 43120 KB | Output is correct |

87 | Correct | 1457 ms | 43144 KB | Output is correct |

88 | Correct | 1721 ms | 43116 KB | Output is correct |

89 | Correct | 1803 ms | 43164 KB | Output is correct |

90 | Correct | 1758 ms | 43164 KB | Output is correct |

91 | Correct | 1638 ms | 43040 KB | Output is correct |

92 | Correct | 1219 ms | 43156 KB | Output is correct |

93 | Correct | 1534 ms | 43176 KB | Output is correct |

94 | Correct | 1604 ms | 43072 KB | Output is correct |

95 | Correct | 1570 ms | 43140 KB | Output is correct |

96 | Correct | 1688 ms | 43044 KB | Output is correct |

97 | Correct | 1713 ms | 43212 KB | Output is correct |

98 | Correct | 1618 ms | 43140 KB | Output is correct |

99 | Correct | 1644 ms | 43120 KB | Output is correct |

100 | Correct | 1627 ms | 43388 KB | Output is correct |

101 | Correct | 982 ms | 43092 KB | Output is correct |

102 | Correct | 1024 ms | 43144 KB | Output is correct |

103 | Correct | 1074 ms | 43132 KB | Output is correct |

104 | Correct | 1164 ms | 43140 KB | Output is correct |

105 | Correct | 1365 ms | 43152 KB | Output is correct |

106 | Correct | 1249 ms | 43124 KB | Output is correct |

107 | Correct | 1404 ms | 43200 KB | Output is correct |

108 | Correct | 1589 ms | 43172 KB | Output is correct |

109 | Correct | 1474 ms | 43084 KB | Output is correct |

110 | Correct | 1679 ms | 43212 KB | Output is correct |

111 | Correct | 1708 ms | 43168 KB | Output is correct |

112 | Correct | 1320 ms | 43132 KB | Output is correct |

113 | Correct | 1643 ms | 43152 KB | Output is correct |

114 | Correct | 1652 ms | 43052 KB | Output is correct |

115 | Correct | 963 ms | 43144 KB | Output is correct |

116 | Correct | 966 ms | 43136 KB | Output is correct |

117 | Correct | 1010 ms | 43064 KB | Output is correct |

118 | Correct | 1037 ms | 43076 KB | Output is correct |

119 | Correct | 1288 ms | 43072 KB | Output is correct |

120 | Correct | 1262 ms | 43080 KB | Output is correct |