QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#361174#8229. 栈XY_Eleven40 213ms32756kbC++236.1kb2024-03-22 21:15:272024-03-22 21:15:27

Judging History

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

  • [2024-03-22 21:15:27]
  • 评测
  • 测评结果:40
  • 用时:213ms
  • 内存:32756kb
  • [2024-03-22 21:15:27]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize(3)
#define DB double
#define LL long long
#define ULL unsigned long long
#define in128 __int128
#define cint const int
#define cLL const LL
#define For(z,e1,e2) for(int z=(e1);z<=(e2);z++)
#define Rof(z,e1,e2) for(int z=(e2);z>=(e1);z--)
#define For_(z,e1,e2) for(int z=(e1);z<(e2);z++)
#define Rof_(z,e1,e2) for(int z=(e2);z>(e1);z--)
#define inint(e) scanf("%d",&e)
#define inll(e) scanf("%lld",&e)
#define inpr(e1,e2) scanf("%d%d",&e1,&e2)
#define in3(e1,e2,e3) scanf("%d%d%d",&e1,&e2,&e3)
#define outint(e) printf("%d\n",e)
#define outint_(e) printf("%d%c",e," \n"[i==n])
#define outint2_(e,e1,e2) printf("%d%c",e," \n"[(e1)==(e2)])
#define outll(e) printf("%lld\n",e)
#define outll_(e) printf("%lld%c",e," \n"[i==n])
#define outll2_(e,e1,e2) printf("%lld%c",e," \n"[(e1)==(e2)])
#define exc(e) if(e) continue
#define stop(e) if(e) break
#define ret(e) if(e) return
#define ll(e) (1ll*(e))
#define pb push_back
#define ft first
#define sc second
#define clean(e) while(!e.empty()) e.pop()
#define all(ev) ev.begin(),ev.end()
#define sz(ev) ((int)ev.size())
#define debug(x) printf("%s=%d\n",#x,x)
#define x0 _x0_
#define y1 _y1_
#define ffo fflush(stdout)
cLL mod=998244353,G=404;
template <typename Type> void get_min(Type &w1,const Type w2) { if(w2<w1) w1=w2; }
template <typename Type> void get_max(Type &w1,const Type w2) { if(w2>w1) w1=w2; }
template <typename Type> Type up_div(Type w1,Type w2) { return (w1/w2+(w1%w2?1:0)); }
template <typename Type> Type gcd(Type X_,Type Y_) { Type R_=X_%Y_; while(R_) { X_=Y_; Y_=R_; R_=X_%Y_; } return Y_; }
template <typename Type> Type lcm(Type X_,Type Y_) { return (X_/gcd(X_,Y_)*Y_); }
template <typename Type> Type md(Type w1,const Type w2=mod) { w1%=w2; if(w1<0) w1+=w2; return w1; }
template <typename Type> Type md_(Type w1,const Type w2=mod) { w1%=w2; if(w1<=0) w1+=w2; return w1; }
void ex_gcd(LL &X_,LL &Y_,LL A_,LL B_)
{ if(!B_) { X_=1ll; Y_=0ll; return ; } ex_gcd(Y_,X_,B_,A_%B_); X_=md(X_,B_); Y_=(1ll-X_*A_)/B_; }
LL inv(LL A_,LL B_=mod) { LL X_=0ll,Y_=0ll; ex_gcd(X_,Y_,A_,B_); return X_; }
template <typename Type> void add(Type &w1,const Type w2,const Type M_=mod) { w1=md(w1+w2,M_); }
void mul(LL &w1,cLL w2,cLL M_=mod) { w1=md(w1*md(w2,M_),M_); }
template <typename Type> Type pw(Type X_,Type Y_,Type M_=mod) { Type S_=1; while(Y_) { if(Y_&1) mul(S_,X_,M_); Y_>>=1; mul(X_,X_,M_); } return S_; }
mt19937 gen(time(NULL)); int rd() { return abs((int)gen()); }
cint N=1.02e5;
int n,Q;
vector <pair<int,pair<LL,LL> > > q[N];
vector <int> v[N];
array <LL,2> a[N];
struct Node
{
    int l,r,mid;
    LL ls,rs,sum,sum2,lcnt;
}t[N<<2|1];
void bld(int p,int l,int r)
{
    int mid=l+r>>1;
    t[p]={l,r,mid,0ll,0ll,0ll,0ll,0ll};
    ret(l>=r);
    bld(p<<1,l,mid),bld(p<<1|1,mid+1,r);
}
LL ans[N];
bool vis[N],b[N];
int K;
void setf(int p,int k)
{
    if(vis[k])
        t[p].ls=t[p].rs=t[p].sum=0ll;
    else
    {
        if(b[k]) t[p].rs=a[k][0],t[p].sum=a[k][0]*a[k][1];
        else t[p].ls=a[k][0];
    }
    vis[k]=!vis[k];
}
LL work(int p,LL c)
{
    // printf("work [%d,%d]:%lld,%lld\n",t[p].l,t[p].r,t[p].lcnt,c);
    if(t[p].l>=t[p].r) return c*a[t[p].l][1];
    if(c<=t[p].lcnt) return work(p<<1,c);
    else return (work(p<<1|1,c-t[p].lcnt)+t[p].sum2);
}
pair <array <LL,2>,LL> sum(int p1,int p2)
{
    if(t[p2].ls>=t[p1].rs) return {{t[p1].ls+(t[p2].ls-t[p1].rs),t[p2].rs},t[p2].sum};
    return {{t[p1].ls,t[p2].rs+(t[p1].rs-t[p2].ls)},t[p2].sum+work(p1,t[p1].rs-t[p2].ls)};
}
void pup(int p)
{
    t[p].sum2=work(p<<1,t[p].lcnt=max(t[p<<1].rs-t[p<<1|1].ls,0ll));
    auto w=sum(p<<1,p<<1|1);
    t[p].ls=w.ft[0],t[p].rs=w.ft[1],t[p].sum=w.sc;
}
void change(int p)
{
    if(t[p].l>=t[p].r)
    {
        setf(p,K);
        return ;
    }
    change(p<<1|(K>t[p].mid));
    pup(p);
}
void Change(int k)
{
    K=k;
    change(1);
}
int L,R;
vector <int> g;
void qry(int p)
{
    if(L<=t[p].l&&t[p].r<=R)
    {
        g.pb(p);
        return ;
    }
    if(L<=t[p].mid) qry(p<<1);
    if(R>t[p].mid) qry(p<<1|1);
}
stack <pair<int,LL> > st;
LL Qry(int k,LL c)
{
    // printf("\nquery %d,%lld\n",k,c);
    L=1,R=k,g.clear();
    qry(1);
    clean(st);
    LL sum=0ll;
    for(auto i:g)
    {
        LL w=t[i].ls;
        while(!st.empty()&&w>=st.top().sc)
            w-=st.top().sc,st.pop();
        if(!st.empty()) st.top().sc-=w;
        st.push({i,t[i].rs});
    }
    while(!st.empty())
    {
        int p=st.top().ft; LL c2=st.top().sc;
        get_min(c2,c); c-=c2;
        st.pop();
        // printf("[%d,%d]:%lld(%lld)\n",t[p].l,t[p].r,c2,t[p].rs);
        sum+=work(p,c2);
    }
    return sum;
}
void print(int p)
{
    // printf("print %d:[%d,%d] %lld(%lld)&%lld\n",p,t[p].l,t[p].r,t[p].ls,t[p].lcnt,t[p].rs);
    ret(t[p].l>=t[p].r);
    print(p<<1),print(p<<1|1);
}
void main_solve()
{
    inpr(n,Q);
    int opt;
    For(i,1,Q)
    {
        inint(opt);
        if(opt==3)
        {
            int k; LL l,r;
            scanf("%d%lld%lld",&k,&l,&r);
            q[k].pb({i,{l,r}});
        }
        else
        {
            int l,r; inpr(l,r);
            v[l].pb(i),v[r+1].pb(i);
            if(opt==1)
            {
                LL c,w; scanf("%lld%lld",&c,&w);
                a[i]={c,w};
            }
            else
            {
                LL c; scanf("%lld",&c);
                a[i]={c,0ll};
            }
            b[i]=(opt==1);
        }
    }
    bld(1,1,Q);
    memset(ans,0xff,(Q+1)*sizeof(LL));
    For(i,1,n)
    {
        // printf("\ni=%d\n",i);
        for(auto j:v[i]) Change(j);
        for(auto [id,c]:q[i])
            ans[id]=Qry(id,c.sc)-Qry(id,c.ft-1ll);
        // printf("\n"); print(1);
    }
    For(i,1,Q) if(ans[i]!=-1ll)
        outll(ans[i]);
}
int main()
{
    // ios::sync_with_stdio(0); cin.tie(0);
    // freopen("in.txt","r",stdin);
    // freopen("out1.txt","w",stdout);
    // rsand(time(NULL));
    // main_init();
    // int _; inint(_); For(__,1,_) // T>1 ?
        // printf("\n------------\n\n"),
        main_solve();
    return 0;
}
/*
2 2 2 1 1
*/

详细

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 6ms
memory: 9392kb

input:

4907 4910
2 763 3330 1
3 307 1 1
1 2262 3430 22699 89397
1 1915 4000 51541 67587
2 212 2990 9763
2 1086 2162 1
2 1813 4496 16760
1 51 2796 68005 99390
1 1267 1519 74236 66178
3 1768 23808 54314
2 900 4122 27758
3 3287 17350 28989
2 3277 4024 3633
2 444 4866 1
2 353 4219 1061
1 987 3141 99906 17320
2...

output:

0
3032090730
903396180
471569175
200648623
98486697
214102593
123945
113900940
61782451
0
0
0
762429740
321140700
661791594
97825657
5854255411
0
1747798348
6502828468
2351056740
122249391
283261500
5250788038
1145132507
140071334
0
118545795
4845967480
8355899456
84280112
128431809
4992966775
98734...

result:

wrong answer 7th numbers differ - expected: '647114751', found: '214102593'

Subtask #2:

score: 0
Wrong Answer

Test #6:

score: 0
Wrong Answer
time: 206ms
memory: 30892kb

input:

99999 99998
1 5026 18575 27178 90423
3 30623 1 1
3 76936 1 1
1 77021 95683 84664 24734
1 46085 74886 40512 11266
3 5048 8594 22468
1 53318 77721 97151 70784
1 70645 91192 37556 13013
1 56752 56940 91812 62887
1 7928 34576 87339 69404
3 74875 32807 100970
3 22338 17221 25771
3 21421 20602 57957
3 717...

output:

0
0
1254619125
2139315110
593473604
2592655824
3657975552
5652513833
110091352
1226646296
1989326852
238600374
6208421260
1133345895
925424768
14415119878
2900664601
15486317750
28487172978
4722824224
16341882407
899316516
38935050954
988382364
13466737951
9077631207
2449683584
5875277101
7875260146...

result:

wrong answer 4th numbers differ - expected: '4366274868', found: '2139315110'

Subtask #3:

score: 16
Accepted

Test #12:

score: 16
Accepted
time: 131ms
memory: 30776kb

input:

100000 99993
1 47773 70467 16065 1
2 52349 78446 2304
3 40821 1 1
1 40216 93069 78144 1
1 41089 43671 76025 1
2 35263 68629 31066
3 79881 13534 57327
3 5556 1 1
2 21962 38192 1
1 664 58116 9417 1
3 28089 6039 7989
2 88500 90302 9946
3 63215 49410 60770
2 11069 89527 57581
2 70303 97603 12363
1 3420 ...

output:

0
43794
0
1951
11361
129
898
29245
7969
1947
34972
16405
59952
123666
24537
68209
34537
0
32225
37527
0
31810
16824
96178
14285
300941
57614
1602
129470
61935
4068
114182
17609
152949
26099
179359
250368
4796
183349
125791
17414
61871
42058
0
2698
183297
23029
54464
0
26259
204595
35604
0
0
18437
29...

result:

ok 33281 numbers

Test #13:

score: 0
Accepted
time: 126ms
memory: 30812kb

input:

100000 99999
3 11279 1 1
1 21196 82827 47041 1
2 58608 97529 1
2 22065 32528 37154
1 2138 16260 96858 1
1 25755 42875 82334 1
1 31799 48594 28327 1
3 58271 16371 33060
1 9407 50398 53680 1
2 40505 54132 176725
2 4626 22919 41250
2 28476 63110 133245
2 501 87564 1
2 5927 27401 96494
2 27254 64078 1
2...

output:

0
16690
27551
1442
4671
0
35160
4953
1559
3430
1768
0
0
11628
0
0
2495
13673
0
0
162093
135864
330
17312
0
29074
0
0
0
33641
51926
7051
0
0
42277
0
44110
543
12418
51322
9338
89794
9387
44052
43969
170272
42203
209676
5275
15969
11537
29757
26609
8288
33600
0
21384
48804
75598
11624
67508
10170
1751...

result:

ok 33467 numbers

Test #14:

score: 0
Accepted
time: 164ms
memory: 30780kb

input:

99993 99998
3 67041 1 1
3 6929 1 1
2 17524 32038 1
2 61604 73005 1
3 89616 1 1
2 40031 62338 1
3 58255 1 1
1 13009 67563 20939 1
1 73959 97229 47418 1
2 60834 61638 3740
2 29078 66369 1909
3 20355 4984 7284
2 75885 86625 3998
1 58692 90189 3242 1
3 99600 1 1
1 4102 8018 16478 1
3 53676 3918 8517
3 6...

output:

0
0
0
0
2301
0
4600
1472
56471
13213
0
143912
24988
0
59240
0
0
65385
5137
154745
70944
42704
209563
9676
121308
24627
52979
49278
37462
16444
0
1611
409040
392695
111628
265718
65783
55560
11142
45479
32621
118811
0
27594
239805
284844
19955
220309
8044
161759
1982
53200
41530
102413
43466
28624
17...

result:

ok 33389 numbers

Test #15:

score: 0
Accepted
time: 163ms
memory: 30724kb

input:

99991 99996
1 47657 83825 20467 1
2 18475 94316 1
1 45137 56194 42134 1
2 62287 64784 3656
1 34371 82222 66403 1
2 26982 76957 4461
2 1186 62584 1
2 63744 85641 5313
1 20658 59024 63800 1
2 51424 82606 5804
2 90768 91321 1
3 15951 1 1
2 51955 91548 1298
3 37870 8860 39509
3 8317 1 1
3 308 1 1
1 1977...

output:

0
30650
0
0
0
0
0
52497
2540
51822
0
22469
45077
10570
146261
11438
80060
21311
114935
197491
113332
156089
207620
36833
104730
21761
58044
72459
72699
105703
297859
98381
351013
75662
42544
50509
161825
375089
22703
209315
121760
4317
496943
121741
116864
11213
87742
871
452690
54302
100601
39830
2...

result:

ok 33262 numbers

Test #16:

score: 0
Accepted
time: 198ms
memory: 30724kb

input:

99997 99999
2 53252 91242 1
1 57337 88934 37260 1
1 16834 34642 93492 1
2 81166 94101 6093
1 46770 56947 41803 1
2 70882 88729 2179
2 55489 59818 1
1 29212 60579 61103 1
3 37904 1447 28743
1 68609 95313 51191 1
1 41758 51157 38733 1
3 57276 44404 49850
1 53448 66120 27464 1
1 64716 86889 8186 1
1 30...

output:

27297
5447
87454
7764
0
36668
9059
202784
226798
35791
44217
20176
425699
841344
314555
628121
279373
862035
1237442
638303
225509
1013325
143603
280017
469785
168019
102756
1008786
266597
5507
31097
1524290
288879
523157
706592
434088
1052960
282317
254606
633715
493060
281268
273353
139218
259977
...

result:

ok 16863 numbers

Subtask #4:

score: 24
Accepted

Test #17:

score: 24
Accepted
time: 148ms
memory: 31032kb

input:

99999 99996
3 77889 1 10000000000
1 6316 86327 89644 386
3 9260 1 10000000000
2 2603 47234 69717
2 20260 73011 19290
2 62477 81233 26127
1 50140 68508 37004 98794
2 14449 22788 16063
1 43860 84932 50375 21777
1 67345 94584 28202 66610
2 661 68654 1
1 14411 94422 82738 61196
1 16563 94416 4920 38408
...

output:

0
34602584
0
0
27739639583
1363823412
0
1902514434
1902514434
2147553884
1902514434
15794375094
0
4192446657
15797478185
13141921145
0
6351944090
5775183021
363222594
1995572111
2193350882
0
6843261316
5508935691
250667843
0
14181223499
7734049978
21958753162
12852564544
4496343819
15011219087
11331...

result:

ok 33196 numbers

Test #18:

score: 0
Accepted
time: 142ms
memory: 32756kb

input:

99993 100000
3 61460 1 10000000000
1 24890 92871 3803 26680
1 13860 37123 61687 5252
1 8370 24754 70468 14033
3 89253 1 10000000000
3 19857 1 10000000000
1 46250 80211 68621 64496
2 51133 69614 60852
1 6552 42728 61410 66775
3 16111 1 10000000000
3 48406 1 10000000000
2 46319 62460 3834
3 11455 1 10...

output:

0
101464040
1312857568
5413510318
4527244056
5089530194
4526096914
0
4475006240
7393292878
6354306906
5962661320
1073478334
14785061024
124598326
5273378126
3143834350
5315386486
567431731
3354264361
0
8452414800
16197376342
15594421332
7644906667
10259594309
15786872317
21575834611
25614641754
0
56...

result:

ok 33334 numbers

Test #19:

score: 0
Accepted
time: 162ms
memory: 30744kb

input:

99998 99996
3 40534 1 10000000000
1 89230 99016 8691 49307
1 73075 80610 27269 1760
1 80632 96125 13027 41376
1 55057 71990 82693 44377
2 11566 27301 1
2 23704 47061 1
1 67323 97867 14275 31136
1 11736 72566 78826 36301
3 70013 1 10000000000
1 23701 76122 6240 56626
2 71627 75885 1100
3 852 1 100000...

output:

0
6975596287
0
0
2144844585
6718561947
6718561947
2158130751
2917409114
3686398232
3317159253
1336852308
8373494196
2102154609
2709470190
1740124736
7659185913
1508488055
4242893725
8408091078
11875396012
18171183033
0
14595335642
18243076995
18521970659
18538979218
18538979218
20876408549
136521304...

result:

ok 33368 numbers

Test #20:

score: 0
Accepted
time: 170ms
memory: 30692kb

input:

99995 99996
3 45022 1 10000000000
2 3423 75909 1
1 54871 80611 9913 46243
2 12223 64484 1
1 12991 92385 39637 71608
3 20817 1 10000000000
3 14810 1 10000000000
3 85611 1 10000000000
3 34957 1 10000000000
3 22540 1 10000000000
2 11680 85376 4565
2 37283 97824 2191
3 84953 1 10000000000
3 56562 1 1000...

output:

0
2838326296
2838326296
2838326296
2838326296
2838326296
2354542648
2812903264
2631018944
2518569019
2681433168
2439582449
0
2681433168
2596475577
2439582449
0
7076261394
4449272647
15245942497
17667326760
15245942497
17667326760
17015058013
16860972874
42913399354
6034264601
96968820
12777724000
15...

result:

ok 33362 numbers

Test #21:

score: 0
Accepted
time: 213ms
memory: 32488kb

input:

99997 99996
3 68591 1 10000000000
2 11039 97222 1
1 34581 58556 66216 49214
1 42922 79247 32694 462
2 53032 58124 10301
3 34753 1 10000000000
1 22670 52566 70087 14019
3 55338 1 10000000000
3 30269 1 10000000000
1 4720 84384 20451 10356
3 11823 1 10000000000
1 37895 41892 96036 45498
2 19158 57043 7...

output:

0
3258754224
3269099790
982549653
211790556
1278106321
13591686831
9174283336
13929158983
10709860696
11476736634
24202776273
22066287959
23834159039
19695058244
28492871831
46736921586
859941225
5996946536
32463961710
31748786358
726580728
43724564767
39567498070
43724564767
57942980296
41944974287...

result:

ok 16689 numbers

Subtask #5:

score: 0
Skipped

Dependency #1:

0%