oj.uz

Submission #707000

# Submission time Handle Problem Language Result Execution time Memory
707000 2023-03-08T08:47:18 Z lam Progression (NOI20_progression) C++14
44 / 100
 982 ms 117948 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 3e5 + 10;
typedef pair<int,int> ii;
#define ff first
#define ss second

int n,m;
int D[maxn];

struct node
{
    int pre,suf,val_l,val_r,ans,sz;
};
inline node hop(node x, node y)
{
    if (x.val_l==-1e18) return y;
    if (y.val_l==-1e18) return x;
    node z;
    z.pre = x.pre;
    if (x.pre==x.sz&&x.val_r==y.val_l) z.pre = max(z.pre,x.sz+y.pre);
    z.suf = y.suf;
    if (y.suf==y.sz&&y.val_l==x.val_r) z.suf = max(z.suf,y.sz+x.suf);
    z.val_l = x.val_l; z.val_r = y.val_r;
    z.ans = max(x.ans, y.ans);
    if (x.val_r==y.val_l) z.ans = max(z.ans,x.suf+y.pre);
    z.sz = x.sz + y.sz;
    return z;
}

node f[4*maxn]; int lazy_sum[4*maxn], lazy_eq[4*maxn];

void pusheq(int x, int lx, int rx, int val)
{
    f[x].val_l = f[x].val_r = lazy_eq[x] = val; lazy_sum[x]=0;
    f[x].ans = f[x].pre = f[x].suf = f[x].sz = (rx-lx+1);
}

void pushsum(int x, int lx, int rx, int val)
{
    f[x].val_l += val; f[x].val_r += val; lazy_sum[x] += val;
}

void down(int x, int lx, int rx)
{
    if (lx==rx) return;
    int mid=(lx+rx)/2;
    if (lazy_eq[x]!=-1e18)
    {
        pusheq(2*x,lx,mid,lazy_eq[x]);
        pusheq(2*x+1,mid+1,rx,lazy_eq[x]);
        lazy_eq[x]=-1e18;
    }
    if (lazy_sum[x]!=0)
    {
        pushsum(2*x,lx,mid,lazy_sum[x]);
        pushsum(2*x+1,mid+1,rx,lazy_sum[x]);
        lazy_sum[x]=0;
    }
}

void add(int x, int lx, int rx, int l, int r, int val)
{
    if (lx>r||rx<l) return ;
    if (lx>=l&&rx<=r)
    {
        pushsum(x,lx,rx,val);
        return;
    }
    int mid=(lx+rx)/2;
    down(x,lx,rx);
    add(2*x,lx,mid,l,r,val);
    add(2*x+1,mid+1,rx,l,r,val);
    f[x]=hop(f[2*x],f[2*x+1]);
}

void update_eq(int x, int lx, int rx, int l, int r, int val)
{
    if (lx>r||rx<l) return ;
    if (lx>=l&&rx<=r)
    {
        pusheq(x,lx,rx,val);
        return;
    }
    int mid=(lx+rx)/2; down(x,lx,rx);
    update_eq(2*x,lx,mid,l,r,val);
    update_eq(2*x+1,mid+1,rx,l,r,val);
    f[x]=hop(f[2*x],f[2*x+1]);
}

void update(int x, int lx, int rx, int idx, int val)
{
    if (lx==rx)
    {
        pusheq(x,lx,rx,val);
        return;
    }
    int mid=(lx+rx)/2;
    down(x,lx,rx);
    if (idx<=mid) update(2*x,lx,mid,idx,val);
        else update(2*x+1,mid+1,rx,idx,val);
    f[x]=hop(f[2*x],f[2*x+1]);
}

node get(int x, int lx, int rx, int l, int r)
{
    if (lx>r||rx<l) return {0,0,(int)-1e18,(int)-1e18,0,0};
    if (lx>=l&&rx<=r) return f[x];
    int mid=(lx+rx)/2;
    down(x,lx,rx);
    return hop(get(2*x,lx,mid,l,r),get(2*x+1,mid+1,rx,l,r));
}

struct line
{
    int a,b;
};
inline int calc(line x, int idx)
{
    return x.a*idx + x.b;
}
line seg[4*maxn],lazyeq[4*maxn],lazysum[4*maxn];

void pusheq_lichao(int x, int lx, int rx, line val)
{
    seg[x]=lazyeq[x]=val; lazysum[x]={0,0};
}
void pushsum_lichao(int x, int lx, int rx, line val)
{
    seg[x].a+=val.a; seg[x].b+=val.b;
    lazysum[x].a+=val.a; lazysum[x].b+=val.b;
}

void down_lichao(int x, int lx, int rx)
{
    if (lx==rx) return;
    int mid=(lx+rx)/2;
    if (lazyeq[x].a!=-1e18)
    {
        pusheq_lichao(2*x,lx,mid,lazyeq[x]);
        pusheq_lichao(2*x+1,mid+1,rx,lazyeq[x]);
        lazyeq[x]={(int)-1e18,(int)-1e18};
    }
    if (lazysum[x].a!=0||lazysum[x].b!=0)
    {
        pushsum_lichao(2*x,lx,mid,lazysum[x]);
        pushsum_lichao(2*x+1,mid+1,rx,lazysum[x]);
        lazysum[x]={0,0};
    }
}

void add_lichao(int x, int lx, int rx, int l, int r, line val)
{
    if (lx>r||rx<l) return ;
    if (lx>=l&&rx<=r)
    {
        pushsum_lichao(x,lx,rx,val);
        return;
    }
    int mid=(lx+rx)/2;
    down_lichao(x,lx,rx);
    add_lichao(2*x,lx,mid,l,r,val);
    add_lichao(2*x+1,mid+1,rx,l,r,val);
}

void update_lichao(int x, int lx, int rx, int l, int r, line val)
{
    if (lx>r||rx<l) return;
    if (lx>=l&&rx<=r)
    {
        pusheq_lichao(x,lx,rx,val);
        return;
    }
    int mid=(lx+rx)/2;
    down_lichao(x,lx,rx);
    update_lichao(2*x,lx,mid,l,r,val);
    update_lichao(2*x+1,mid+1,rx,l,r,val);
}

line qry(int x, int lx, int rx, int idx)
{
    if (lx==rx) return seg[x];
    int mid=(lx+rx)/2;
    down_lichao(x,lx,rx);
    if (idx<=mid) return qry(2*x,lx,mid,idx);
    else return qry(2*x+1,mid+1,rx,idx);
}

void build(int x, int lx, int rx)
{
    lazy_eq[x]=-1e18;
    lazy_sum[x]=0;
    if (lx==rx)
    {
        pusheq(x,lx,rx,D[lx]-D[lx-1]);
        return;
    }
    int mid=(lx+rx)/2;
    build(2*x,lx,mid); build(2*x+1,mid+1,rx);
    f[x]=hop(f[2*x],f[2*x+1]);
}

void build_lichao(int x, int lx, int rx)
{
    lazyeq[x]={(int)-1e18,(int)-1e18};
    lazysum[x]={0,0};
    if (lx==rx)
    {
        pusheq_lichao(x,lx,rx,{0,D[lx]});
        return;
    }
    int mid=(lx+rx)/2;
    build_lichao(2*x,lx,mid); build_lichao(2*x+1,mid+1,rx);
}

//void dbg(int x, int lx, int rx)
//{
//    cout<<x<<' '<<lx<<' '<<rx<<" = "<<f[x].val_l<<' '<<f[x].val_r<<" , "<<f[x].pre<<' '<<f[x].suf<<" , "<<f[x].sz<<' '<<f[x].ans<<" :: "<<lazy_eq[x]<<' '<<lazy_sum[x]<<'\n';
//    if (lx==rx) return;
//    int mid=(lx+rx)/2;
//    dbg(2*x,lx,mid);
//    dbg(2*x+1,mid+1,rx);
//}
//void dbg_lichao(int x, int lx, int rx)
//{
//    cout<<x<<' '<<lx<<' '<<rx<<" = "<<seg[x].a<<' '<<seg[x].b<<" , "<<lazysum[x].a<<' '<<lazysum[x].b<<" , "<<lazyeq[x].a<<' '<<lazyeq[x].b<<'\n';
//    if (lx==rx) return;
//    int mid=(lx+rx)/2;
//    dbg_lichao(2*x,lx,mid);
//    dbg_lichao(2*x+1,mid+1,rx);
//}

void sub1()
{
    for (int i=1; i<=m; i++)
    {
        int t,l,r; cin>>t;
        if (t==1||t==2)
        {
            int x,y; cin>>l>>r>>x>>y;
        }
        else
        {
            cin>>l>>r;
            cout<<"1\n";
        }
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cin>>n>>m;
    for (int i=1; i<=n; i++) cin>>D[i];
    if (n==1)
    {
        sub1();
        return 0;
    }
    build(1,2,n);
//    build_lichao(1,1,n);
    bool has=0;
    for (int i=1; i<=m; i++)
    {
        int t; cin>>t;
        if (t==1)
        {
            int l,r,S,C; cin>>l>>r>>S>>C;
            line temp = {C, S-l*C};
            add(1,2,n,l+1,r,C);
            add_lichao(1,1,n,l,r,temp);
            if (l>1) update(1,2,n,l,calc(qry(1,1,n,l),l) - calc(qry(1,1,n,l-1),l-1));
            if (r<n) update(1,2,n,r+1,calc(qry(1,1,n,r+1),r+1) - calc(qry(1,1,n,r),r));
//            cout<<l<<" :: "<<calc(qry(1,1,n,l),l)<<'\n';
//            cout<<r<<" :: "<<calc(qry(1,1,n,r),r)<<'\n';
        }
        else if (t==2)
        {
            int l,r,S,C; cin>>l>>r>>S>>C;
            has=1;
            line temp = {C, S-l*C};
            update_eq(1,2,n,l+1,r,C);
            update_lichao(1,1,n,l,r,temp);
            if (l>1) update(1,2,n,l,calc(qry(1,1,n,l),l) - calc(qry(1,1,n,l-1),l-1));
            if (r<n) update(1,2,n,r+1,calc(qry(1,1,n,r+1),r+1) - calc(qry(1,1,n,r),r));
        }
        else
        {
            int l,r; cin>>l>>r;
            node temp = get(1,2,n,l+1,r);
            int ans = temp.ans + 1;
            cout<<ans<<'\n';
        }
//        dbg(1,2,n);
//        cout<<" ========= \n";
//        dbg_lichao(1,1,n);
//        cout<<"---------------------------\n";
//        cout<<"---------------------------\n";
//        cout<<"---------------------------\n";
    }
}
/**
10 3
1 2 3 4 1 2 3 4 5 5
3 1 10
1 2 8 1 2
3 2 9
2 1 10 3 4
3 1 10
**/

Compilation message

Progression.cpp: In function 'int main()':
Progression.cpp:264:10: warning: variable 'has' set but not used [-Wunused-but-set-variable]
  264 |     bool has=0;
      |          ^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 74104 KB Output is correct
2 Correct 71 ms 3548 KB Output is correct
3 Correct 81 ms 3476 KB Output is correct
4 Correct 79 ms 3584 KB Output is correct
5 Correct 75 ms 3620 KB Output is correct
6 Correct 81 ms 3616 KB Output is correct
7 Correct 83 ms 3548 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 171 ms 73756 KB Output is correct
12 Correct 155 ms 73620 KB Output is correct
13 Correct 152 ms 73920 KB Output is correct
14 Correct 169 ms 73932 KB Output is correct
15 Correct 143 ms 73912 KB Output is correct
16 Correct 156 ms 73672 KB Output is correct
17 Correct 154 ms 73544 KB Output is correct
18 Correct 148 ms 73648 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 596 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 2 ms 592 KB Output is correct
11 Incorrect 2 ms 596 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 281 ms 74264 KB Output is correct
2 Correct 84 ms 3064 KB Output is correct
3 Correct 85 ms 2984 KB Output is correct
4 Correct 76 ms 3040 KB Output is correct
5 Correct 79 ms 3148 KB Output is correct
6 Correct 84 ms 3212 KB Output is correct
7 Correct 87 ms 3276 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 287 ms 71400 KB Output is correct
12 Correct 307 ms 71732 KB Output is correct
13 Correct 282 ms 71244 KB Output is correct
14 Correct 288 ms 71392 KB Output is correct
15 Correct 288 ms 71500 KB Output is correct
16 Correct 293 ms 69760 KB Output is correct
17 Correct 347 ms 69652 KB Output is correct
18 Correct 293 ms 69864 KB Output is correct
19 Correct 255 ms 69032 KB Output is correct
20 Correct 268 ms 69040 KB Output is correct
21 Correct 257 ms 68940 KB Output is correct

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 801 ms 117896 KB Output is correct
2 Incorrect 153 ms 3660 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 281 ms 74264 KB Output is correct
2 Correct 84 ms 3064 KB Output is correct
3 Correct 85 ms 2984 KB Output is correct
4 Correct 76 ms 3040 KB Output is correct
5 Correct 79 ms 3148 KB Output is correct
6 Correct 84 ms 3212 KB Output is correct
7 Correct 87 ms 3276 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 287 ms 71400 KB Output is correct
12 Correct 307 ms 71732 KB Output is correct
13 Correct 282 ms 71244 KB Output is correct
14 Correct 288 ms 71392 KB Output is correct
15 Correct 288 ms 71500 KB Output is correct
16 Correct 293 ms 69760 KB Output is correct
17 Correct 347 ms 69652 KB Output is correct
18 Correct 293 ms 69864 KB Output is correct
19 Correct 255 ms 69032 KB Output is correct
20 Correct 268 ms 69040 KB Output is correct
21 Correct 257 ms 68940 KB Output is correct
22 Correct 982 ms 117948 KB Output is correct
23 Incorrect 161 ms 3688 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 74104 KB Output is correct
2 Correct 71 ms 3548 KB Output is correct
3 Correct 81 ms 3476 KB Output is correct
4 Correct 79 ms 3584 KB Output is correct
5 Correct 75 ms 3620 KB Output is correct
6 Correct 81 ms 3616 KB Output is correct
7 Correct 83 ms 3548 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 171 ms 73756 KB Output is correct
12 Correct 155 ms 73620 KB Output is correct
13 Correct 152 ms 73920 KB Output is correct
14 Correct 169 ms 73932 KB Output is correct
15 Correct 143 ms 73912 KB Output is correct
16 Correct 156 ms 73672 KB Output is correct
17 Correct 154 ms 73544 KB Output is correct
18 Correct 148 ms 73648 KB Output is correct
19 Correct 3 ms 596 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 2 ms 596 KB Output is correct
27 Correct 2 ms 596 KB Output is correct
28 Correct 2 ms 592 KB Output is correct
29 Incorrect 2 ms 596 KB Output isn't correct
30 Halted 0 ms 0 KB -