Submission #74595

ソースコード

#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 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 18:52:29
言語	C++17
状態	Accepted
得点	5
ソースコード長	1629 Byte
最大実行時間	355 ms
最大メモリ使用量	26548 KB

セット

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

テストケース

ファイル名	状態	実行時間	メモリ使用量	#
00_sample_00.in	AC	23 ms	604 KB	1
00_sample_01.in	AC	17 ms	440 KB	1
01_small_00.in	AC	17 ms	412 KB	1
01_small_01.in	AC	25 ms	512 KB	1
01_small_02.in	AC	28 ms	612 KB	1
01_small_03.in	AC	18 ms	580 KB	1
01_small_04.in	AC	24 ms	556 KB	1
02_corner_minimum_00.in	AC	21 ms	524 KB	1
02_corner_minimum_01.in	AC	19 ms	492 KB	1
02_corner_minimum_02.in	AC	16 ms	464 KB	1
02_corner_minimum_03.in	AC	17 ms	436 KB	1
02_corner_minimum_04.in	AC	17 ms	532 KB	1
02_corner_minimum_05.in	AC	23 ms	628 KB	1
02_corner_minimum_06.in	AC	17 ms	596 KB	1
02_corner_minimum_07.in	AC	19 ms	568 KB	1
03_general_00.in	AC	17 ms	544 KB	1
03_general_01.in	AC	26 ms	512 KB	1
04_random_00.in	AC	18 ms	604 KB	1
04_random_01.in	AC	28 ms	704 KB	1
04_random_02.in	AC	28 ms	668 KB	1
04_random_03.in	AC	24 ms	632 KB	1
05_large_00.in	AC	19 ms	688 KB	1
05_large_01.in	AC	19 ms	832 KB	1
05_large_02.in	AC	24 ms	1056 KB	1
05_large_03.in	AC	32 ms	1364 KB	1
06_corner_maximum_00.in	AC	287 ms	26352 KB	1
06_corner_maximum_01.in	AC	264 ms	23072 KB	1
06_corner_maximum_02.in	AC	248 ms	23148 KB	1
06_corner_maximum_03.in	AC	260 ms	23232 KB	1
06_corner_maximum_04.in	AC	262 ms	23184 KB	1
07_corner_critical_00.in	AC	202 ms	26452 KB	1
07_corner_critical_01.in	AC	211 ms	26476 KB	1
07_corner_critical_02.in	AC	193 ms	26500 KB	1
07_corner_critical_03.in	AC	180 ms	26524 KB	1
07_corner_critical_04.in	AC	355 ms	26548 KB	1
07_corner_critical_05.in	AC	299 ms	26316 KB	1
07_corner_critical_06.in	AC	251 ms	26340 KB	1
07_corner_critical_07.in	AC	269 ms	26492 KB	1