Submission #74569

ソースコード

#include <bits/stdc++.h>
 
using namespace std;
 
template<typename T>
class BinaryIndexedTree {
private:
    vector<T> data;
 
public:
    BinaryIndexedTree() = default;
 
    explicit BinaryIndexedTree(size_t sz) : data(sz + 1, 0) {}
 
    explicit BinaryIndexedTree(const vector<T> &vs) : data(vs.size() + 1, 0) {
        for(size_t i = 0; i < vs.size(); i++) data[i + 1] = vs[i];
        for(size_t i = 1; i < data.size(); i++) {
            size_t j = i + (i & -i);
            if(j < data.size()) data[j] += data[i];
        }
    }
 
    void add(int k, const T &x) {
        for(++k; k < (int) data.size(); k += k & -k) data[k] += x;
    }
 
    T fold(int r) const {
        T ret = T();
        for(; r > 0; r -= r & -r) ret += data[r];
        return ret;
    }
 
    T fold(int l, int r) const {
        return fold(r) - fold(l);
    }
};
 
#define MAX_D 10
 
int main() {
    int n;
    cin >> n;
 
    vector<int> a(n), d(n), ord(n);
    vector<string> s(n);
 
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        s[i] = to_string(a[i]);
        d[i] = s[i].size() - 1;
    }
 
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int u, int v) { return s[u] < s[v]; });
    [&](auto v) { for (int i = 0; i < n; ++i) ord[v[i]] = i; } (ord);
 
    vector<BinaryIndexedTree<int> > bit(MAX_D, BinaryIndexedTree<int>(n));
 
    long long res = 0;
 
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j <= d[i]; ++j) {
            res += bit[j].fold(ord[i]);
        }
        bit[d[i]].add(ord[i], 1);
    }
 
    cout << res << '\n';
 
    return 0;
}

ステータス

項目	データ
問題	1635 - Numeric and Lexicographic order
ユーザー名	ei1903
投稿日時	2023-07-13 10:51:02
言語	C++17
状態	Accepted
得点	5
ソースコード長	1652 Byte
最大実行時間	300 ms
最大メモリ使用量	26584 KB

セット

	セット	得点	Cases
1	ALL	5 / 5	*

テストケース

ファイル名	状態	実行時間	メモリ使用量	#
00_sample_00.in	AC	23 ms	600 KB	1
00_sample_01.in	AC	25 ms	572 KB	1
01_small_00.in	AC	23 ms	416 KB	1
01_small_01.in	AC	23 ms	516 KB	1
01_small_02.in	AC	16 ms	616 KB	1
01_small_03.in	AC	23 ms	588 KB	1
01_small_04.in	AC	19 ms	428 KB	1
02_corner_minimum_00.in	AC	22 ms	524 KB	1
02_corner_minimum_01.in	AC	18 ms	488 KB	1
02_corner_minimum_02.in	AC	20 ms	588 KB	1
02_corner_minimum_03.in	AC	23 ms	556 KB	1
02_corner_minimum_04.in	AC	19 ms	400 KB	1
02_corner_minimum_05.in	AC	20 ms	504 KB	1
02_corner_minimum_06.in	AC	20 ms	604 KB	1
02_corner_minimum_07.in	AC	22 ms	580 KB	1
03_general_00.in	AC	22 ms	556 KB	1
03_general_01.in	AC	21 ms	524 KB	1
04_random_00.in	AC	26 ms	620 KB	1
04_random_01.in	AC	27 ms	584 KB	1
04_random_02.in	AC	15 ms	548 KB	1
04_random_03.in	AC	23 ms	640 KB	1
05_large_00.in	AC	16 ms	564 KB	1
05_large_01.in	AC	26 ms	700 KB	1
05_large_02.in	AC	18 ms	928 KB	1
05_large_03.in	AC	26 ms	1232 KB	1
06_corner_maximum_00.in	AC	294 ms	26352 KB	1
06_corner_maximum_01.in	AC	245 ms	23068 KB	1
06_corner_maximum_02.in	AC	243 ms	23024 KB	1
06_corner_maximum_03.in	AC	254 ms	23108 KB	1
06_corner_maximum_04.in	AC	256 ms	23192 KB	1
07_corner_critical_00.in	AC	207 ms	26464 KB	1
07_corner_critical_01.in	AC	213 ms	26492 KB	1
07_corner_critical_02.in	AC	192 ms	26516 KB	1
07_corner_critical_03.in	AC	179 ms	26536 KB	1
07_corner_critical_04.in	AC	291 ms	26432 KB	1
07_corner_critical_05.in	AC	300 ms	26584 KB	1
07_corner_critical_06.in	AC	263 ms	26476 KB	1
07_corner_critical_07.in	AC	280 ms	26368 KB	1