QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#547252 | #9104. Zayin and Forest | wzxtsl# | WA | 67ms | 13832kb | C++17 | 875b | 2024-09-04 19:46:06 | 2024-09-04 19:46:07 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+7;
#define lowbit(x) (x&(-x))
int a[500005];
map<int,int> c;
int n,m;
//区间修改
int update(int pos,int k){//pos表示修改点的位置,K表示修改的值也即+K操作
int cnt=1;
for(int i=pos;i<=n;i+=lowbit(i)){
c[i]+=cnt*k;
cnt++;
}
return 0;
}
//单点查询
int ask_qujian(int pos){//返回区间pos到1的总和,由于是使用差分数组维护因此使用前缀和
int ans=0;
for(int i=pos;i;i-=lowbit(i)){
ans+=c[i];
}
return ans;
}
signed main(){
cin>>n>>m;
while(m--){
int a;
int x,y;
cin>>a;
if(a==1){
cin>>x>>y;
update(x,y);
}else{
cin>>x>>y;
cout<<ask_qujian(y)-ask_qujian(x-1)<<endl;
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 67ms
memory: 13832kb
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 199202242 433535526 0 -1551160324 -1874727506 -1538232129 966808564 2070263348 -1212611755 1978237088 -177376817 2081562604 1395660479 -248090194 803622255 -360603037 -1839254968 0 -2085924484 501656243 -1309296041 -4550264 984339927 1052706588 1040792610 44000147 0 1402534480 2004564958 -60143242...
result:
wrong answer 2nd lines differ - expected: '43148875202', found: '199202242'