oj.uz

Submission #1088501

# Submission time Handle Problem Language Result Execution time Memory
1088501 2024-09-14T14:15:01 Z vjudge1 Progression (NOI20_progression) C++17
55 / 100
 857 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=1e18;
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];
//        cout<<b[i]<<" ";
    }
//    cout<<"\n";
    f.cons(1,1,n);
    g.cons(1,1,n);
    node kk=g.get(1,1,n,2,2);
//    cout<<"!"<<kk.opt.fi<<" "<<kk.opt.sc<<"\n";
//    cout<<"!"<<g.ST[17].opt.fi<<" "<<g.ST[17].opt.sc<<"\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:238:10: warning: variable 'kk' set but not used [-Wunused-but-set-variable]
  238 |     node kk=g.get(1,1,n,2,2);
      |          ^~
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 304 ms 112208 KB Output is correct
2 Correct 118 ms 69280 KB Output is correct
3 Correct 123 ms 69456 KB Output is correct
4 Correct 125 ms 69460 KB Output is correct
5 Correct 123 ms 69380 KB Output is correct
6 Correct 129 ms 69460 KB Output is correct
7 Correct 141 ms 69244 KB Output is correct
8 Correct 23 ms 66096 KB Output is correct
9 Correct 29 ms 66132 KB Output is correct
10 Correct 25 ms 66140 KB Output is correct
11 Correct 313 ms 112196 KB Output is correct
12 Correct 316 ms 112388 KB Output is correct
13 Correct 321 ms 112468 KB Output is correct
14 Correct 318 ms 112756 KB Output is correct
15 Correct 308 ms 112368 KB Output is correct
16 Correct 323 ms 112196 KB Output is correct
17 Correct 305 ms 112212 KB Output is correct
18 Correct 310 ms 112212 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 66136 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 118868 KB Output is correct
2 Correct 95 ms 68944 KB Output is correct
3 Correct 93 ms 68692 KB Output is correct
4 Correct 86 ms 68688 KB Output is correct
5 Correct 95 ms 68944 KB Output is correct
6 Correct 102 ms 68956 KB Output is correct
7 Correct 96 ms 69012 KB Output is correct
8 Correct 25 ms 66040 KB Output is correct
9 Correct 25 ms 66228 KB Output is correct
10 Correct 26 ms 66136 KB Output is correct
11 Correct 340 ms 117584 KB Output is correct
12 Correct 303 ms 118868 KB Output is correct
13 Correct 343 ms 117464 KB Output is correct
14 Correct 361 ms 117584 KB Output is correct
15 Correct 294 ms 118868 KB Output is correct
16 Correct 345 ms 119576 KB Output is correct
17 Correct 343 ms 119444 KB Output is correct
18 Correct 368 ms 119636 KB Output is correct
19 Correct 333 ms 118868 KB Output is correct
20 Correct 319 ms 118868 KB Output is correct
21 Correct 336 ms 118864 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 790 ms 121640 KB Output is correct
2 Correct 159 ms 69456 KB Output is correct
3 Correct 167 ms 69460 KB Output is correct
4 Correct 167 ms 69456 KB Output is correct
5 Correct 158 ms 69492 KB Output is correct
6 Correct 168 ms 69784 KB Output is correct
7 Correct 160 ms 69572 KB Output is correct
8 Correct 27 ms 66136 KB Output is correct
9 Correct 24 ms 66140 KB Output is correct
10 Correct 23 ms 66140 KB Output is correct
11 Correct 782 ms 118420 KB Output is correct
12 Correct 787 ms 121836 KB Output is correct
13 Correct 729 ms 118356 KB Output is correct
14 Correct 750 ms 118356 KB Output is correct
15 Correct 715 ms 121680 KB Output is correct
16 Correct 783 ms 121684 KB Output is correct
17 Correct 816 ms 121684 KB Output is correct
18 Correct 809 ms 121940 KB Output is correct
19 Correct 828 ms 121640 KB Output is correct
20 Correct 809 ms 121588 KB Output is correct
21 Correct 809 ms 121680 KB Output is correct

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 309 ms 118868 KB Output is correct
2 Correct 95 ms 68944 KB Output is correct
3 Correct 93 ms 68692 KB Output is correct
4 Correct 86 ms 68688 KB Output is correct
5 Correct 95 ms 68944 KB Output is correct
6 Correct 102 ms 68956 KB Output is correct
7 Correct 96 ms 69012 KB Output is correct
8 Correct 25 ms 66040 KB Output is correct
9 Correct 25 ms 66228 KB Output is correct
10 Correct 26 ms 66136 KB Output is correct
11 Correct 340 ms 117584 KB Output is correct
12 Correct 303 ms 118868 KB Output is correct
13 Correct 343 ms 117464 KB Output is correct
14 Correct 361 ms 117584 KB Output is correct
15 Correct 294 ms 118868 KB Output is correct
16 Correct 345 ms 119576 KB Output is correct
17 Correct 343 ms 119444 KB Output is correct
18 Correct 368 ms 119636 KB Output is correct
19 Correct 333 ms 118868 KB Output is correct
20 Correct 319 ms 118868 KB Output is correct
21 Correct 336 ms 118864 KB Output is correct
22 Incorrect 857 ms 121104 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 304 ms 112208 KB Output is correct
2 Correct 118 ms 69280 KB Output is correct
3 Correct 123 ms 69456 KB Output is correct
4 Correct 125 ms 69460 KB Output is correct
5 Correct 123 ms 69380 KB Output is correct
6 Correct 129 ms 69460 KB Output is correct
7 Correct 141 ms 69244 KB Output is correct
8 Correct 23 ms 66096 KB Output is correct
9 Correct 29 ms 66132 KB Output is correct
10 Correct 25 ms 66140 KB Output is correct
11 Correct 313 ms 112196 KB Output is correct
12 Correct 316 ms 112388 KB Output is correct
13 Correct 321 ms 112468 KB Output is correct
14 Correct 318 ms 112756 KB Output is correct
15 Correct 308 ms 112368 KB Output is correct
16 Correct 323 ms 112196 KB Output is correct
17 Correct 305 ms 112212 KB Output is correct
18 Correct 310 ms 112212 KB Output is correct
19 Incorrect 25 ms 66136 KB Output isn't correct
20 Halted 0 ms 0 KB -