oj.uz

Submission #426276

# Submission time Handle Problem Language Result Execution time Memory
426276 2021-06-13T16:32:13 Z TLP39 Progression (NOI20_progression) C++14
55 / 100
 1452 ms 84324 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,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,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:184:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  184 |     scanf("%d %d",&n,&q);
      |     ~~~~~^~~~~~~~~~~~~~~
Progression.cpp:185:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  185 |     for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
      |                           ~~~~~^~~~~~~~~~~~~~
Progression.cpp:198:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  198 |         scanf("%d",&ty);
      |         ~~~~~^~~~~~~~~~
Progression.cpp:201:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  201 |             scanf("%d %d %lld %lld",&l,&r,&s,&c);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Progression.cpp:207:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  207 |             scanf("%d %d %lld %lld",&l,&r,&s,&c);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Progression.cpp:213:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  213 |             scanf("%d %d",&l,&r);
      |             ~~~~~^~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 292 ms 82748 KB Output is correct
2 Correct 160 ms 34020 KB Output is correct
3 Correct 182 ms 33988 KB Output is correct
4 Correct 190 ms 33996 KB Output is correct
5 Correct 169 ms 34124 KB Output is correct
6 Correct 167 ms 34184 KB Output is correct
7 Correct 163 ms 34060 KB Output is correct
8 Correct 19 ms 30780 KB Output is correct
9 Correct 21 ms 30796 KB Output is correct
10 Correct 18 ms 30836 KB Output is correct
11 Correct 290 ms 82724 KB Output is correct
12 Correct 253 ms 82752 KB Output is correct
13 Correct 251 ms 83052 KB Output is correct
14 Correct 295 ms 83124 KB Output is correct
15 Correct 243 ms 83012 KB Output is correct
16 Correct 243 ms 82680 KB Output is correct
17 Correct 268 ms 82760 KB Output is correct
18 Correct 287 ms 82756 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 30924 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 360 ms 81180 KB Output is correct
2 Correct 193 ms 33524 KB Output is correct
3 Correct 140 ms 33444 KB Output is correct
4 Correct 138 ms 33440 KB Output is correct
5 Correct 148 ms 33636 KB Output is correct
6 Correct 173 ms 33656 KB Output is correct
7 Correct 170 ms 33704 KB Output is correct
8 Correct 16 ms 30796 KB Output is correct
9 Correct 18 ms 30780 KB Output is correct
10 Correct 17 ms 30796 KB Output is correct
11 Correct 390 ms 79920 KB Output is correct
12 Correct 360 ms 81220 KB Output is correct
13 Correct 419 ms 79924 KB Output is correct
14 Correct 421 ms 79812 KB Output is correct
15 Correct 359 ms 81196 KB Output is correct
16 Correct 480 ms 81824 KB Output is correct
17 Correct 433 ms 81732 KB Output is correct
18 Correct 416 ms 81968 KB Output is correct
19 Correct 402 ms 81284 KB Output is correct
20 Correct 349 ms 81136 KB Output is correct
21 Correct 444 ms 81148 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 673 ms 84084 KB Output is correct
2 Correct 205 ms 34152 KB Output is correct
3 Correct 209 ms 34136 KB Output is correct
4 Correct 207 ms 34172 KB Output is correct
5 Correct 205 ms 34080 KB Output is correct
6 Correct 236 ms 34336 KB Output is correct
7 Correct 223 ms 34164 KB Output is correct
8 Correct 19 ms 30820 KB Output is correct
9 Correct 21 ms 30856 KB Output is correct
10 Correct 18 ms 30796 KB Output is correct
11 Correct 738 ms 80876 KB Output is correct
12 Correct 716 ms 84056 KB Output is correct
13 Correct 746 ms 80904 KB Output is correct
14 Correct 711 ms 80800 KB Output is correct
15 Correct 647 ms 83908 KB Output is correct
16 Correct 708 ms 84088 KB Output is correct
17 Correct 711 ms 84184 KB Output is correct
18 Correct 728 ms 84324 KB Output is correct
19 Correct 694 ms 84128 KB Output is correct
20 Correct 708 ms 84132 KB Output is correct
21 Correct 733 ms 84036 KB Output is correct

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 360 ms 81180 KB Output is correct
2 Correct 193 ms 33524 KB Output is correct
3 Correct 140 ms 33444 KB Output is correct
4 Correct 138 ms 33440 KB Output is correct
5 Correct 148 ms 33636 KB Output is correct
6 Correct 173 ms 33656 KB Output is correct
7 Correct 170 ms 33704 KB Output is correct
8 Correct 16 ms 30796 KB Output is correct
9 Correct 18 ms 30780 KB Output is correct
10 Correct 17 ms 30796 KB Output is correct
11 Correct 390 ms 79920 KB Output is correct
12 Correct 360 ms 81220 KB Output is correct
13 Correct 419 ms 79924 KB Output is correct
14 Correct 421 ms 79812 KB Output is correct
15 Correct 359 ms 81196 KB Output is correct
16 Correct 480 ms 81824 KB Output is correct
17 Correct 433 ms 81732 KB Output is correct
18 Correct 416 ms 81968 KB Output is correct
19 Correct 402 ms 81284 KB Output is correct
20 Correct 349 ms 81136 KB Output is correct
21 Correct 444 ms 81148 KB Output is correct
22 Incorrect 1452 ms 83616 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 292 ms 82748 KB Output is correct
2 Correct 160 ms 34020 KB Output is correct
3 Correct 182 ms 33988 KB Output is correct
4 Correct 190 ms 33996 KB Output is correct
5 Correct 169 ms 34124 KB Output is correct
6 Correct 167 ms 34184 KB Output is correct
7 Correct 163 ms 34060 KB Output is correct
8 Correct 19 ms 30780 KB Output is correct
9 Correct 21 ms 30796 KB Output is correct
10 Correct 18 ms 30836 KB Output is correct
11 Correct 290 ms 82724 KB Output is correct
12 Correct 253 ms 82752 KB Output is correct
13 Correct 251 ms 83052 KB Output is correct
14 Correct 295 ms 83124 KB Output is correct
15 Correct 243 ms 83012 KB Output is correct
16 Correct 243 ms 82680 KB Output is correct
17 Correct 268 ms 82760 KB Output is correct
18 Correct 287 ms 82756 KB Output is correct
19 Incorrect 18 ms 30924 KB Output isn't correct
20 Halted 0 ms 0 KB -