oj.uz

Submission #426316

# Submission time Handle Problem Language Result Execution time Memory
426316 2021-06-13T17:39:50 Z TLP39 Progression (NOI20_progression) C++14
55 / 100
 1739 ms 100628 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;
    int len,cl;
    ll dl;
    int cr;
    ll dr;
    int 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,2);
        }
    }

    return ans;
}

play mod(play x,dev y,int l,int 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;
}

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

void build(int v,int st,int ed)
{
    if(st==ed)
    {
        seg[v]={a[st],a[st],1,1,0,1,0,1};
        bottom[v]=true;
        return;
    }
    int 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(int v,int l,int 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(int v,int st,int ed,int l,int 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);
    int 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(int v,int st,int ed,int l,int r)
{
    if(l==st && r==ed) return seg[v];
    push_down(v,l,r);
    int 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("%d %d",&n,&q);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    for(int i=0;i<1200040;i++)
    {
        marked[i]=false;
        bottom[i]=false;
        lz[i]={false,0,0};
    }
    build(1,1,n);
    int ty,l,r;
    ll s,c;
    dev temp;
    while(q--)
    {
        scanf("%d",&ty);
        if(ty==1)
        {
            scanf("%d %d %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("%d %d %lld %lld",&l,&r,&s,&c);
            temp={true,s+(1-l)*c,c};
            upd(1,l,r,1,n,temp);
        }
        else
        {
            scanf("%d %d",&l,&r);
            printf("%d\n",(que(1,l,r,1,n)).c);
        }
    }
}

Compilation message

Progression.cpp: In function 'int main()':
Progression.cpp:188:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  188 |     scanf("%d %d",&n,&q);
      |     ~~~~~^~~~~~~~~~~~~~~
Progression.cpp:189:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  189 |     for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
      |                           ~~~~~^~~~~~~~~~~~~~
Progression.cpp:202:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  202 |         scanf("%d",&ty);
      |         ~~~~~^~~~~~~~~~
Progression.cpp:205:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  205 |             scanf("%d %d %lld %lld",&l,&r,&s,&c);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Progression.cpp:211:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  211 |             scanf("%d %d %lld %lld",&l,&r,&s,&c);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Progression.cpp:217:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  217 |             scanf("%d %d",&l,&r);
      |             ~~~~~^~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 282 ms 99196 KB Output is correct
2 Correct 162 ms 33932 KB Output is correct
3 Correct 176 ms 34036 KB Output is correct
4 Correct 165 ms 34016 KB Output is correct
5 Correct 167 ms 34116 KB Output is correct
6 Correct 170 ms 34088 KB Output is correct
7 Correct 167 ms 33988 KB Output is correct
8 Correct 20 ms 30796 KB Output is correct
9 Correct 18 ms 30816 KB Output is correct
10 Correct 18 ms 30796 KB Output is correct
11 Correct 262 ms 99184 KB Output is correct
12 Correct 270 ms 99268 KB Output is correct
13 Correct 255 ms 99416 KB Output is correct
14 Correct 273 ms 99500 KB Output is correct
15 Correct 268 ms 99400 KB Output is correct
16 Correct 287 ms 99124 KB Output is correct
17 Correct 268 ms 99152 KB Output is correct
18 Correct 263 ms 99080 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 30984 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 361 ms 97648 KB Output is correct
2 Correct 166 ms 33524 KB Output is correct
3 Correct 143 ms 33584 KB Output is correct
4 Correct 140 ms 33468 KB Output is correct
5 Correct 152 ms 33644 KB Output is correct
6 Correct 159 ms 33732 KB Output is correct
7 Correct 189 ms 33528 KB Output is correct
8 Correct 19 ms 30796 KB Output is correct
9 Correct 20 ms 30796 KB Output is correct
10 Correct 18 ms 30796 KB Output is correct
11 Correct 518 ms 96404 KB Output is correct
12 Correct 374 ms 97808 KB Output is correct
13 Correct 426 ms 96412 KB Output is correct
14 Correct 460 ms 96324 KB Output is correct
15 Correct 389 ms 97736 KB Output is correct
16 Correct 510 ms 98244 KB Output is correct
17 Correct 454 ms 98192 KB Output is correct
18 Correct 490 ms 98316 KB Output is correct
19 Correct 399 ms 97612 KB Output is correct
20 Correct 460 ms 97560 KB Output is correct
21 Correct 373 ms 97556 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 862 ms 100580 KB Output is correct
2 Correct 208 ms 34052 KB Output is correct
3 Correct 212 ms 34108 KB Output is correct
4 Correct 220 ms 34124 KB Output is correct
5 Correct 227 ms 34144 KB Output is correct
6 Correct 214 ms 34116 KB Output is correct
7 Correct 223 ms 34168 KB Output is correct
8 Correct 18 ms 30796 KB Output is correct
9 Correct 18 ms 30796 KB Output is correct
10 Correct 18 ms 30796 KB Output is correct
11 Correct 944 ms 97192 KB Output is correct
12 Correct 854 ms 100544 KB Output is correct
13 Correct 849 ms 97128 KB Output is correct
14 Correct 764 ms 97236 KB Output is correct
15 Correct 708 ms 100296 KB Output is correct
16 Correct 795 ms 100468 KB Output is correct
17 Correct 948 ms 100512 KB Output is correct
18 Correct 836 ms 100628 KB Output is correct
19 Correct 859 ms 100432 KB Output is correct
20 Correct 739 ms 100332 KB Output is correct
21 Correct 797 ms 100368 KB Output is correct

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 361 ms 97648 KB Output is correct
2 Correct 166 ms 33524 KB Output is correct
3 Correct 143 ms 33584 KB Output is correct
4 Correct 140 ms 33468 KB Output is correct
5 Correct 152 ms 33644 KB Output is correct
6 Correct 159 ms 33732 KB Output is correct
7 Correct 189 ms 33528 KB Output is correct
8 Correct 19 ms 30796 KB Output is correct
9 Correct 20 ms 30796 KB Output is correct
10 Correct 18 ms 30796 KB Output is correct
11 Correct 518 ms 96404 KB Output is correct
12 Correct 374 ms 97808 KB Output is correct
13 Correct 426 ms 96412 KB Output is correct
14 Correct 460 ms 96324 KB Output is correct
15 Correct 389 ms 97736 KB Output is correct
16 Correct 510 ms 98244 KB Output is correct
17 Correct 454 ms 98192 KB Output is correct
18 Correct 490 ms 98316 KB Output is correct
19 Correct 399 ms 97612 KB Output is correct
20 Correct 460 ms 97560 KB Output is correct
21 Correct 373 ms 97556 KB Output is correct
22 Incorrect 1739 ms 99864 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 282 ms 99196 KB Output is correct
2 Correct 162 ms 33932 KB Output is correct
3 Correct 176 ms 34036 KB Output is correct
4 Correct 165 ms 34016 KB Output is correct
5 Correct 167 ms 34116 KB Output is correct
6 Correct 170 ms 34088 KB Output is correct
7 Correct 167 ms 33988 KB Output is correct
8 Correct 20 ms 30796 KB Output is correct
9 Correct 18 ms 30816 KB Output is correct
10 Correct 18 ms 30796 KB Output is correct
11 Correct 262 ms 99184 KB Output is correct
12 Correct 270 ms 99268 KB Output is correct
13 Correct 255 ms 99416 KB Output is correct
14 Correct 273 ms 99500 KB Output is correct
15 Correct 268 ms 99400 KB Output is correct
16 Correct 287 ms 99124 KB Output is correct
17 Correct 268 ms 99152 KB Output is correct
18 Correct 263 ms 99080 KB Output is correct
19 Incorrect 20 ms 30984 KB Output isn't correct
20 Halted 0 ms 0 KB -