結果
| 問題 | No.877 Range ReLU Query |
| ユーザー |
 koi_kotya
|
| 提出日時 | 2019-09-06 22:41:31 |
| 言語 | C++14 (gcc 13.2.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 226 ms / 2,000 ms |
| コード長 | 7,458 bytes |
| コンパイル時間 | 2,012 ms |
| コンパイル使用メモリ | 183,820 KB |
| 実行使用メモリ | 11,900 KB |
| 最終ジャッジ日時 | 2023-08-08 04:21:46 |
| 合計ジャッジ時間 | 5,708 ms |
|
ジャッジサーバーID （参考情報） |
judge11 / judge13 |
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
4,376 KB |
| testcase_01 | AC | 2 ms
4,376 KB |
| testcase_02 | AC | 2 ms
4,376 KB |
| testcase_03 | AC | 3 ms
4,376 KB |
| testcase_04 | AC | 1 ms
4,376 KB |
| testcase_05 | AC | 2 ms
4,376 KB |
| testcase_06 | AC | 2 ms
4,380 KB |
| testcase_07 | AC | 2 ms
4,380 KB |
| testcase_08 | AC | 3 ms
4,376 KB |
| testcase_09 | AC | 2 ms
4,376 KB |
| testcase_10 | AC | 2 ms
4,376 KB |
| testcase_11 | AC | 223 ms
11,620 KB |
| testcase_12 | AC | 189 ms
11,220 KB |
| testcase_13 | AC | 151 ms
8,268 KB |
| testcase_14 | AC | 162 ms
8,248 KB |
| testcase_15 | AC | 226 ms
11,656 KB |
| testcase_16 | AC | 211 ms
11,524 KB |
| testcase_17 | AC | 221 ms
11,572 KB |
| testcase_18 | AC | 216 ms
11,392 KB |
| testcase_19 | AC | 172 ms
11,676 KB |
| testcase_20 | AC | 203 ms
11,900 KB |
ソースコード
// V...TPsnnwwnnPC..............jm..............a..............................Aw
// .ymNq.. Yq.en....ye....pc.....pM...............g......................................Y.
// .ymPf. ..YNwp... .c.......yc....yC......r................jE...h........j...je..........................Y
// .pmPf.. ....jC r.......aN......g......yP..m.............jC...jb.........j....p..k..........................k
// j. jH y......yCg..vp...j....ycy.yjA..............p...pjO..........Fk...Op..k...........Jp..............h.
// K g . gJC.r...jN..r...bC.gjp...........M.F.jC..b..........jHj..jOH...k............Q...............Y
// jN k .jAbNfkC . f.b.........yC gjC j.h.........F. pjO.L....p............Jp...............C
// jh N r.NNNj. .... P. KOjlPfYsw..y. b. L.....p.............Ap....W.........k
// gH qNNp N A...NNqb .. ..... .. ..Jp..............Xp....q........L
// B jpNNNNNNNNNNNp N y.....lNj. .... Jp...............ln...Jp.......p
// jC jNNC N A.......jN .p.................q...k......j
// jE .gpNNP N C......jNNp .g..................V..t.....j.
// .h NNNNC. N b......KNNNh ... t...................Xpj....j.
// K. gpp k h.....gNNNNNN .ugjgpppppppc KW.......jp...........Q...j
// jp gNN. g L.pn.gNNNNNNNNp ...... hP............. NqNp......Jp............Y.F
// jE gNNgNNr jNN K Z...gNNNNNNNNNNN. upNNNNNNNNn jNNNp......Y..............C Ap
// Jh gNNN..NNp jNNC fH .C...gNNNNNNNNNNNNNh. C. .jNp.Jp.....Jp..............Y..C...
// jh fNN. JNNNNP. jpz....jNNNNNNNNNNNNNNNNb. . jNY......k.........Jq....JQ.C ac..
// jC ........... C...MfNNNNNNNNNNNNjNNNNNk jH...V.....j...........V....lp..........
// jH lPP.....jNNP Et. jNNNNNNNNNNNNgNNNNqCj Jp...Jp....t............C....t.......y
// B g. JC B KNNNNNNNNNNNNjNNNj. j ....wwsPPYYvw.. .g......Q....L............l.....p..ppC
// jh KNN. B NNNNNjNNNNNNNjNNy L ..cP..................V ....... .hp...p.............W....VP.
// Jp .NNNNNNNNNNNN jC jNNNNNNNNNNNNNNNq. f ge......................jO .gNNgNp..j..............lp...pqu..
// jC g NNNNqNNNNNNNNNNi p Jp.......................h .KNNNNNNbNNjNNNNNp.jNp..............p..jNpNP
// K N gNNNNpNNNNNNNNNL L. .W....................P. .yQNNNNNNNjNCFNNNNNNN.jNNp...jp.........p..H
// jE jC pNNCJpNNNNNNNNNC v. .Yc............ .vE..KNNggNbNdy jNNgpNNNpjNppb...y.........Hp.H
// g j. NNL QNNNNNNNpNC .w. .........JpNgNNNNNgjNNNNNNNbgNNNNN..j........f tj.
// K. j. VhNNNNNpNk .v.. ..aC..........jNNNNNNNjNNNNNNNNNNHNNNNNNb.jH......j. .
// lNNNNNwpp. lC .YqpNNpNN. fZw... ..ypN............yNgNNNNNNyNNNNNNNNNNNNNNNNNNNNkjH.....j.
// .YWp....ypmmmNNNNNNNmmN .Y.Yph. A..JCf....Yy..........ypNNNNNO..........jNbNNNNNNNNjNNNNNNNNNNNNNNNNNNNNNNNj.....gNNb
// YQy . bjb.pNNNNNNNyNNqNNNNQ.........pmPNNNNNNNNNNNqNNNNNNNNNNNNNNNNNNNNNNNNNO...gNNNNNE
// .ANNNNgPjNNqNNNNNNgppNNjppmNNgNNNNNNNNNNNNNNNyNNNNNNNNNNNNNNNNNNNNNNNNNOjgNNNNNNNNNC
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
#define p_ary(ary,a,b,i) do { cout << "["; for (int (i) = (a);(i) < (b);++(i)) cout << ary[(i)] << ((b)-1 == (i) ? "" : ", "); cout << "]\n"; } while(0)
#define p_map(map,it) do {cout << "{";for (auto (it) = map.begin();;++(it)) {if ((it) == map.end()) {cout << "}\n";break;}else cout << "" << (it)->first << "=>" << (it)->second << ", ";}}while(0)
struct SegmentTree {
private:
int n;
vector<ll> node;
public:
SegmentTree(vector<ll> v) {
int sz = v.size();
n = 1;
while (n < sz) n *= 2;
node.resize(2*n-1,0);
for (int i = 0;i < sz;++i) node[i+n-1] = v[i];
for (int i = n-2;i >= 0;--i) node[i] = node[2*i+1]+node[2*i+2];
}
void add(int x,ll val) {
x += (n-1);
node[x] += val;
while (x > 0) {
x = (x-1)/2;
node[x] = node[2*x+1]+node[2*x+2];
}
}
ll getsum(int a,int b,int k = 0,int l = 0,int r = -1) {
if (r < 0) r = n;
if (r <= a || b <= l) return 0;
if (a <= l && r <= b) return node[k];
ll vl = getsum(a,b,2*k+1,l,(l+r)/2);
ll vr = getsum(a,b,2*k+2,(l+r)/2,r);
return vl+vr;
}
};
struct query {
int i,l,r;
ll x;
bool operator<(const query& a) const {
return x < a.x;
}
};
int main() {
int n,q,c;
cin >> n >> q;
vector<P> a(n);
vector<query> qry(q);
vector<ll> ans(q);
SegmentTree seg1(vector<ll>(n,0)),seg2(vector<ll>(n,0));
for (int i = 0;i < n;++i) {
scanf("%d",&a[i].first);
a[i].second = i;
}
sort(a.begin(),a.end());
reverse(a.begin(),a.end());
for (int i = 0;i < q;++i) {
cin >> c >> qry[i].l >> qry[i].r >> qry[i].x;
qry[i].i = i;
}
sort(qry.begin(),qry.end());
reverse(qry.begin(),qry.end());
int j = 0;
for (int i = 0;i < q;++i) {
while (j < n && a[j].first >= qry[i].x) {
seg1.add(a[j].second,a[j].first);
seg2.add(a[j].second,1);
j++;
}
ll ret = 0;
ret += seg1.getsum(qry[i].l-1,qry[i].r);
ret -= seg2.getsum(qry[i].l-1,qry[i].r)*qry[i].x;
ans[qry[i].i] = ret;
}
for (int i = 0;i < q;++i) cout << ans[i] << "\n";
return 0;
}