oj.uz

Submission #1088506

# Submission time Handle Problem Language Result Execution time Memory
1088506 2024-09-14T14:20:41 Z vjudge1 Progression (NOI20_progression) C++17
55 / 100
 817 ms 121940 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;
        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:224:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  224 |         freopen(taskname".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
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".OUT","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 316 ms 112380 KB Output is correct
2 Correct 146 ms 69460 KB Output is correct
3 Correct 133 ms 69260 KB Output is correct
4 Correct 127 ms 69460 KB Output is correct
5 Correct 120 ms 69456 KB Output is correct
6 Correct 119 ms 69316 KB Output is correct
7 Correct 124 ms 69460 KB Output is correct
8 Correct 30 ms 66140 KB Output is correct
9 Correct 21 ms 66140 KB Output is correct
10 Correct 22 ms 66168 KB Output is correct
11 Correct 316 ms 112212 KB Output is correct
12 Correct 347 ms 112296 KB Output is correct
13 Correct 338 ms 112460 KB Output is correct
14 Correct 346 ms 112576 KB Output is correct
15 Correct 307 ms 112508 KB Output is correct
16 Correct 315 ms 112212 KB Output is correct
17 Correct 308 ms 112208 KB Output is correct
18 Correct 352 ms 112184 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 66356 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 309 ms 118864 KB Output is correct
2 Correct 109 ms 68728 KB Output is correct
3 Correct 97 ms 68688 KB Output is correct
4 Correct 92 ms 68692 KB Output is correct
5 Correct 103 ms 68944 KB Output is correct
6 Correct 99 ms 69016 KB Output is correct
7 Correct 96 ms 68948 KB Output is correct
8 Correct 21 ms 66140 KB Output is correct
9 Correct 21 ms 66140 KB Output is correct
10 Correct 21 ms 66132 KB Output is correct
11 Correct 331 ms 117584 KB Output is correct
12 Correct 357 ms 119172 KB Output is correct
13 Correct 419 ms 117664 KB Output is correct
14 Correct 361 ms 117428 KB Output is correct
15 Correct 353 ms 118800 KB Output is correct
16 Correct 364 ms 119380 KB Output is correct
17 Correct 404 ms 119364 KB Output is correct
18 Correct 333 ms 119636 KB Output is correct
19 Correct 296 ms 118724 KB Output is correct
20 Correct 295 ms 118848 KB Output is correct
21 Correct 295 ms 118792 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 695 ms 121580 KB Output is correct
2 Correct 166 ms 69356 KB Output is correct
3 Correct 155 ms 69456 KB Output is correct
4 Correct 158 ms 69456 KB Output is correct
5 Correct 181 ms 69452 KB Output is correct
6 Correct 166 ms 69456 KB Output is correct
7 Correct 168 ms 69588 KB Output is correct
8 Correct 25 ms 66228 KB Output is correct
9 Correct 24 ms 66092 KB Output is correct
10 Correct 24 ms 66192 KB Output is correct
11 Correct 770 ms 118360 KB Output is correct
12 Correct 792 ms 121728 KB Output is correct
13 Correct 795 ms 118532 KB Output is correct
14 Correct 706 ms 118488 KB Output is correct
15 Correct 696 ms 121684 KB Output is correct
16 Correct 817 ms 121804 KB Output is correct
17 Correct 809 ms 121788 KB Output is correct
18 Correct 813 ms 121940 KB Output is correct
19 Correct 715 ms 121824 KB Output is correct
20 Correct 738 ms 121584 KB Output is correct
21 Correct 691 ms 121656 KB Output is correct

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 309 ms 118864 KB Output is correct
2 Correct 109 ms 68728 KB Output is correct
3 Correct 97 ms 68688 KB Output is correct
4 Correct 92 ms 68692 KB Output is correct
5 Correct 103 ms 68944 KB Output is correct
6 Correct 99 ms 69016 KB Output is correct
7 Correct 96 ms 68948 KB Output is correct
8 Correct 21 ms 66140 KB Output is correct
9 Correct 21 ms 66140 KB Output is correct
10 Correct 21 ms 66132 KB Output is correct
11 Correct 331 ms 117584 KB Output is correct
12 Correct 357 ms 119172 KB Output is correct
13 Correct 419 ms 117664 KB Output is correct
14 Correct 361 ms 117428 KB Output is correct
15 Correct 353 ms 118800 KB Output is correct
16 Correct 364 ms 119380 KB Output is correct
17 Correct 404 ms 119364 KB Output is correct
18 Correct 333 ms 119636 KB Output is correct
19 Correct 296 ms 118724 KB Output is correct
20 Correct 295 ms 118848 KB Output is correct
21 Correct 295 ms 118792 KB Output is correct
22 Incorrect 775 ms 121140 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 316 ms 112380 KB Output is correct
2 Correct 146 ms 69460 KB Output is correct
3 Correct 133 ms 69260 KB Output is correct
4 Correct 127 ms 69460 KB Output is correct
5 Correct 120 ms 69456 KB Output is correct
6 Correct 119 ms 69316 KB Output is correct
7 Correct 124 ms 69460 KB Output is correct
8 Correct 30 ms 66140 KB Output is correct
9 Correct 21 ms 66140 KB Output is correct
10 Correct 22 ms 66168 KB Output is correct
11 Correct 316 ms 112212 KB Output is correct
12 Correct 347 ms 112296 KB Output is correct
13 Correct 338 ms 112460 KB Output is correct
14 Correct 346 ms 112576 KB Output is correct
15 Correct 307 ms 112508 KB Output is correct
16 Correct 315 ms 112212 KB Output is correct
17 Correct 308 ms 112208 KB Output is correct
18 Correct 352 ms 112184 KB Output is correct
19 Incorrect 23 ms 66356 KB Output isn't correct
20 Halted 0 ms 0 KB -