oj.uz

Submission #1088526

# Submission time Handle Problem Language Result Execution time Memory
1088526 2024-09-14T14:53:18 Z vjudge1 Progression (NOI20_progression) C++17
68 / 100
 901 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;
        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);
        }
        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 379 ms 112208 KB Output is correct
2 Correct 142 ms 69460 KB Output is correct
3 Correct 142 ms 69456 KB Output is correct
4 Correct 159 ms 69320 KB Output is correct
5 Correct 146 ms 69352 KB Output is correct
6 Correct 146 ms 69460 KB Output is correct
7 Correct 146 ms 69456 KB Output is correct
8 Correct 23 ms 66136 KB Output is correct
9 Correct 26 ms 66140 KB Output is correct
10 Correct 25 ms 66248 KB Output is correct
11 Correct 389 ms 112244 KB Output is correct
12 Correct 346 ms 112212 KB Output is correct
13 Correct 368 ms 112520 KB Output is correct
14 Correct 350 ms 112724 KB Output is correct
15 Correct 363 ms 112464 KB Output is correct
16 Correct 341 ms 112212 KB Output is correct
17 Correct 351 ms 112208 KB Output is correct
18 Correct 330 ms 112168 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 331 ms 118704 KB Output is correct
2 Correct 101 ms 68792 KB Output is correct
3 Correct 152 ms 68732 KB Output is correct
4 Correct 91 ms 68748 KB Output is correct
5 Correct 103 ms 68948 KB Output is correct
6 Correct 138 ms 69040 KB Output is correct
7 Correct 108 ms 68948 KB Output is correct
8 Correct 29 ms 66132 KB Output is correct
9 Correct 26 ms 66032 KB Output is correct
10 Correct 25 ms 66128 KB Output is correct
11 Correct 375 ms 117588 KB Output is correct
12 Correct 352 ms 119148 KB Output is correct
13 Correct 385 ms 117428 KB Output is correct
14 Correct 370 ms 117616 KB Output is correct
15 Correct 335 ms 118868 KB Output is correct
16 Correct 376 ms 119380 KB Output is correct
17 Correct 369 ms 119460 KB Output is correct
18 Correct 368 ms 119632 KB Output is correct
19 Correct 353 ms 118808 KB Output is correct
20 Correct 316 ms 118868 KB Output is correct
21 Correct 330 ms 119116 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 747 ms 121652 KB Output is correct
2 Correct 170 ms 69460 KB Output is correct
3 Correct 174 ms 69456 KB Output is correct
4 Correct 168 ms 69356 KB Output is correct
5 Correct 174 ms 69460 KB Output is correct
6 Correct 172 ms 69456 KB Output is correct
7 Correct 171 ms 69464 KB Output is correct
8 Correct 25 ms 66140 KB Output is correct
9 Correct 25 ms 66140 KB Output is correct
10 Correct 26 ms 66140 KB Output is correct
11 Correct 754 ms 118432 KB Output is correct
12 Correct 765 ms 121788 KB Output is correct
13 Correct 785 ms 118356 KB Output is correct
14 Correct 784 ms 118360 KB Output is correct
15 Correct 721 ms 121680 KB Output is correct
16 Correct 787 ms 121624 KB Output is correct
17 Correct 760 ms 121772 KB Output is correct
18 Correct 772 ms 121940 KB Output is correct
19 Correct 732 ms 121624 KB Output is correct
20 Correct 752 ms 121684 KB Output is correct
21 Correct 752 ms 121748 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 331 ms 118704 KB Output is correct
2 Correct 101 ms 68792 KB Output is correct
3 Correct 152 ms 68732 KB Output is correct
4 Correct 91 ms 68748 KB Output is correct
5 Correct 103 ms 68948 KB Output is correct
6 Correct 138 ms 69040 KB Output is correct
7 Correct 108 ms 68948 KB Output is correct
8 Correct 29 ms 66132 KB Output is correct
9 Correct 26 ms 66032 KB Output is correct
10 Correct 25 ms 66128 KB Output is correct
11 Correct 375 ms 117588 KB Output is correct
12 Correct 352 ms 119148 KB Output is correct
13 Correct 385 ms 117428 KB Output is correct
14 Correct 370 ms 117616 KB Output is correct
15 Correct 335 ms 118868 KB Output is correct
16 Correct 376 ms 119380 KB Output is correct
17 Correct 369 ms 119460 KB Output is correct
18 Correct 368 ms 119632 KB Output is correct
19 Correct 353 ms 118808 KB Output is correct
20 Correct 316 ms 118868 KB Output is correct
21 Correct 330 ms 119116 KB Output is correct
22 Correct 810 ms 121172 KB Output is correct
23 Correct 172 ms 69496 KB Output is correct
24 Correct 162 ms 69460 KB Output is correct
25 Correct 171 ms 69460 KB Output is correct
26 Correct 164 ms 69456 KB Output is correct
27 Correct 171 ms 69456 KB Output is correct
28 Correct 177 ms 69460 KB Output is correct
29 Correct 23 ms 66136 KB Output is correct
30 Correct 21 ms 66140 KB Output is correct
31 Correct 23 ms 66140 KB Output is correct
32 Correct 845 ms 118356 KB Output is correct
33 Correct 813 ms 121128 KB Output is correct
34 Correct 885 ms 118276 KB Output is correct
35 Correct 831 ms 118452 KB Output is correct
36 Correct 605 ms 118096 KB Output is correct
37 Correct 614 ms 118356 KB Output is correct
38 Correct 665 ms 118244 KB Output is correct
39 Correct 850 ms 121096 KB Output is correct
40 Correct 855 ms 121424 KB Output is correct
41 Correct 901 ms 121304 KB Output is correct
42 Correct 865 ms 121168 KB Output is correct
43 Correct 819 ms 121236 KB Output is correct
44 Correct 799 ms 121028 KB Output is correct
45 Correct 809 ms 121168 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 379 ms 112208 KB Output is correct
2 Correct 142 ms 69460 KB Output is correct
3 Correct 142 ms 69456 KB Output is correct
4 Correct 159 ms 69320 KB Output is correct
5 Correct 146 ms 69352 KB Output is correct
6 Correct 146 ms 69460 KB Output is correct
7 Correct 146 ms 69456 KB Output is correct
8 Correct 23 ms 66136 KB Output is correct
9 Correct 26 ms 66140 KB Output is correct
10 Correct 25 ms 66248 KB Output is correct
11 Correct 389 ms 112244 KB Output is correct
12 Correct 346 ms 112212 KB Output is correct
13 Correct 368 ms 112520 KB Output is correct
14 Correct 350 ms 112724 KB Output is correct
15 Correct 363 ms 112464 KB Output is correct
16 Correct 341 ms 112212 KB Output is correct
17 Correct 351 ms 112208 KB Output is correct
18 Correct 330 ms 112168 KB Output is correct
19 Incorrect 25 ms 66140 KB Output isn't correct
20 Halted 0 ms 0 KB -