QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#84851	#5657. Hungry Cow	shr_	0	2855ms	420832kb	C++17	4.9kb	2023-03-06 20:16:36	2023-03-06 20:16:39

Judging History

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

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2023-03-06 20:16:39]
评测

测评结果：0
用时：2855ms
内存：420832kb

查看

[2023-03-06 20:16:36]
提交

answer

# include <bits/stdc++.h>
using namespace std;
const int mod=1e9+7,inv=5e8+4;
const long long inf=2e14;
int n,ans[100010],ro;
pair<long long,int> op[100010];
map<long long,pair<int,int> > mp;
struct Second_Segment_Tree {
    int cnt=0;
    vector<int> bin;
    struct node { 
        int son[2],sum;
        long long cnt;
    } f[10000010];
    struct operation {
        int x,opt;
        long long vl;
        operation() {}
        operation(int _x,int _opt,long long _vl) { x=_x, opt=_opt, vl=_vl;}
    };
    vector<operation> op;
    int new_() {
        if (bin.empty()) return ++cnt;
        int x=bin.back(); bin.pop_back();
        return x;
    }
    void erase_(int x) {
        f[x].son[0]=f[x].son[1]=f[x].sum=f[x].cnt=0;
        bin.push_back(x);
    }
    void pushup_(int x) { 
        op.push_back(operation(x,1,f[x].sum)), f[x].sum=(f[f[x].son[0]].sum+f[f[x].son[1]].sum)%mod;
        op.push_back(operation(x,2,f[x].cnt)), f[x].cnt=f[f[x].son[0]].cnt+f[f[x].son[1]].cnt;
    }
    int cover_(int x,long long l,long long r,long long lpos,long long rpos) {
        if (!x) x=new_(), op.push_back(operation(x,3,0));
        if (f[x].cnt==r-l+1) return x;
        if (lpos<=l&&r<=rpos) {
            op.push_back(operation(x,1,f[x].sum)), f[x].sum=(l+r)%mod*((r-l+1)%mod)%mod*inv%mod;
            op.push_back(operation(x,2,f[x].cnt)), f[x].cnt=r-l+1;
            return x;
        }
        long long mid=(l+r)>>1;
        if (lpos<=mid) f[x].son[0]=cover_(f[x].son[0],l,mid,lpos,rpos);
        if (mid<rpos) f[x].son[1]=cover_(f[x].son[1],mid+1,r,lpos,rpos);
        pushup_(x);
        return x;
    }
    pair<long long,long long> check_prefix_(int x,long long l,long long r,long long lpos,int kl) {
        if (!x&&r-max(lpos,l)+1<kl) return make_pair(1e18+7,r-max(lpos,l)+1);
        if (!x) return make_pair(max(lpos,l)+kl-1,0);
        if (f[x].cnt==r-l+1) return make_pair(1e18+7,0);
        if (lpos<=l&&r-l+1-f[x].cnt<kl) return make_pair(1e18+7,r-l+1-f[x].cnt);
        if (l==r) return make_pair(l,0);
        long long mid=(l+r)>>1;
        if (lpos>mid) return check_prefix_(f[x].son[1],mid+1,r,lpos,kl);
        auto e=check_prefix_(f[x].son[0],l,mid,lpos,kl);
        if (e.first==1e18+7) {
            auto o=check_prefix_(f[x].son[1],mid+1,r,lpos,kl-e.second);
            if (o.first==1e18+7) return make_pair(1e18+7,e.second+o.second);
            return o;
        }
        return e;
    }
    int check_sum_(int x,long long l,long long r,long long lpos,long long rpos) {
        if (!x) return 0;
        if (f[x].cnt==r-l+1) {
            lpos=max(lpos,l), rpos=min(rpos,r);
            return (lpos+rpos)%mod*((rpos-lpos+1)%mod)%mod*inv%mod;
        }
        if (lpos<=l&&r<=rpos) return f[x].sum;
        int ans=0;
        long long mid=(l+r)>>1;
        if (lpos<=mid) ans=(ans+check_sum_(f[x].son[0],l,mid,lpos,rpos))%mod;
        if (mid<rpos) ans=(ans+check_sum_(f[x].son[1],mid+1,r,lpos,rpos))%mod;
        return ans;
    }
    int check_ver_() { return op.size();}
    void rollback_(int ver) {
        while ((int)op.size()>ver) {
            operation e=op[(int)op.size()-1]; op.pop_back();
            if (e.opt==1) f[e.x].sum=e.vl;
            if (e.opt==2) f[e.x].cnt=e.vl;
            if (e.opt==3) erase_(e.x);
        }
    }
} sst;
struct First_Segment_Tree {
    struct node { vector<pair<long long,int> > op;} f[400010];
    void insert_(int k,int l,int r,int lpos,int rpos,pair<long long,int> key) {
        if (key.second==0) return;
        if (lpos<=l&&r<=rpos) { f[k].op.push_back(key); return;}
        int mid=(l+r)>>1;
        if (lpos<=mid) insert_(k<<1,l,mid,lpos,rpos,key);
        if (mid<rpos) insert_(k<<1|1,mid+1,r,lpos,rpos,key);
    }
    void solve_(int k,int l,int r) {
        int ver=sst.check_ver_();
        for (auto o : f[k].op) {
            long long lr=sst.check_prefix_(ro,1,inf,o.first,o.second).first;
            ro=sst.cover_(ro,1,inf,o.first,lr);
        }
        if (l==r) { ans[l]=sst.check_sum_(ro,1,inf,1,inf), sst.rollback_(ver); return;}
        int mid=(l+r)>>1;
        solve_(k<<1,l,mid), solve_(k<<1|1,mid+1,r);
        sst.rollback_(ver);
    }
} fst;
int main() {
//    freopen("in.in","r",stdin);
//    freopen("out.out","w",stdout);

    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%lld %d\n",&op[i].first,&op[i].second);

    for (int i=1;i<=n;i++) {
        if (mp.count(op[i].first)) fst.insert_(1,1,n,mp[op[i].first].first,i-1,pair<long long,int> (op[i].first,mp[op[i].first].second));
        mp[op[i].first]=pair<int,int> (i,op[i].second);
    }
    for (int i=1;i<=n;i++) if (mp.count(op[i].first)) fst.insert_(1,1,n,mp[op[i].first].first,n,pair<long long,int> (op[i].first,mp[op[i].first].second)), mp.erase(op[i].first);

    fst.solve_(1,1,n);

    for (int i=1;i<=n;i++) printf("%d\n",ans[i]);

    return 0;
}

Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0

Wrong Answer

time: 2ms

memory: 15340kb

input:

output:

15
36
21

result:

wrong answer 3rd numbers differ - expected: '18', found: '21'

Test #2:

score: 0

Wrong Answer

time: 0ms

memory: 16060kb

input:

output:

result:

wrong answer 3rd numbers differ - expected: '7607', found: '10731'

Test #3:

score: 0

Wrong Answer

time: 85ms

memory: 36792kb

input:

5000
1 255364995
414918035 212844
1 112266691
321122438 191414
1 277615842
848755093 61676
1 432591689
892259443 53755
1 263753018
173404455 173565
1 178341924
878941367 221276
1 65332960
439468128 240741
1 812238377
191076090 108732
1 180383041
927440330 112995
1 595696140
579818784 85614
1 5057816...

output:

result:

wrong answer 3rd numbers differ - expected: '430865692', found: '797282574'

Test #4:

score: 0

Memory Limit Exceeded

input:

100000
1 500000000
1000000001 500000000
2000000001 500000000
3000000001 500000000
4000000001 500000000
5000000001 500000000
6000000001 500000000
7000000001 500000000
8000000001 500000000
9000000001 500000000
10000000001 500000000
11000000001 500000000
12000000001 500000000
13000000001 500000000
1400...

output:

result:

Test #5:

score: 0

Wrong Answer

time: 2855ms

memory: 420832kb

input:

100000
49998999950002 500000000
49997999950003 500000000
49996999950004 500000000
49995999950005 500000000
49994999950006 500000000
49993999950007 500000000
49992999950008 500000000
49991999950009 500000000
49990999950010 500000000
49989999950011 500000000
49988999950012 500000000
49987999950013 500...

output:

result:

wrong answer 3rd numbers differ - expected: '129199846', found: '259866744'

Test #6:

score: 0

Wrong Answer

time: 2142ms

memory: 395108kb

input:

100000
92303348842417 121458
92270522994821 852054850
93765096269940 752161890
97779083359973 984327853
90030769679569 439157849
99462493683485 45660
95578441605501 614317411
92236129196525 474149928
96065411631989 429943696
90394247621798 382840249
89263934750729 791122796
93577089467158 99679481
9...

output:

result:

wrong answer 6th numbers differ - expected: '365740738', found: '105816858'

Test #7:

score: 0

Wrong Answer

time: 2127ms

memory: 384960kb

input:

100000
98001410246890 641673458
94816407430628 495030536
95979591652947 43208
95979591652947 183686
97163521776290 904784415
91640049592559 875129980
95914835187460 844802426
94846379383324 974270031
99639652388956 311664277
99298294827771 913614463
99476866913169 221766107
97248342663994 669489020
...

output:

result:

wrong answer 3rd numbers differ - expected: '575810846', found: '27866346'

Test #8:

score: 0

Wrong Answer

time: 2216ms

memory: 382444kb

input:

100000
97338601145206 191999210
97657969728741 875988993
92559675348135 8552565
99354409480201 960853995
93648768326445 343671323
97400841247229 104463842
98844341051398 508718383
96144328794112 187050711
98030257583732 365513
92378049740181 852725611
98301676983212 360931360
99458914124366 80234576...

output:

result:

wrong answer 3rd numbers differ - expected: '819965610', found: '438095378'

Test #9:

score: 0

Wrong Answer

time: 2086ms

memory: 376416kb

input:

100000
96119987448606 658315028
98644701118435 280992389
98180676447908 56168
99822794299596 237183170
94655838918825 563695131
95744558879343 686204820
93739311062176 263266841
97630990881452 96901680
98683433984282 380708175
98141920320037 147598812
98095513966598 814629225
97882900659205 55097258...

output:

result:

wrong answer 3rd numbers differ - expected: '58956281', found: '461366660'

Test #10:

score: 0

Wrong Answer

time: 2114ms

memory: 376364kb

input:

100000
98169641631056 170946511
99452522210742 393032132
98797460964704 393706377
98747209012224 529219651
99152468691953 362194103
99410753036475 215295
97096873124809 1315725
96106202009957 124516158
95176405230280 853965254
99359463136784 622839995
96635771520630 550456203
96368792029394 93630831...

output:

result:

wrong answer 3rd numbers differ - expected: '485258530', found: '846604839'

Test #11:

score: 0

Wrong Answer

time: 1816ms

memory: 354756kb

input:

100000
97499080763005 475255826
97499083333242 9347
97499080763005 395470349
97499924236501 4654
97499080763005 148122052
97499213182916 2365
97499080763005 544025506
97499777050346 9912
97499080763005 41736833
97499401163067 12607
97499080763005 127843558
97499125181305 7144
97499080763005 13152858...

output:

result:

wrong answer 3rd numbers differ - expected: '548564542', found: '159167788'

Test #12:

score: 0

Wrong Answer

time: 1914ms

memory: 353112kb

input:

100000
98999026537234 929244389
98999182418499 5182
98999026537234 774643967
98999646433835 17857
98999026537234 760743518
98999980664456 7597
98999026537234 573421161
98999090975969 6621
98999026537234 95191521
98999947586610 17798
98999026537234 953104244
98999116462517 15643
98999026537234 100617...

output:

result:

wrong answer 3rd numbers differ - expected: '692662359', found: '484071840'

Test #13:

score: 0

Wrong Answer

time: 1722ms

memory: 355008kb

input:

100000
99499024212061 630391525
99499061152079 3864
99499024212061 16505706
99499878275777 4812
99499024212061 776185964
99499757280269 12059
99499024212061 356565635
99499399237611 8902
99499024212061 972528120
99499256994518 9171
99499024212061 419476867
99499909552451 17146
99499024212061 6767939...

output:

result:

wrong answer 3rd numbers differ - expected: '813032842', found: '36439376'

Test #14:

score: 0

Wrong Answer

time: 2160ms

memory: 214508kb

input:

99999
10490328589436 1000000000
13762508396295 1000000000
40632115714511 1000000000
32834989282081 1000000000
29091918306598 1000000000
24352818172350 1000000000
23447797352860 1000000000
38073075086135 1000000000
14288530509239 1000000000
36463049009868 1000000000
10562334120356 1000000000
34490016...

output:

result:

wrong answer 5th numbers differ - expected: '984191481', found: '137460226'

Test #15:

score: 0

Wrong Answer

time: 2362ms

memory: 370860kb

input:

99999
61585049539216 1000000000
58981995705940 1000000000
44247484521936 1000000000
70916218483207 1000000000
47696673638497 1000000000
60781033156530 1000000000
55859922511212 1000000000
59143999312357 1000000000
57175954090596 1000000000
71328224891428 1000000000
46047599292678 1000000000
47510666...

output:

result:

wrong answer 3rd numbers differ - expected: '299706354', found: '943169527'

Test #16:

score: 0

Wrong Answer

time: 2232ms

memory: 223324kb

input:

99999
21219982576425 1000000000
42260400232639 1000000000
26412110792985 1000000000
11035481121988 1000000000
13219690258669 1000000000
19550933913223 1000000000
32679237390903 1000000000
15679803374289 1000000000
23896051833122 1000000000
20099950455987 1000000000
14778766729432 1000000000
21547991...

output:

result:

wrong answer 5th numbers differ - expected: '350714436', found: '102074593'

Test #17:

score: 0

Wrong Answer

time: 2007ms

memory: 220428kb

input:

99999
28503598869279 1000000000
32397709666940 1000000000
25833502058723 1000000000
38020841213328 1000000000
54560138759501 1000000000
42230929758874 1000000000
28972613620824 1000000000
28498598787317 1000000000
54070131397843 1000000000
22084267818956 1000000000
37776835952805 1000000000
44465973...

output:

result:

wrong answer 3rd numbers differ - expected: '330085498', found: '816940310'

Test #18:

score: 0

Wrong Answer

time: 2326ms

memory: 202128kb

input:

99999
18175781548542 1000000000
40883228277118 1000000000
33828113807745 1000000000
17817771477758 1000000000
22749897023579 1000000000
18015777423352 1000000000
28920025506062 1000000000
18799798298070 1000000000
27979006765970 1000000000
17103749421004 1000000000
24329932307643 1000000000
29798042...

output:

result:

wrong answer 3rd numbers differ - expected: '139117719', found: '549124503'

Test #19:

score: 0

Wrong Answer

time: 2278ms

memory: 199408kb

input:

99999
13631696063382 1000000000
19095823575649 1000000000
18048800926387 1000000000
17060779354093 1000000000
15768748767399 1000000000
30886037572930 1000000000
26814970558482 1000000000
8165534157289 1000000000
27914989206121 1000000000
34170089895536 1000000000
27764986366439 1000000000
145187181...

output:

result:

wrong answer 3rd numbers differ - expected: '758530203', found: '152929909'

Test #20:

score: 0

Wrong Answer

time: 2627ms

memory: 372516kb

input:

99999
71091006018203 1000000000
42267334298998 1000000000
53421686894439 1000000000
52992676205010 1000000000
49055576058012 1000000000
70721000416119 1000000000
43151374327143 1000000000
70716000332404 1000000000
51528640431406 1000000000
65945925001029 1000000000
39524135856472 1000000000
66414932...

output:

result:

wrong answer 5th numbers differ - expected: '56850092', found: '876836101'

Test #21:

score: 0

Wrong Answer

time: 2131ms

memory: 197844kb

input:

99999
43981987091230 1000000000
41793950053258 1000000000
23385527966154 1000000000
32049759202175 1000000000
48927065970165 1000000000
26694629471843 1000000000
27661655640242 1000000000
37241867113918 1000000000
49110069037684 1000000000
20323405372655 1000000000
43304975621086 1000000000
48021052...

output:

result:

wrong answer 3rd numbers differ - expected: '749574507', found: '406632471'

Test #22:

score: 0

Wrong Answer

time: 2243ms

memory: 213432kb

input:

99999
31159466866911 1000000000
28413414847308 1000000000
25948364344910 1000000000
31236468095715 1000000000
22036273821032 1000000000
24056321657736 1000000000
36031551606814 1000000000
37935581367999 1000000000
40624624246259 1000000000
18857191994835 1000000000
22179277697755 1000000000
29154428...

output:

result:

wrong answer 3rd numbers differ - expected: '281776724', found: '830094985'