QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#504500#9104. Zayin and ForestCheek_support#AC ✓581ms88360kbC++201.5kb2024-08-04 13:32:582024-08-04 13:32:59

Judging History

你现在查看的是最新测评结果

  • [2024-08-04 13:32:59]
  • 评测
  • 测评结果:AC
  • 用时:581ms
  • 内存:88360kb
  • [2024-08-04 13:32:58]
  • 提交

answer

#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>

#define DEBUG_VAR(x) { cerr << "* "#x" = " << x << endl; }
#define DEBUG_ARR(arr, l, r) \
{ \ 
    cerr << "* "#arr"[" << l << ", " << r << "]:"; \
    for(auto it = l, itr = r; it <= itr; it++) \
        cerr << arr[it] << ", "; \
    cerr << endl; \
}
#define DEBUG_FMT(...) { cerr << "* "; fprintf(stderr, __VA_ARGS__); }
#define DEBUG_HERE { DEBUG_FMT("Passing [%s] in LINE %d\n", __FUNCTION__, __LINE__); } 

using namespace std;
using LL = long long;
using ULL = unsigned long long;

LL n;
int m;

struct Bits
{
    unordered_map<LL, LL> c;

    inline LL lowbit(LL x) { return x & (-x); }
    void add(LL x, LL v)
    {
        for(LL i = 1; x <= n; x += lowbit(x), i++) {
            c[x] += i * v;
        }
    }
    LL sum(LL x)
    {
        if(x == 0) return 0;
        LL res = 0;
        for(; x > 0; x -= lowbit(x)) {
            if(c.count(x)) {
                res += c[x];
            }
        }
        return res;
    }   
} B;

int main()
{
    // freopen("1.in", "r", stdin);
    ios::sync_with_stdio(false); cin.tie(nullptr);

    cin >> n >> m;
    while(m--) {
        int opt; cin >> opt;
        if(opt == 1) {
            LL x, v;
            cin >> x >> v;
            B.add(x, v);
        } else {
            LL l, r;
            cin >> l >> r;
            cout << B.sum(r) - B.sum(l - 1) << endl;
        }
    }

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 25ms
memory: 8148kb

input:

1000000000 20000
2 384578735 526547442
1 64211261 592970906
1 512065247 448267721
1 44993150 127180320
1 880319036 927623947
1 170536687 572121854
1 896600029 804033011
1 666246328 754201635
1 654066651 179982083
2 240989825 984888006
2 372004567 858916479
2 76127818 98606736
1 181794163 902842353
1...

output:

0
43148875202
17613404710
0
32808578044
28190043566
15641637055
78276219892
14955165236
20262224725
105057452192
17002492367
57916137452
27165464255
72766353838
39458327919
38294102627
264448717384
0
70928519548
279674530483
88885017175
111664599432
69703816663
211506104092
104120007714
34403738515
...

result:

ok 6649 lines

Test #2:

score: 0
Accepted
time: 137ms
memory: 28596kb

input:

1000000000000000000 100000
1 384578735 526547442
1 64211261 592970906
1 512065247 448267721
1 44993150 127180320
1 880319036 927623947
1 170536687 572121854
1 896600029 804033011
2 666246328 931651408754201635
1 654066651 179982083
1 984888006 240989825
1 372004567 858916479
1 76127818 98606736
1 18...

output:

144205553442
497561506762
903930740555
878459229726
689906696633
859703313829
735231510045
1177875391120
1461659121798
1612314483744
2027462020547
1991476058156
2381861014705
2033973986301
2117738140401
2946661001323
2187638958334
2593068002437
1854182975909
2262561461341
3038788266419
3070435321746...

result:

ok 12561 lines

Test #3:

score: 0
Accepted
time: 581ms
memory: 88360kb

input:

1000000000000000000 100000
1 395661363384578735 526547442
1 843068846064211261 592970906
1 550209039512065247 448267721
1 79278526044993150 127180320
1 193676380880319036 927623947
1 81194098170536687 572121854
1 223947079896600029 804033011
2 921340893666246328 931651408754201635
1 3605022006540666...

output:

0
152171177084
261154456848
98759395571
132967101279
214003153997
109857765028
569583036989
221377921411
943235254745
1036051470108
1290577544766
795223506189
1251272020902
662604469794
907615793356
1786684858550
488655543368
1495388560030
1818589934911
151873013358
717984689394
2039336496945
378996...

result:

ok 12561 lines