oj.uz

Submission #426318

# Submission time Handle Problem Language Result Execution time Memory
426318 2021-06-13T17:44:40 Z TLP39 Progression (NOI20_progression) C++14
55 / 100
 1657 ms 100228 KB 
#include <stdio.h>
#include <math.h>
#include <utility>
#include <string.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
using namespace std;
typedef long long int ll;
struct dev{
    bool typ;
    ll s,c;
};

struct play{
    ll l,r,len,cl,dl,cr,dr,c;
};

dev rep(dev x,dev y)
{
    if(y.typ) return y;
    return {x.typ,x.s+y.s,x.c+y.c};
}

play mix(play x,play y)
{
    play ans={x.l,y.r,x.len+y.len,x.cl,x.dl,y.cr,y.dr,max(x.c,y.c)};
    if(x.cl==x.len)
    {
        if(x.len==1)
        {
            ans.dl=y.l-x.r;
            if(y.cl==1) ans.cl=2;
            else
            {
                if(y.dl==y.l-x.r) ans.cl=y.cl+1;
                else ans.cl=2;
            }
        }
        else
        {
            if(y.l-x.r!=x.dl) ans.cl=x.cl;
            else
            {
                if(y.dl==x.dl) ans.cl=x.cl+y.cl;
                else ans.cl=x.cl+1;
            }
        }
    }

    if(y.cr==y.len)
    {
        if(y.len==1)
        {
            ans.dr=y.l-x.r;
            if(x.cr==1) ans.cr=2;
            else
            {
                if(x.dr==y.l-x.r) ans.cr=x.cr+1;
                else ans.cr=2;
            }
        }
        else
        {
            if(y.l-x.r!=y.dr) ans.cr=y.cr;
            else
            {
                if(x.dr==y.dr) ans.cr=x.cr+y.cr;
                else ans.cr=y.cr+1;
            }
        }
    }

    if(y.l-x.r==x.dr)
    {
        if(y.l-x.r==y.dl)
        {
            ans.c=max(ans.c,x.cr+y.cl);
        }
        else
        {
            ans.c=max(ans.c,x.cr+1);
        }
    }
    else
    {
        if(y.l-x.r==y.dl)
        {
            ans.c=max(ans.c,1+y.cl);
        }
        else
        {
            ans.c=max(ans.c,2ll);
        }
    }

    return ans;
}

play mod(play x,dev y,ll l,ll r)
{
    play ans=x;
    if(y.typ)
    {
        ans.l=y.s+(l-1)*y.c;
        ans.r=y.s+(r-1)*y.c;
        ans.cl=ans.len;
        ans.cr=ans.len;
        ans.c=ans.len;
        ans.dl=ans.dr=y.c;
        return ans;
    }
    ans.l+=(y.s+(l-1)*y.c);
    ans.r+=(y.s+(r-1)*y.c);
    ans.dl+=y.c;
    ans.dr+=y.c;
    return ans;
}

ll n,q;
ll a[300010];
play seg[1200040];
dev lz[1200040];
bool marked[1200040],bottom[1200040];

void build(ll v,ll st,ll ed)
{
    if(st==ed)
    {
        seg[v]={a[st],a[st],1,1,0,1,0,1};
        bottom[v]=true;
        return;
    }
    ll mid=(st+ed)>>1;
    build(2*v,st,mid);
    build(2*v+1,mid+1,ed);
    seg[v]=mix(seg[2*v],seg[2*v+1]);
}

void push_down(ll v,ll l,ll r)
{
    if(!marked[v] || bottom[v]) return;
    marked[v]=false;
    marked[2*v]=marked[2*v+1]=true;
    seg[2*v]=mod(seg[2*v],lz[v],l,r);
    lz[2*v]=rep(lz[2*v],lz[v]);
    seg[2*v+1]=mod(seg[2*v+1],lz[v],l,r);
    lz[2*v+1]=rep(lz[2*v+1],lz[v]);
    lz[v]={false,0,0};
}

void upd(ll v,ll st,ll ed,ll l,ll r,dev x)
{
    if(st>ed) return;
    if(st==l && ed==r)
    {
        marked[v]=true;
        seg[v]=mod(seg[v],x,l,r);
        lz[v]=rep(lz[v],x);
        return;
    }
    push_down(v,l,r);
    ll mid=(l+r)>>1;
    upd(2*v,st,min(mid,ed),l,mid,x);
    upd(2*v+1,max(mid+1,st),ed,mid+1,r,x);
    seg[v]=mix(seg[2*v],seg[2*v+1]);
}

play que(ll v,ll st,ll ed,ll l,ll r)
{
    if(l==st && r==ed) return seg[v];
    push_down(v,l,r);
    ll mid=(l+r)>>1;
    if(ed<=mid) return que(2*v,st,ed,l,mid);
    if(st>mid) return que(2*v+1,st,ed,mid+1,r);
    return mix(que(2*v,st,mid,l,mid),que(2*v+1,mid+1,ed,mid+1,r));
}

int main()
{
    scanf("%lld %lld",&n,&q);
    for(ll i=1;i<=n;i++) scanf("%lld",&a[i]);
    for(ll i=0;i<1200040;i++)
    {
        marked[i]=false;
        bottom[i]=false;
        lz[i]={false,0,0};
    }
    build(1,1,n);
    ll ty,l,r;
    ll s,c;
    dev temp;
    while(q--)
    {
        scanf("%lld",&ty);
        if(ty==1)
        {
            scanf("%lld %lld %lld %lld",&l,&r,&s,&c);
            temp={false,s+(1-l)*c,c};
            upd(1,l,r,1,n,temp);
        }
        else if(ty==2)
        {
            scanf("%lld %lld %lld %lld",&l,&r,&s,&c);
            temp={true,s+(1-l)*c,c};
            upd(1,l,r,1,n,temp);
        }
        else
        {
            scanf("%lld %lld",&l,&r);
            printf("%lld\n",(que(1,l,r,1,n)).c);
        }
    }
}

Compilation message

Progression.cpp: In function 'int main()':
Progression.cpp:183:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  183 |     scanf("%lld %lld",&n,&q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
Progression.cpp:184:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  184 |     for(ll i=1;i<=n;i++) scanf("%lld",&a[i]);
      |                          ~~~~~^~~~~~~~~~~~~~
Progression.cpp:197:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  197 |         scanf("%lld",&ty);
      |         ~~~~~^~~~~~~~~~~~
Progression.cpp:200:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  200 |             scanf("%lld %lld %lld %lld",&l,&r,&s,&c);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Progression.cpp:206:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  206 |             scanf("%lld %lld %lld %lld",&l,&r,&s,&c);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Progression.cpp:212:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  212 |             scanf("%lld %lld",&l,&r);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 291 ms 99524 KB Output is correct
2 Correct 167 ms 31120 KB Output is correct
3 Correct 155 ms 31044 KB Output is correct
4 Correct 159 ms 31024 KB Output is correct
5 Correct 153 ms 31128 KB Output is correct
6 Correct 157 ms 31160 KB Output is correct
7 Correct 157 ms 31112 KB Output is correct
8 Correct 21 ms 30796 KB Output is correct
9 Correct 19 ms 30844 KB Output is correct
10 Correct 19 ms 30768 KB Output is correct
11 Correct 255 ms 99436 KB Output is correct
12 Correct 260 ms 99456 KB Output is correct
13 Correct 269 ms 99652 KB Output is correct
14 Correct 250 ms 99608 KB Output is correct
15 Correct 268 ms 99684 KB Output is correct
16 Correct 290 ms 99304 KB Output is correct
17 Correct 256 ms 99352 KB Output is correct
18 Correct 263 ms 99292 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 30976 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 373 ms 99756 KB Output is correct
2 Correct 158 ms 31392 KB Output is correct
3 Correct 199 ms 31360 KB Output is correct
4 Correct 148 ms 31428 KB Output is correct
5 Correct 154 ms 31460 KB Output is correct
6 Correct 147 ms 31396 KB Output is correct
7 Correct 150 ms 31408 KB Output is correct
8 Correct 17 ms 30796 KB Output is correct
9 Correct 20 ms 30796 KB Output is correct
10 Correct 19 ms 30820 KB Output is correct
11 Correct 452 ms 99524 KB Output is correct
12 Correct 361 ms 99856 KB Output is correct
13 Correct 442 ms 99652 KB Output is correct
14 Correct 473 ms 99692 KB Output is correct
15 Correct 368 ms 99912 KB Output is correct
16 Correct 464 ms 100188 KB Output is correct
17 Correct 451 ms 100200 KB Output is correct
18 Correct 466 ms 100228 KB Output is correct
19 Correct 374 ms 99476 KB Output is correct
20 Correct 385 ms 99524 KB Output is correct
21 Correct 450 ms 99524 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 725 ms 99104 KB Output is correct
2 Correct 199 ms 31068 KB Output is correct
3 Correct 203 ms 30964 KB Output is correct
4 Correct 203 ms 31000 KB Output is correct
5 Correct 211 ms 31012 KB Output is correct
6 Correct 212 ms 30964 KB Output is correct
7 Correct 208 ms 31096 KB Output is correct
8 Correct 18 ms 30796 KB Output is correct
9 Correct 18 ms 30788 KB Output is correct
10 Correct 19 ms 30808 KB Output is correct
11 Correct 766 ms 99204 KB Output is correct
12 Correct 798 ms 99204 KB Output is correct
13 Correct 819 ms 99188 KB Output is correct
14 Correct 806 ms 99072 KB Output is correct
15 Correct 706 ms 99012 KB Output is correct
16 Correct 822 ms 99168 KB Output is correct
17 Correct 782 ms 99276 KB Output is correct
18 Correct 772 ms 99104 KB Output is correct
19 Correct 786 ms 99072 KB Output is correct
20 Correct 710 ms 98980 KB Output is correct
21 Correct 831 ms 99096 KB Output is correct

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 373 ms 99756 KB Output is correct
2 Correct 158 ms 31392 KB Output is correct
3 Correct 199 ms 31360 KB Output is correct
4 Correct 148 ms 31428 KB Output is correct
5 Correct 154 ms 31460 KB Output is correct
6 Correct 147 ms 31396 KB Output is correct
7 Correct 150 ms 31408 KB Output is correct
8 Correct 17 ms 30796 KB Output is correct
9 Correct 20 ms 30796 KB Output is correct
10 Correct 19 ms 30820 KB Output is correct
11 Correct 452 ms 99524 KB Output is correct
12 Correct 361 ms 99856 KB Output is correct
13 Correct 442 ms 99652 KB Output is correct
14 Correct 473 ms 99692 KB Output is correct
15 Correct 368 ms 99912 KB Output is correct
16 Correct 464 ms 100188 KB Output is correct
17 Correct 451 ms 100200 KB Output is correct
18 Correct 466 ms 100228 KB Output is correct
19 Correct 374 ms 99476 KB Output is correct
20 Correct 385 ms 99524 KB Output is correct
21 Correct 450 ms 99524 KB Output is correct
22 Incorrect 1657 ms 99152 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 291 ms 99524 KB Output is correct
2 Correct 167 ms 31120 KB Output is correct
3 Correct 155 ms 31044 KB Output is correct
4 Correct 159 ms 31024 KB Output is correct
5 Correct 153 ms 31128 KB Output is correct
6 Correct 157 ms 31160 KB Output is correct
7 Correct 157 ms 31112 KB Output is correct
8 Correct 21 ms 30796 KB Output is correct
9 Correct 19 ms 30844 KB Output is correct
10 Correct 19 ms 30768 KB Output is correct
11 Correct 255 ms 99436 KB Output is correct
12 Correct 260 ms 99456 KB Output is correct
13 Correct 269 ms 99652 KB Output is correct
14 Correct 250 ms 99608 KB Output is correct
15 Correct 268 ms 99684 KB Output is correct
16 Correct 290 ms 99304 KB Output is correct
17 Correct 256 ms 99352 KB Output is correct
18 Correct 263 ms 99292 KB Output is correct
19 Incorrect 24 ms 30976 KB Output isn't correct
20 Halted 0 ms 0 KB -