QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#504888#9104. Zayin and ForestXunwuqishi#TL 225ms29416kbC++231.9kb2024-08-04 16:59:302024-08-04 16:59:31

Judging History

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

  • [2024-08-04 16:59:31]
  • 评测
  • 测评结果:TL
  • 用时:225ms
  • 内存:29416kb
  • [2024-08-04 16:59:30]
  • 提交

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;

map<int,int> mp;
set<int> st;
int cnt;
int input[100005][3];

void solve() {
    cin>>n>>m;
    cnt = 1;

    int x,v,l,r,op;

    for(int i = 1;i<=m;i++){
        cin>>input[i][0]>>input[i][1]>>input[i][2];
        st.insert(input[i][1]);
        if(input[i][0] == 2)st.insert(input[i][2]);

        if(input[i][0] == 1){
            x = input[i][1];
            while(x < 1e18){
                st.insert(x);
                x += lowbit(x);
            }
        }
    }

    for(auto i:st) mp[i] = cnt++;

    for(int i = 1;i<=m;i++){
        if(input[i][0] == 2){
            l = mp[input[i][1]];
            r = mp[input[i][2]];

            cout<<tree.range_ask(l,r)<<endl;
        }
        else{
            x = input[i][1];
            v = input[i][2];

            while(x < 1e18){
                tree.range_add(mp[x],mp[x],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: 225ms
memory: 29416kb

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...

result: