QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#504903 | #9104. Zayin and Forest | Xunwuqishi# | WA | 423ms | 53120kb | C++23 | 2.1kb | 2024-08-04 17:09:44 | 2024-08-04 17:09:45 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) x&(-x)
#define int long long
const int N = 1e7+10;
//int INF = 1e9;
int mod = 998244353;
typedef struct{
#define lowbit(x) x&(-x)
#define int long long
typedef long long ll;
int sum1[N],sum2[N];
void add(ll p, ll x){
for(int i = p; i <= 1e6; i += i & -i)
sum1[i] += x, sum2[i] += x * p;
}
void range_add(ll l, ll r, ll x){
add(l, x), add(r + 1, -x);
}
ll ask(ll p){
ll res = 0;
for(int i = p; i; i -= i & -i)
res += (p + 1) * sum1[i] - sum2[i];
return res;
}
ll range_ask(ll l, ll r){
return ask(r) - ask(l - 1);
}
}TR;
TR tree;
int n,m;
int cnt;
int input[100005][3];
vector<int> st;
int getid(int x)
{
return lower_bound(st.begin(),st.end(),x)-st.begin()+1;
}
void solve() {
cin>>n>>m;
int x,v,l,r,op;
for(int i = 1;i<=m;i++){
cin>>input[i][0]>>input[i][1]>>input[i][2];
st.push_back(input[i][1]);
if(input[i][0] == 2)st.push_back(input[i][2]);
if(input[i][0] == 1){
x = input[i][1];
while(x <= n){
st.push_back(x);
x += lowbit(x);
}
}
}
sort(st.begin(),st.end());
st.erase(unique(st.begin(),st.end()) ,st.end());
for(int i = 1;i<=m;i++){
if(input[i][0] == 2){
l = getid(input[i][1]);
r = getid(input[i][2]);
cout<<tree.range_ask(l,r)<<endl;
}
else{
x = input[i][1];
v = input[i][2];
while(x <= n){
int id = getid(x);
tree.range_add(id,id,v);
x += lowbit(x);
}
}
}
}
signed main() {
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
//cout<<fixed<<setprecision(8);
int caset = 1;
//cin>>caset;
for(int i = 1;i<=caset;i++){
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 32ms
memory: 16556kb
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: 423ms
memory: 53120kb
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: -100
Wrong Answer
time: 418ms
memory: 45388kb
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 -239443695265 -382977695485 -383805817131 132967101279 0 0 -112712851434 221377921411 -252810987758 -24193875290 -126747304754 -967433500725 -52614010984 0 -1034584607405 -245826339578 488655543368 -52614010984 -286682068929 151873013358 717984689394 -473614653952 0 -1589187227133 -76156070118 0 1...
result:
wrong answer 2nd lines differ - expected: '152171177084', found: '-239443695265'