Submission #74573

ソースコード

#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() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
 
    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 11:03:46
言語	C++17
状態	Accepted
得点	5
ソースコード長	1736 Byte
最大実行時間	242 ms
最大メモリ使用量	26436 KB

セット

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

テストケース

ファイル名	状態	実行時間	メモリ使用量	#
00_sample_00.in	AC	22 ms	604 KB	1
00_sample_01.in	AC	20 ms	436 KB	1
01_small_00.in	AC	29 ms	388 KB	1
01_small_01.in	AC	18 ms	468 KB	1
01_small_02.in	AC	17 ms	548 KB	1
01_small_03.in	AC	23 ms	632 KB	1
01_small_04.in	AC	23 ms	460 KB	1
02_corner_minimum_00.in	AC	20 ms	540 KB	1
02_corner_minimum_01.in	AC	16 ms	496 KB	1
02_corner_minimum_02.in	AC	19 ms	580 KB	1
02_corner_minimum_03.in	AC	32 ms	408 KB	1
02_corner_minimum_04.in	AC	26 ms	624 KB	1
02_corner_minimum_05.in	AC	31 ms	704 KB	1
02_corner_minimum_06.in	AC	23 ms	656 KB	1
02_corner_minimum_07.in	AC	28 ms	608 KB	1
03_general_00.in	AC	21 ms	564 KB	1
03_general_01.in	AC	19 ms	516 KB	1
04_random_00.in	AC	20 ms	720 KB	1
04_random_01.in	AC	18 ms	668 KB	1
04_random_02.in	AC	23 ms	744 KB	1
04_random_03.in	AC	20 ms	552 KB	1
05_large_00.in	AC	20 ms	720 KB	1
05_large_01.in	AC	19 ms	836 KB	1
05_large_02.in	AC	28 ms	1036 KB	1
05_large_03.in	AC	19 ms	1320 KB	1
06_corner_maximum_00.in	AC	236 ms	26416 KB	1
06_corner_maximum_01.in	AC	194 ms	23108 KB	1
06_corner_maximum_02.in	AC	196 ms	23164 KB	1
06_corner_maximum_03.in	AC	195 ms	23224 KB	1
06_corner_maximum_04.in	AC	206 ms	23164 KB	1
07_corner_critical_00.in	AC	141 ms	26412 KB	1
07_corner_critical_01.in	AC	144 ms	26416 KB	1
07_corner_critical_02.in	AC	133 ms	26416 KB	1
07_corner_critical_03.in	AC	116 ms	26424 KB	1
07_corner_critical_04.in	AC	239 ms	26428 KB	1
07_corner_critical_05.in	AC	242 ms	26432 KB	1
07_corner_critical_06.in	AC	190 ms	26308 KB	1
07_corner_critical_07.in	AC	230 ms	26436 KB	1