結果
問題 | No.877 Range ReLU Query |
ユーザー |
![]() |
提出日時 | 2019-09-06 22:41:31 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 235 ms / 2,000 ms |
コード長 | 7,458 bytes |
コンパイル時間 | 2,059 ms |
コンパイル使用メモリ | 183,080 KB |
実行使用メモリ | 12,184 KB |
最終ジャッジ日時 | 2024-11-08 10:08:10 |
合計ジャッジ時間 | 5,749 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 3 ms
5,248 KB |
testcase_02 | AC | 3 ms
5,248 KB |
testcase_03 | AC | 3 ms
5,248 KB |
testcase_04 | AC | 2 ms
5,248 KB |
testcase_05 | AC | 2 ms
5,248 KB |
testcase_06 | AC | 3 ms
5,248 KB |
testcase_07 | AC | 2 ms
5,248 KB |
testcase_08 | AC | 4 ms
5,248 KB |
testcase_09 | AC | 2 ms
5,248 KB |
testcase_10 | AC | 3 ms
5,248 KB |
testcase_11 | AC | 234 ms
11,848 KB |
testcase_12 | AC | 198 ms
11,384 KB |
testcase_13 | AC | 160 ms
8,596 KB |
testcase_14 | AC | 169 ms
8,628 KB |
testcase_15 | AC | 235 ms
12,176 KB |
testcase_16 | AC | 230 ms
11,740 KB |
testcase_17 | AC | 235 ms
11,816 KB |
testcase_18 | AC | 229 ms
12,024 KB |
testcase_19 | AC | 181 ms
12,176 KB |
testcase_20 | AC | 217 ms
12,184 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; }