#949512 (C++17) No.2627 Unnatural Pitch

• 問題: No.2627 Unnatural Pitch
• ユーザー: ゆにぽけ
• 提出日時: 2024-02-09 22:48:00
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: WA
• 実行時間: -
• コード長: 1,968 bytes
• コンパイル時間: 1,392 ms
• コンパイル使用メモリ: 130,948 KB
• 最終ジャッジ日時: 2025-02-19 03:59:59
• ジャッジサーバーID （参考情報）: judge2 / judge1

ファイルパターン	結果
sample	AC * 3
other	AC * 8 WA * 15

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include <iostream>
#include <vector>
#include <algorithm>
#include <array>
#include <iterator>
#include <string>
#include <cctype>
#include <cstring>
#include <cstdlib>
#include <cassert>
#include <cmath>
#include <ctime>
#include <iomanip>
#include <numeric>
#include <stack>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <bitset>
#include <random>
#include <utility>
#include <functional>
using namespace std;
template<class T> struct BinaryIndexedTree
{
    private:
    int N;
    vector<T> node;
    public:
    BinaryIndexedTree() : N(0) {}
    BinaryIndexedTree(int N) : N(N), node(N) {}
    void add(int pos,T x)
    {
        assert(0 <= pos && pos < N);
        pos++;
        while(pos <= N)
        {
            node[pos-1] += x;
            pos += pos & -pos;
        }
    }
    T sum(int l,int r)
    {
        assert(0 <= l && l <= N && r <= N);
        return sum(r) - sum(l);
    }
    T sum(int r)
    {
        T ret = 0;
        while(r > 0)
        {
            ret += node[r-1];
            r -= r & -r;
        }
        return ret;
    }
    T sum() {return sum(N);}
    
};
void Main()
{
    int N,K;
    long long L,U;
    cin >> N >> K >> L >> U;
    vector<long long> A(N);
    for(int i = 0;i < N;i++)
    {
        cin >> A[i];
    }
    sort(A.begin(),A.end());
    vector<long long> S(N + 1);
    for(int i = 0;i < N;i++)
    {
        S[i + 1] = S[i] + A[i] / K;
    }
    long long ans = (long long)1e18;
    int ri = 0;
    BinaryIndexedTree<int> rcnt(K),lcnt(K);
    for(int i = 0;i < N;i++)
    {
        rcnt.add(A[i] % K,1);
    }
    for(int i = 0;i < N;i++)
    {
        while(ri < N && A[ri] <= A[i] + U - L)
        {
            rcnt.add(A[ri] % K,-1);
            ri++;
        }
        long long cur = 0;
        {
            //left
            
            cur += A[i] / K * i - S[i];
            cur += i - lcnt.sum(0,A[i] % K + 1);
        }
        {
            //right
            cur += S[N] - S[ri];
            cur -= (A[i] + U - L) / K * (N - ri);
            cur += N - ri - rcnt.sum(0,(A[i] + U - L) % K + 1);
        }
        lcnt.add(A[i] % K,1);
        ans = min(ans,cur);
    }
    cout << ans << "\n";
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt = 1;
    /* cin >> tt; */
    while(tt--) Main();
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX