QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#547252#9104. Zayin and Forestwzxtsl#WA 67ms13832kbC++17875b2024-09-04 19:46:062024-09-04 19:46:07

Judging History

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

  • [2024-09-04 19:46:07]
  • 评测
  • 测评结果:WA
  • 用时:67ms
  • 内存:13832kb
  • [2024-09-04 19:46:06]
  • 提交

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'