1
n,k = map(int,input().split())
2
a = list(map(int,input().split()))
3
ans = 0
4
cnt = 0
5
for i,x in enumerate(a):
6
    if x >= k:
7
        cnt += 1
8
    else:
9
        if cnt >= 1:
10
            ans += 1
11
            cnt = 0
12
        else:
13
            continue
14
if cnt >= 1:
15
    ans += 1
16
print(ans)

1
n,m = map(int,input().split())
2
r = [0]*(n+1)
3
t = [0]*(n+1)
4
for i in range(1,n+1):
5
    x,y = map(int,input().split())
6
    r[i] = x
7
    t[i] = y
8
dp = [[0]*(m+1) for _ in range(n+1)]
9
for i in range(1,n+1):
10
    for j in range(1,m+1):
11
        if t[i] > j:
12
            dp[i][j] = dp[i-1][j]
13
        else:
14
            dp[i][j] = max(dp[i-1][j],dp[i-1][j-t[i]]+ r[i])
15
print(dp[n][m])

1
#include<bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4

5
int main(){
6
    int n, m;
7
    cin >> n >> m;
8
    vector<int> r(n+1), t(n+1);
9

10
    for(int i = 1; i <= n; i++){
11
        cin >> r[i] >> t[i];
12
    }
13

14
    vector<vector<ll>> dp(n+1, vector<ll>(m+1, 0));
15

16
    for(int i = 1; i <= n; i++){
17
        for(int j = 1; j <= m; j++){
18
            if(t[i] > j){
19
                dp[i][j] = dp[i-1][j];
20
            } else {
21
                dp[i][j] = max(dp[i-1][j], dp[i-1][j - t[i]] + r[i]);
22
            }
23
        }
24
    }
25

26
    cout << dp[n][m] << endl;
27
    return 0;
28
}

1
n,m = map(int,input().split())
2
g = []
3
for _ in range(m):
4
    u,v,w = map(int,input().split())
5
    g.append((w,u,v))
6
g.sort()
7
p = list(range(n+1))
8
rank = [1]*(n+1)
9
def find(p, x):
10
    if p[x] != x:
11
        p[x] = find(p, p[x])
12
    return p[x]
13

14
def union(p, rank, x, y):
15
    rx, ry = find(p, x), find(p, y)
16
    if rx == ry:
17
        return False
18
    if rank[rx] < rank[ry]:
19
        p[rx] = ry
20
    elif rank[rx] > rank[ry]:
21
        p[ry] = rx
22
    else:
23
        p[ry] = rx
24
        rank[rx] += 1
25
    return True
26
res = 0
27
cnt = 0
28
for w,u,v in g:
29
    if union(p,rank,u,v):
30
        res += w
31
        cnt += 1
32
        if cnt == n-1:
33
            break
34
if cnt == n-1:
35
    print(res)
36
else:
37
    print("-1")

1
#include<bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4
vector<int> p;
5
vector<int> rk;
6
int find(int x){
7
    if(p[x] != x){
8
        p[x] = find(p[x]);
9
    }
10
    return p[x];
11
}
12
bool unite(int x,int y){
13
    int rx = find(x),ry = find(y);
14
    if(rx == ry){
15
        return false;
16
    }
17
    else if (rk[rx] < rk[ry]){
18
        p[rx] = ry;
19
    }
20
    else if (rk[rx] > rk[ry]){
21
        p[ry] = rx;
22
    }
23
    else{
24
        p[ry] = rx;
25
        rk[rx]++;
26
    }
27
    return true;
28
}
29
int main(){
30
    int n,m;
31
    cin >> n >> m;
32
    vector<tuple<int,int,int>>edges;
33
    for(int i = 0;i < m;i++){
34
        int u,v,w;
35
        cin >> u >> v >> w;
36
        edges.emplace_back(w,u,v);
37
    }
38
    sort(edges.begin(),edges.end());
39
    p.resize(n+1);
40
    rk.resize(n+1,1);
41
    for(int i = 1;i <= n;i++){
42
        p[i] = i;
43
    }
44
    long long res = 0;
45
    int cnt = 0;
46
    for (auto edge : edges) {
47
        int w = get<0>(edge), u = get<1>(edge), v = get<2>(edge);
48
        if (unite(u, v)) {
49
            res += w;
50
            cnt++;
51
            if (cnt == n - 1) break;
52
        }
53
    }
54
    if (cnt == n-1){
55
        cout << res << endl;
56
    }
57
    else{
58
        cout << -1 << endl;
59
    }
60
    return 0;
61
}

1
class FT:
2
    def __init__(self, length):
3
        self.length = length
4
        self.tree = [0] * (length + 1)
5

6
    def lowbit(self, x):
7
        return x & -x
8

9
    def update(self, idx, val):
10
        while idx <= self.length:
11
            self.tree[idx] += val
12
            idx += self.lowbit(idx)
13

14
    def query(self, idx):
15
        res = 0
16
        while idx > 0:
17
            res += self.tree[idx]
18
            idx -= self.lowbit(idx)
19
        return res
20

21

22
def main():
23
    n, k = map(int, input().split())
24
    a = list(map(int, input().split()))
25
    sorted_a = sorted(set(a))
26
    mp = {v: i + 1 for i, v in enumerate(sorted_a)}
27
    m = len(mp)
28

29
    bit = FT(m)
30
    inv = 0
31
    for i, x in enumerate(a):
32
        idx = mp[x]
33
        inv += i - bit.query(idx)
34
        bit.update(idx, 1)
35
    ans = max(0, inv - k)
36
    print(ans)
37
if __name__ == "__main__":
38
    main()

1
#include<bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4

5
class FT{
6
private:
7
    int length;
8
    vector<ll> tree;
9
public:
10
    FT(int len):length(len),tree(len + 1,0){}
11
    int lowbit(int x){
12
        return x&-x;
13
    }
14
    void update(int idx,int val){
15
        while (idx <= length){
16
            tree[idx] += val;
17
            idx += lowbit(idx);
18
        }
19
    }
20
    ll query(int idx){
21
        ll res = 0;
22
        while (idx > 0){
23
            res += tree[idx];
24
            idx -= lowbit(idx);
25
        }
26
        return res;
27
    }
28
};
29

30
int main(){
31
    ios::sync_with_stdio(false);
32
    cin.tie(nullptr);
33
    int n,k;
34
    cin >> n >> k;
35
    vector<int> a(n);
36

37
    for(int i = 0;i < n;i++){
38
        cin >> a[i];
39
    }
40

41
    vector<int> sorted_a(a.begin(),a.end());
42
    sort(sorted_a.begin(),sorted_a.end());
43
    sorted_a.erase(unique(sorted_a.begin(), sorted_a.end()), sorted_a.end());
44

45
    unordered_map<int,int>mp;
46
    for(size_t i = 0;i < sorted_a.size();i++){
47
        mp[sorted_a[i]] = i + 1;
48
    }
49

50
    int m = sorted_a.size();
51
    FT bit(m);
52
    ll inv = 0;
53

54
    for(int i = 0;i < n;i++){
55
        int idx = mp[a[i]];
56
        inv += i - bit.query(idx);
57
        bit.update(idx,1);
58
    }
59

60
    ll ans = max(0LL, inv - k);
61
    cout << ans << endl;
62
    return 0;
63
}