Submission #77537

ソースコード

?
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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
#include <bits/stdc++.h>
using namespace std;
struct Mo {
private:
int n;
vector<pair<int, int> > lr;
public:
Mo(int n) : n(n) {}
/* [l, r) */
void insert(int l, int r){
lr.emplace_back(l, r);
}
template<typename AL, typename AR, typename EL, typename ER, typename O>
void run(const AL &add_left, const AR &add_right, const EL &erase_left, const ER &erase_right, const O &out){
int q = (int) lr.size();
int bs = n / min<int>(n, sqrt(q));
vector<int> ord(q);
iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&](int a, int b){
int ablock = lr[a].first / bs, bblock = lr[b].first / bs;
if(ablock != bblock) return (ablock < bblock);
if(ablock & 1) return (lr[a].second > lr[b].second);
return (lr[a].second < lr[b].second);
});
int l = 0, r = 0;
for(auto idx : ord){
while(l > lr[idx].first) add_left(--l);
while(r < lr[idx].second) add_right(r++);
while(l < lr[idx].first) erase_left(l++);
while(r > lr[idx].second) erase_right(--r);
out(idx);
}
}
template<typename A, typename E, typename O>
void run(const A &add, const E &erase, const O &out){
run(add, add, erase, erase, out);
}
};
template<typename T>
struct RSQ {
int bs;
vector<T> a, b;
RSQ(int n) : a(n), bs(max(1, (int) sqrt(n))), b((n + bs - 1) / bs) {}
RSQ(const vector<T> &a) : a(a), bs(max(1, (int) sqrt(a.size()))), b((a.size() + bs - 1) / bs) {}
T get(int k) const {
return a[k];
}
void add(int k, const T &v = 1) {
b[k / bs] += v;
a[k] += v;
}
void update(int k, const T &v) {
b[k / bs] += v - a[k];
a[k] = v;
}
T query(int l, int r) {
T ret = T();
for (int i = l; i < min(r, (l + bs) / bs * bs); ++i) {
ret += a[i];
}
for (int i = (l + bs) / bs; i < r / bs; ++i) {
ret += b[i];
}
for (int i = max((l + bs) / bs, r / bs) * bs; i < r; ++i) {
ret += a[i];
}
return ret;
}
T query(int r) {
return query(0, r);
}
};
int main(){
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
int n, m;
cin >> n >> m;
vector<int> a(n), t(m), vs;
Mo mo(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
vs.push_back(a[i]);
}
for (int i = 0; i < m; ++i) {
int l, r;
cin >> l >> r >> t[i];
--l, --r;
mo.insert(l, r + 1);
}
sort(vs.begin(), vs.end());
vs.erase(unique(vs.begin(), vs.end()), vs.end());
vector<int> ca(n);
for (int i = 0; i < n; ++i) {
ca[i] = lower_bound(vs.begin(), vs.end(), a[i]) - vs.begin();
}
RSQ<long long> rsq(vs.size());
RSQ<long long> rcq(vs.size());
vector<long long> res(m);
long long sum = 0;
int cnt = 0;
mo.run([&](int k) {
sum += a[k];
cnt++;
rsq.add(ca[k], a[k]);
rcq.add(ca[k], 1);
}, [&](int k) {
sum -= a[k];
cnt--;
rsq.add(ca[k], -a[k]);
rcq.add(ca[k], -1);
}, [&](int k) {
int lower = lower_bound(vs.begin(), vs.end(), t[k]) - vs.begin();
long long ls = rsq.query(lower);
long long lc = rcq.query(lower);
res[k] += (long long) lc * t[k] - ls + sum - ls - (long long) (cnt - lc) * t[k];
});
for (int i = 0; i < m; ++i) {
cout << res[i] << '\n';
}
return (0);
}

ステータス

項目 データ
問題 1730 - Sum of Absolutes
ユーザー名 ei1903
投稿日時 2024-01-19 09:26:51
言語 C++17
状態 Accepted
得点 5
ソースコード長 3745 Byte
最大実行時間 778 ms
最大メモリ使用量 40024 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
00_sample_00.in AC 23 ms 600 KB
1
01_small_00.in AC 32 ms 680 KB
1
01_small_01.in AC 19 ms 636 KB
1
01_small_02.in AC 17 ms 468 KB
1
02_corner_minimum_00.in AC 19 ms 552 KB
1
02_corner_minimum_01.in AC 29 ms 512 KB
1
02_corner_minimum_02.in AC 18 ms 472 KB
1
03_general_00.in AC 20 ms 428 KB
1
03_general_01.in AC 27 ms 508 KB
1
04_random_00.in AC 28 ms 468 KB
1
04_random_01.in AC 21 ms 544 KB
1
04_random_02.in AC 24 ms 620 KB
1
04_random_03.in AC 24 ms 552 KB
1
05_large_00.in AC 15 ms 596 KB
1
05_large_01.in AC 30 ms 876 KB
1
05_large_02.in AC 32 ms 1196 KB
1
05_large_03.in AC 27 ms 864 KB
1
06_corner_maximum_00.in AC 609 ms 13796 KB
1
06_corner_maximum_01.in AC 766 ms 16724 KB
1
06_corner_maximum_02.in AC 778 ms 19536 KB
1
07_corner_critical_00.in AC 284 ms 22344 KB
1
07_corner_critical_01.in AC 99 ms 22212 KB
1
07_corner_critical_02.in AC 586 ms 27776 KB
1
07_corner_critical_03.in AC 324 ms 30708 KB
1
07_corner_critical_04.in AC 317 ms 32620 KB
1
07_corner_critical_05.in AC 685 ms 35556 KB
1
07_corner_critical_06.in AC 770 ms 37856 KB
1
07_corner_critical_07.in AC 759 ms 40024 KB
1
07_corner_critical_08.in AC 75 ms 36432 KB
1