oj.uz

Submission #707012

# Submission time Handle Problem Language Result Execution time Memory
707012 2023-03-08T09:27:04 Z lam Progression (NOI20_progression) C++14
44 / 100
 1036 ms 118056 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||lazyeq[x].b!=-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 138 ms 68932 KB Output is correct
2 Correct 93 ms 576 KB Output is correct
3 Correct 76 ms 620 KB Output is correct
4 Correct 69 ms 624 KB Output is correct
5 Correct 73 ms 640 KB Output is correct
6 Correct 68 ms 664 KB Output is correct
7 Correct 72 ms 588 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 132 ms 69004 KB Output is correct
12 Correct 143 ms 68904 KB Output is correct
13 Correct 156 ms 69128 KB Output is correct
14 Correct 136 ms 69144 KB Output is correct
15 Correct 133 ms 69184 KB Output is correct
16 Correct 145 ms 69004 KB Output is correct
17 Correct 142 ms 68904 KB Output is correct
18 Correct 136 ms 68812 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 3 ms 536 KB Output is correct
11 Incorrect 2 ms 540 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 273 ms 69268 KB Output is correct
2 Correct 81 ms 844 KB Output is correct
3 Correct 86 ms 928 KB Output is correct
4 Correct 72 ms 856 KB Output is correct
5 Correct 77 ms 924 KB Output is correct
6 Correct 78 ms 984 KB Output is correct
7 Correct 96 ms 960 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 212 KB Output is correct
11 Correct 275 ms 69052 KB Output is correct
12 Correct 296 ms 69384 KB Output is correct
13 Correct 270 ms 69068 KB Output is correct
14 Correct 271 ms 69096 KB Output is correct
15 Correct 268 ms 69560 KB Output is correct
16 Correct 288 ms 69700 KB Output is correct
17 Correct 303 ms 69612 KB Output is correct
18 Correct 275 ms 69772 KB Output is correct
19 Correct 254 ms 68964 KB Output is correct
20 Correct 247 ms 68936 KB Output is correct
21 Correct 240 ms 69056 KB Output is correct

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 857 ms 118000 KB Output is correct
2 Incorrect 163 ms 560 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 69268 KB Output is correct
2 Correct 81 ms 844 KB Output is correct
3 Correct 86 ms 928 KB Output is correct
4 Correct 72 ms 856 KB Output is correct
5 Correct 77 ms 924 KB Output is correct
6 Correct 78 ms 984 KB Output is correct
7 Correct 96 ms 960 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 212 KB Output is correct
11 Correct 275 ms 69052 KB Output is correct
12 Correct 296 ms 69384 KB Output is correct
13 Correct 270 ms 69068 KB Output is correct
14 Correct 271 ms 69096 KB Output is correct
15 Correct 268 ms 69560 KB Output is correct
16 Correct 288 ms 69700 KB Output is correct
17 Correct 303 ms 69612 KB Output is correct
18 Correct 275 ms 69772 KB Output is correct
19 Correct 254 ms 68964 KB Output is correct
20 Correct 247 ms 68936 KB Output is correct
21 Correct 240 ms 69056 KB Output is correct
22 Correct 1036 ms 118056 KB Output is correct
23 Incorrect 160 ms 768 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 68932 KB Output is correct
2 Correct 93 ms 576 KB Output is correct
3 Correct 76 ms 620 KB Output is correct
4 Correct 69 ms 624 KB Output is correct
5 Correct 73 ms 640 KB Output is correct
6 Correct 68 ms 664 KB Output is correct
7 Correct 72 ms 588 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 132 ms 69004 KB Output is correct
12 Correct 143 ms 68904 KB Output is correct
13 Correct 156 ms 69128 KB Output is correct
14 Correct 136 ms 69144 KB Output is correct
15 Correct 133 ms 69184 KB Output is correct
16 Correct 145 ms 69004 KB Output is correct
17 Correct 142 ms 68904 KB Output is correct
18 Correct 136 ms 68812 KB Output is correct
19 Correct 2 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 3 ms 536 KB Output is correct
29 Incorrect 2 ms 540 KB Output isn't correct
30 Halted 0 ms 0 KB -