QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#504500 | #9104. Zayin and Forest | Cheek_support# | AC ✓ | 581ms | 88360kb | C++20 | 1.5kb | 2024-08-04 13:32:58 | 2024-08-04 13:32:59 |
Judging History
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