oj.uz

Submission #1088550

# Submission time Handle Problem Language Result Execution time Memory
1088550 2024-09-14T15:21:00 Z vjudge1 Progression (NOI20_progression) C++17
68 / 100
 887 ms 121852 KB 
#include<bits/stdc++.h>
#define taskname ""
#define el '\n'
#define fi first
#define sc second
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
#define int ll
using namespace std;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
#define Faster ios_base::sync_with_stdio(false);cin.tie(0);
using namespace std;
const int maxn=3e5+3;
const int INF=LLONG_MAX;
int n,q,a[maxn],b[maxn];
struct segtree
{
    int sett[4*maxn],add[4*maxn],mul[4*maxn];
    void cons(int id,int cl,int cr)
    {
        if(cl==cr)
        {
            sett[id]=a[cl];
            add[id]=0;
            mul[id]=0;
            return;
        }
        int mid=(cl+cr)/2;
        cons(2*id,cl,mid);
        cons(2*id+1,mid+1,cr);
        add[id]=mul[id]=0;
        sett[id]=INF;
    }
    void down(int id)
    {
        if(sett[id]!=INF)
        {
            sett[2*id]=sett[id*2+1]=sett[id];
            add[2*id]=add[id*2+1]=0;
            mul[2*id]=mul[id*2+1]=0;
            sett[id]=INF;
        }
        add[id*2]+=add[id];
        add[id*2+1]+=add[id];
        add[id]=0;
        mul[id*2]+=mul[id];
        mul[id*2+1]+=mul[id];
        mul[id]=0;
    }
    void updateset(int id,int cl,int cr,int l,int r,int val)
    {
        if(cl>r||cr<l) return;
        if(cl>=l&&cr<=r)
        {
            sett[id]=val;
            add[id]=0;
            mul[id]=0;
            return;
        }
        int mid=(cl+cr)/2;
        down(id);
        updateset(2*id,cl,mid,l,r,val);
        updateset(2*id+1,mid+1,cr,l,r,val);
    }
    void updateadd(int id,int cl,int cr,int l,int r,int val)
    {
        if(cl>r||cr<l) return;
        if(cl>=l&&cr<=r)
        {
            add[id]+=val;
            return;
        }
        int mid=(cl+cr)/2;
        down(id);
        updateadd(2*id,cl,mid,l,r,val);
        updateadd(2*id+1,mid+1,cr,l,r,val);
    }
    void updatemul(int id,int cl,int cr,int l,int r,int val)
    {
        if(cl>r||cr<l) return;
        if(cl>=l&&cr<=r)
        {
            mul[id]+=val;
            return;
        }
        int mid=(cl+cr)/2;
        down(id);
        updatemul(2*id,cl,mid,l,r,val);
        updatemul(2*id+1,mid+1,cr,l,r,val);
    }
    int get(int id,int cl,int cr,int pos)
    {
        if(cl==cr)
        {
//            if(sett[id]==INF) return add[id]+pos*mul[id];
            return sett[id]+add[id]+pos*mul[id];
        }
        int mid=(cl+cr)/2;
        down(id);
        if(pos<=mid) return get(2*id,cl,mid,pos);
        else return get(2*id+1,mid+1,cr,pos);
    }
}f;
struct node
{
    pii pre,suf,opt;
    int l;
};
node operator +(node a,node b)
{
    node res;
    res.l=a.l+b.l;
    if(a.l==0) return b;
    if(b.l==0) return a;
    if(a.pre.sc==a.l&&(a.pre.fi==b.pre.fi))
    {
        res.pre={a.pre.fi,a.l+b.pre.sc};
    }
    else res.pre=a.pre;
    if(b.suf.sc==b.l&&(b.suf.fi==a.suf.fi))
    {
        res.suf={b.suf.fi,b.l+a.suf.sc};
    }
    else res.suf=b.suf;
    res.opt=a.opt;
    if(res.opt.sc<b.opt.sc) res.opt=b.opt;
    if(a.suf.fi==b.pre.fi)
    {
        if(a.suf.sc+b.pre.sc>res.opt.sc)
        {
            res.opt={a.suf.fi,a.suf.sc+b.pre.sc};
        }
    }
    return res;
}
struct seggtree
{
    node ST[4*maxn];
    int laz[4*maxn],add[maxn*4];
    void down(int id)
    {
        if(laz[id]!=INF)
        {
            laz[id*2]=laz[id];
            laz[id*2+1]=laz[id];
            ST[id*2]={{laz[id],ST[id*2].l},{laz[id],ST[id*2].l},{laz[id],ST[id*2].l},ST[id*2].l};
            ST[id*2+1]={{laz[id],ST[id*2+1].l},{laz[id],ST[id*2+1].l},{laz[id],ST[id*2+1].l},ST[id*2+1].l};
            add[id*2]=add[2*id+1]=0;
            laz[id]=INF;
        }
        {
            ST[id*2].pre.fi+=add[id];
            ST[id*2].opt.fi+=add[id];
            ST[id*2].suf.fi+=add[id];
            ST[id*2+1].pre.fi+=add[id];
            ST[id*2+1].opt.fi+=add[id];
            ST[id*2+1].suf.fi+=add[id];
            add[2*id]+=add[id];
            add[2*id+1]+=add[id];
            add[id]=0;
        }
    }
    void cons(int id,int cl,int cr)
    {
        if(cl==cr)
        {
            ST[id]={{b[cl],1},{b[cl],1},{b[cl],1},1};
            laz[id]=b[cl];
            return;
        }
        int mid=(cl+cr)/2;
        cons(2*id,cl,mid);
        cons(2*id+1,mid+1,cr);
        ST[id]=ST[id*2]+ST[id*2+1];
        laz[id]=INF;
    }
    void update(int id,int cl,int cr,int l,int r,int val)
    {
        if(cl>r||cr<l) return;
        if(cl>=l&&cr<=r)
        {
            ST[id].opt.fi+=val;
            ST[id].pre.fi+=val;
            ST[id].suf.fi+=val;
            add[id]+=val;
            return;
        }
        int mid=(cl+cr)/2;
        down(id);
        update(2*id,cl,mid,l,r,val);
        update(2*id+1,mid+1,cr,l,r,val);
        ST[id]=ST[id*2]+ST[id*2+1];
    }
    void rupdate(int id,int cl,int cr,int l,int r,int val)
    {
        if(cl>r||cr<l) return;
        if(cl>=l&&cr<=r)
        {
            laz[id]=val;
            ST[id]={{laz[id],ST[id].l},{laz[id],ST[id].l},{laz[id],ST[id].l},ST[id].l};
            return;
        }
        int mid=(cl+cr)/2;
        down(id);
        rupdate(2*id,cl,mid,l,r,val);
        rupdate(2*id+1,mid+1,cr,l,r,val);
        ST[id]=ST[id*2]+ST[id*2+1];
    }
    node get(int id,int cl,int cr,int l,int r)
    {
        if(cl>r||cr<l) return {{0,0},{0,0},{0,0},0};
        if(cl>=l&&cr<=r) return ST[id];
        int mid=(cl+cr)/2;
        down(id);
        node siu=get(2*id,cl,mid,l,r)+get(2*id+1,mid+1,cr,l,r);
        return siu;
    }
}g;
signed main()
{
    if (fopen(taskname".INP","r"))
    {
        freopen(taskname".INP","r",stdin);
        freopen(taskname".OUT","w",stdout);
    }
    Faster
    cin>>n>>q;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        b[i]=a[i]-a[i-1];
    }
    f.cons(1,1,n);
    g.cons(1,1,n);
    for(int i=1;i<=q;i++)
    {
        int t,l,r,s,c;
        cin>>t;
        if(t==1)
        {
            cin>>l>>r>>s>>c;
            g.update(1,1,n,l,l,s);
            if(r<n) g.update(1,1,n,r+1,r+1,-(s+c*(r-l)));
            g.update(1,1,n,l+1,r,c);
            f.updateadd(1,1,n,l,r,s-l*c);
            f.updatemul(1,1,n,l,r,c);
            if(n<=1000)
            {
                for(int j=l;j<=r;j++)
                {
                    a[j]+=s+(j-l)*c;
                }
            }
        }
        else if(t==2)
        {
            cin>>l>>r>>s>>c;
            int xx;
            if(l>1)
            {
                xx=f.get(1,1,n,l-1);
                if(n<=1000) xx=a[l-1];
                g.rupdate(1,1,n,l,l,s-xx);
            }
            if(r<n)
            {
                xx=f.get(1,1,n,r+1);
                if(n<=1000) xx=a[r+1];
                g.rupdate(1,1,n,r+1,r+1,xx-(s+(r-l)*c));
            }
            g.rupdate(1,1,n,l+1,r,c);
            f.updateset(1,1,n,l,r,s-l*c);
            f.updatemul(1,1,n,l,r,c);
            if(n<=1000)
            {
                for(int j=l;j<=r;j++)
                {
                    a[j]=s+(j-l)*c;
                }
            }
        }
        else
        {
            cin>>l>>r;
            if(l==r) cout<<1<<"\n";
            else
            {
                node siu=g.get(1,1,n,l+1,r);
                cout<<siu.opt.sc+1<<"\n";
            }

        }
    }

}

Compilation message

Progression.cpp: In function 'int main()':
Progression.cpp:225:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  225 |         freopen(taskname".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
Progression.cpp:226:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  226 |         freopen(taskname".OUT","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 339 ms 112212 KB Output is correct
2 Correct 157 ms 69456 KB Output is correct
3 Correct 145 ms 69456 KB Output is correct
4 Correct 154 ms 69384 KB Output is correct
5 Correct 151 ms 69456 KB Output is correct
6 Correct 145 ms 69444 KB Output is correct
7 Correct 145 ms 69460 KB Output is correct
8 Correct 28 ms 66136 KB Output is correct
9 Correct 25 ms 66096 KB Output is correct
10 Correct 26 ms 66144 KB Output is correct
11 Correct 336 ms 112212 KB Output is correct
12 Correct 348 ms 112120 KB Output is correct
13 Correct 344 ms 112448 KB Output is correct
14 Correct 340 ms 112704 KB Output is correct
15 Correct 332 ms 112548 KB Output is correct
16 Correct 350 ms 112208 KB Output is correct
17 Correct 328 ms 112208 KB Output is correct
18 Correct 340 ms 112208 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 66140 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 315 ms 118972 KB Output is correct
2 Correct 109 ms 68720 KB Output is correct
3 Correct 120 ms 68944 KB Output is correct
4 Correct 83 ms 68864 KB Output is correct
5 Correct 100 ms 68948 KB Output is correct
6 Correct 100 ms 69064 KB Output is correct
7 Correct 99 ms 68948 KB Output is correct
8 Correct 21 ms 66140 KB Output is correct
9 Correct 22 ms 66140 KB Output is correct
10 Correct 22 ms 66108 KB Output is correct
11 Correct 335 ms 117444 KB Output is correct
12 Correct 313 ms 118924 KB Output is correct
13 Correct 336 ms 117592 KB Output is correct
14 Correct 331 ms 117676 KB Output is correct
15 Correct 304 ms 118896 KB Output is correct
16 Correct 351 ms 119380 KB Output is correct
17 Correct 359 ms 119448 KB Output is correct
18 Correct 358 ms 119636 KB Output is correct
19 Correct 320 ms 118832 KB Output is correct
20 Correct 305 ms 118864 KB Output is correct
21 Correct 305 ms 118816 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 703 ms 121720 KB Output is correct
2 Correct 167 ms 69712 KB Output is correct
3 Correct 165 ms 69432 KB Output is correct
4 Correct 186 ms 69460 KB Output is correct
5 Correct 191 ms 69732 KB Output is correct
6 Correct 166 ms 69460 KB Output is correct
7 Correct 166 ms 69456 KB Output is correct
8 Correct 21 ms 66132 KB Output is correct
9 Correct 22 ms 66140 KB Output is correct
10 Correct 23 ms 66128 KB Output is correct
11 Correct 749 ms 118308 KB Output is correct
12 Correct 732 ms 121820 KB Output is correct
13 Correct 759 ms 118496 KB Output is correct
14 Correct 736 ms 118392 KB Output is correct
15 Correct 700 ms 121684 KB Output is correct
16 Correct 773 ms 121768 KB Output is correct
17 Correct 827 ms 121680 KB Output is correct
18 Correct 826 ms 121852 KB Output is correct
19 Correct 709 ms 121656 KB Output is correct
20 Correct 716 ms 121572 KB Output is correct
21 Correct 761 ms 121732 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 315 ms 118972 KB Output is correct
2 Correct 109 ms 68720 KB Output is correct
3 Correct 120 ms 68944 KB Output is correct
4 Correct 83 ms 68864 KB Output is correct
5 Correct 100 ms 68948 KB Output is correct
6 Correct 100 ms 69064 KB Output is correct
7 Correct 99 ms 68948 KB Output is correct
8 Correct 21 ms 66140 KB Output is correct
9 Correct 22 ms 66140 KB Output is correct
10 Correct 22 ms 66108 KB Output is correct
11 Correct 335 ms 117444 KB Output is correct
12 Correct 313 ms 118924 KB Output is correct
13 Correct 336 ms 117592 KB Output is correct
14 Correct 331 ms 117676 KB Output is correct
15 Correct 304 ms 118896 KB Output is correct
16 Correct 351 ms 119380 KB Output is correct
17 Correct 359 ms 119448 KB Output is correct
18 Correct 358 ms 119636 KB Output is correct
19 Correct 320 ms 118832 KB Output is correct
20 Correct 305 ms 118864 KB Output is correct
21 Correct 305 ms 118816 KB Output is correct
22 Correct 841 ms 121172 KB Output is correct
23 Correct 177 ms 69344 KB Output is correct
24 Correct 160 ms 69344 KB Output is correct
25 Correct 160 ms 69460 KB Output is correct
26 Correct 166 ms 69368 KB Output is correct
27 Correct 174 ms 69504 KB Output is correct
28 Correct 169 ms 69288 KB Output is correct
29 Correct 25 ms 66140 KB Output is correct
30 Correct 23 ms 66136 KB Output is correct
31 Correct 22 ms 66148 KB Output is correct
32 Correct 828 ms 118352 KB Output is correct
33 Correct 806 ms 121184 KB Output is correct
34 Correct 823 ms 118416 KB Output is correct
35 Correct 887 ms 118356 KB Output is correct
36 Correct 660 ms 118096 KB Output is correct
37 Correct 625 ms 118124 KB Output is correct
38 Correct 634 ms 118100 KB Output is correct
39 Correct 761 ms 121168 KB Output is correct
40 Correct 809 ms 121340 KB Output is correct
41 Correct 796 ms 121176 KB Output is correct
42 Correct 862 ms 121264 KB Output is correct
43 Correct 803 ms 121172 KB Output is correct
44 Correct 755 ms 121224 KB Output is correct
45 Correct 776 ms 121172 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 339 ms 112212 KB Output is correct
2 Correct 157 ms 69456 KB Output is correct
3 Correct 145 ms 69456 KB Output is correct
4 Correct 154 ms 69384 KB Output is correct
5 Correct 151 ms 69456 KB Output is correct
6 Correct 145 ms 69444 KB Output is correct
7 Correct 145 ms 69460 KB Output is correct
8 Correct 28 ms 66136 KB Output is correct
9 Correct 25 ms 66096 KB Output is correct
10 Correct 26 ms 66144 KB Output is correct
11 Correct 336 ms 112212 KB Output is correct
12 Correct 348 ms 112120 KB Output is correct
13 Correct 344 ms 112448 KB Output is correct
14 Correct 340 ms 112704 KB Output is correct
15 Correct 332 ms 112548 KB Output is correct
16 Correct 350 ms 112208 KB Output is correct
17 Correct 328 ms 112208 KB Output is correct
18 Correct 340 ms 112208 KB Output is correct
19 Incorrect 25 ms 66140 KB Output isn't correct
20 Halted 0 ms 0 KB -