QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#504768 | #9104. Zayin and Forest | Xunwuqishi# | TL | 91ms | 39832kb | C++20 | 1.9kb | 2024-08-04 15:44:54 | 2024-08-04 15:44:54 |
Judging History
answer
#include<bits/stdc++.h>
#define Alex std::ios::sync_with_stdio(false),std::cin.tie(0),std::cout.tie(0);
#define int long long
#define double long double
const int QAQ = 0;
const double eps = 1e-10;
const int mod = 1e9 + 7;
const int N = 1e7 + 10;
inline int lowbit(int x)
{
return x & (-x);
}
struct node {
int l, r;
int add, sum;
} tr[N << 1];
int n, m, idx, root;
void pushup(int p)
{
tr[p].sum = tr[tr[p].l].sum + tr[tr[p].r].sum;
}
void pushdown(int p, int l, int r)
{
if(tr[p].add) {
int mid = l + r >> 1;
tr[tr[p].l].sum += (mid - l + 1) * tr[p].add, tr[tr[p].l].add += tr[p].add;
tr[tr[p].r].sum += (r - mid) * tr[p].add, tr[tr[p].r].add += tr[p].add;
tr[p].add = 0;
}
}
void modify(int &p, int l, int r, int ql, int qr, int k)
{
if(!p) p = ++idx;
if(l >= ql && r <= qr) {
tr[p].sum += (r - l + 1) * k;
tr[p].add += k;
return ;
}
pushdown(p, l, r);
int mid = l + r >> 1;
if(ql <= mid) modify(tr[p].l, l, mid, ql, qr, k);
if(qr > mid) modify(tr[p].r, mid + 1, r, ql, qr, k);
pushup(p);
}
int query(int p, int l, int r, int ql, int qr)
{
if(l >= ql && r <= qr) { return tr[p].sum; }
int mid = l + r >> 1;
pushdown(p, l, r);
int v = 0;
if(ql <= mid) v = query(tr[p].l, l, mid, ql, qr);
if(qr > mid) v += query(tr[p].r, mid + 1, r, ql, qr);
return v;
}
signed main()
{
Alex;
int _;
_ = 1;
while(_--)
{
std::cin>>n>>m;
std::map<int,int> ma;
root = 0;
for(int i = 1;i <= m;i++)
{
int op;
std::cin>>op;
if(op == 1)
{
int x,v;
std::cin>>x>>v;
for(x;x <= n;x = x + lowbit(x))
{
modify(root, 1, n, x, x, v);
}
}else
{
int l,r;
int ans = 0;
std::cin>>l>>r;
ans = query(root, 1, n, l, r);
std::cout<<ans<<'\n';
}
}
}
return QAQ;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 91ms
memory: 39832kb
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: -100
Time Limit Exceeded
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...