Submission #64790

ソースコード

?
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
#include <cmath>
#include <vector>
#include <iostream>
#include <algorithm>
#include <set>
#include <iomanip>
#include <queue>
#include <string>
#include <map>
#include <fstream>
#include <cassert>
#include <stack>
#include <climits>
#include <array>
#include <unordered_set>
#include <unordered_map>
#include <memory>
#include <functional>
#include <cfloat>
#include <numeric>
#include <random>
#include <sstream>
#include <bitset>
using namespace std;
class Bit {
std::vector<int> vec;
public:
Bit(const int size) : vec(size, 0) {};
int get(int pos) const {
int sum{ 0 };
while (pos >= 0) {
sum += vec[pos];
pos -= (pos + 1) & ~pos;
}
return sum;
}
void increment(int pos) {
while (pos < vec.size()) {
vec[pos]++;
pos += (pos + 1) & ~pos;
}
}
};
long long int swap_count(const std::vector<int> &numbers) {
auto sorted = numbers;
std::sort(sorted.begin(), sorted.end());
std::unordered_map<int, int> compress;
for (auto i = 0; i < sorted.size(); ++i) {
compress[sorted[i]] = i;
}
Bit bit(numbers.size());
long long int result{ 0 };
for (auto i = 0; i < numbers.size(); ++i) {
const auto a = compress[numbers[i]];
result += i - bit.get(a);
bit.increment(a);
}
return result;
}
void solve(std::vector<int> numbers, const int query) {
const int section = std::sqrt(numbers.size());
std::vector<std::vector<int>> sections((numbers.size() + section - 1) / section);
for (auto i = 0; i < numbers.size(); i += section) {
const auto size = std::min<int>(section, numbers.size() - i);
sections[i / section].reserve(size);
std::copy(std::next(std::begin(numbers), i), std::next(std::begin(numbers), i + size), std::back_inserter(sections[i / section]));
std::sort(std::begin(sections[i / section]), std::end(sections[i / section]));
}
long long int count{ swap_count(numbers) };
for (auto q = 0; q < query; ++q) {
int begin, end; std::cin >> begin >> end; --begin; --end;
const auto right = numbers[begin];
const auto left = numbers[end];
std::swap(numbers[begin], numbers[end]);
if (right < left) ++count;
else --count;
{
const auto until = std::min((begin / section + 1) * section, end);
for (auto i = begin + 1; i < until; ++i) {
if (right < numbers[i]) ++count;
else --count;
if (left < numbers[i]) --count;
else ++count;
}
const auto pos = begin / section;
const auto offset = pos * section;
for (auto i = 0; i < sections[pos].size(); ++i) {
sections[pos][i] = numbers[i + offset];
}
std::sort(sections[pos].begin(), sections[pos].end());
}
if (begin / section < end / section) {
for (auto i = end / section * section; i < end; ++i) {
if (right < numbers[i]) ++count;
else --count;
if (left < numbers[i]) --count;
else ++count;
}
const auto pos = end / section;
const auto offset = pos * section;
for (auto i = 0; i < sections[pos].size(); ++i) {
sections[pos][i] = numbers[i + offset];
}
std::sort(sections[pos].begin(), sections[pos].end());
}
const auto until = end / section;
for (auto i = begin / section + 1; i < until; ++i) {
const auto under_right = std::distance(sections[i].begin(), std::lower_bound(sections[i].begin(), sections[i].end(), right));
const auto under_left = std::distance(sections[i].begin(), std::lower_bound(sections[i].begin(), sections[i].end(), left));
count += (under_left - under_right) << 1;
}
std::cout << count << '\n';
}
}
int main() {
int n; std::cin >> n;
std::vector<int> nums(n);
for (auto& a : nums) std::cin >> a;
int m; std::cin >> m;
solve(nums, m);
}

ステータス

項目 データ
問題 1461 - 交換と転倒数
ユーザー名 syoribu
投稿日時 2020-11-20 12:28:49
言語 C++17
状態 Accepted
得点 12
ソースコード長 3705 Byte
最大実行時間 2252 ms
最大メモリ使用量 31620 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in1 AC 26 ms 604 KB
1
in2 AC 22 ms 2092 KB
1
in3 AC 17 ms 2476 KB
1
in4 AC 21 ms 2576 KB
1
in5 AC 26 ms 2672 KB
1
in6 AC 17 ms 2632 KB
1
in7 AC 17 ms 2600 KB
1
in8 AC 21 ms 2564 KB
1
in9 AC 18 ms 2660 KB
1
in10 AC 19 ms 444 KB
1
in11 AC 29 ms 528 KB
1
in12 AC 38 ms 596 KB
1
in13 AC 31 ms 1016 KB
1
in14 AC 116 ms 1208 KB
1
in15 AC 2252 ms 30104 KB
1
in16 AC 2182 ms 30392 KB
1
in17 AC 1021 ms 30804 KB
1
in18 AC 819 ms 31088 KB
1
in19 AC 1035 ms 31240 KB
1
in20 AC 825 ms 31620 KB
1