oj.uz

Submission #1088517

# Submission time Handle Problem Language Result Execution time Memory
1088517 2024-09-14T14:35:44 Z vjudge1 Progression (NOI20_progression) C++17
55 / 100
 828 ms 121936 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;
        }
        else
        {
            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];
        }
    }
    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]=INF;
            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);
        }
        else if(t==2)
        {
            cin>>l>>r>>s>>c;
            int xx;
            if(l>1)
            {
                xx=f.get(1,1,n,l-1);
                g.rupdate(1,1,n,l,l,s-xx);
            }
            if(r<n)
            {
                xx=f.get(1,1,n,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);
        }
        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 325 ms 112208 KB Output is correct
2 Correct 127 ms 69460 KB Output is correct
3 Correct 128 ms 69460 KB Output is correct
4 Correct 136 ms 69348 KB Output is correct
5 Correct 128 ms 69316 KB Output is correct
6 Correct 127 ms 69464 KB Output is correct
7 Correct 138 ms 69460 KB Output is correct
8 Correct 24 ms 66100 KB Output is correct
9 Correct 24 ms 66272 KB Output is correct
10 Correct 31 ms 66076 KB Output is correct
11 Correct 343 ms 112296 KB Output is correct
12 Correct 326 ms 112276 KB Output is correct
13 Correct 344 ms 112720 KB Output is correct
14 Correct 322 ms 112924 KB Output is correct
15 Correct 322 ms 112464 KB Output is correct
16 Correct 329 ms 112120 KB Output is correct
17 Correct 333 ms 112212 KB Output is correct
18 Correct 316 ms 112208 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 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 332 ms 118868 KB Output is correct
2 Correct 114 ms 68948 KB Output is correct
3 Correct 105 ms 68688 KB Output is correct
4 Correct 80 ms 68692 KB Output is correct
5 Correct 111 ms 68944 KB Output is correct
6 Correct 102 ms 68944 KB Output is correct
7 Correct 100 ms 68948 KB Output is correct
8 Correct 26 ms 66140 KB Output is correct
9 Correct 24 ms 66140 KB Output is correct
10 Correct 23 ms 66184 KB Output is correct
11 Correct 356 ms 117496 KB Output is correct
12 Correct 318 ms 118860 KB Output is correct
13 Correct 357 ms 117580 KB Output is correct
14 Correct 361 ms 117584 KB Output is correct
15 Correct 331 ms 118864 KB Output is correct
16 Correct 361 ms 119376 KB Output is correct
17 Correct 358 ms 119352 KB Output is correct
18 Correct 357 ms 119656 KB Output is correct
19 Correct 328 ms 118836 KB Output is correct
20 Correct 316 ms 118936 KB Output is correct
21 Correct 324 ms 118864 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 792 ms 121680 KB Output is correct
2 Correct 182 ms 69544 KB Output is correct
3 Correct 164 ms 69572 KB Output is correct
4 Correct 169 ms 69464 KB Output is correct
5 Correct 163 ms 69572 KB Output is correct
6 Correct 167 ms 69456 KB Output is correct
7 Correct 177 ms 69468 KB Output is correct
8 Correct 26 ms 66136 KB Output is correct
9 Correct 25 ms 66140 KB Output is correct
10 Correct 25 ms 66140 KB Output is correct
11 Correct 828 ms 118352 KB Output is correct
12 Correct 769 ms 121640 KB Output is correct
13 Correct 765 ms 118348 KB Output is correct
14 Correct 741 ms 118364 KB Output is correct
15 Correct 749 ms 121684 KB Output is correct
16 Correct 765 ms 121684 KB Output is correct
17 Correct 771 ms 121892 KB Output is correct
18 Correct 788 ms 121788 KB Output is correct
19 Correct 748 ms 121936 KB Output is correct
20 Correct 746 ms 121648 KB Output is correct
21 Correct 754 ms 121688 KB Output is correct

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 332 ms 118868 KB Output is correct
2 Correct 114 ms 68948 KB Output is correct
3 Correct 105 ms 68688 KB Output is correct
4 Correct 80 ms 68692 KB Output is correct
5 Correct 111 ms 68944 KB Output is correct
6 Correct 102 ms 68944 KB Output is correct
7 Correct 100 ms 68948 KB Output is correct
8 Correct 26 ms 66140 KB Output is correct
9 Correct 24 ms 66140 KB Output is correct
10 Correct 23 ms 66184 KB Output is correct
11 Correct 356 ms 117496 KB Output is correct
12 Correct 318 ms 118860 KB Output is correct
13 Correct 357 ms 117580 KB Output is correct
14 Correct 361 ms 117584 KB Output is correct
15 Correct 331 ms 118864 KB Output is correct
16 Correct 361 ms 119376 KB Output is correct
17 Correct 358 ms 119352 KB Output is correct
18 Correct 357 ms 119656 KB Output is correct
19 Correct 328 ms 118836 KB Output is correct
20 Correct 316 ms 118936 KB Output is correct
21 Correct 324 ms 118864 KB Output is correct
22 Incorrect 770 ms 121148 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 325 ms 112208 KB Output is correct
2 Correct 127 ms 69460 KB Output is correct
3 Correct 128 ms 69460 KB Output is correct
4 Correct 136 ms 69348 KB Output is correct
5 Correct 128 ms 69316 KB Output is correct
6 Correct 127 ms 69464 KB Output is correct
7 Correct 138 ms 69460 KB Output is correct
8 Correct 24 ms 66100 KB Output is correct
9 Correct 24 ms 66272 KB Output is correct
10 Correct 31 ms 66076 KB Output is correct
11 Correct 343 ms 112296 KB Output is correct
12 Correct 326 ms 112276 KB Output is correct
13 Correct 344 ms 112720 KB Output is correct
14 Correct 322 ms 112924 KB Output is correct
15 Correct 322 ms 112464 KB Output is correct
16 Correct 329 ms 112120 KB Output is correct
17 Correct 333 ms 112212 KB Output is correct
18 Correct 316 ms 112208 KB Output is correct
19 Incorrect 23 ms 66140 KB Output isn't correct
20 Halted 0 ms 0 KB -