oj.uz

Submission #901356

# Submission time Handle Problem Language Result Execution time Memory
901356 2024-01-09T11:04:18 Z 12345678 Progression (NOI20_progression) C++17
35 / 100
 279 ms 113792 KB 
#include <bits/stdc++.h>

using namespace std;

const int nx=3e5+5;
#define ll long long

ll n, q, v[nx], t, l, r;

struct gap
{
    ll type, g;
    gap(ll type=0, ll g=0): type(type), g(g){}
    friend bool operator==(const gap &lhs, const gap &rhs) {return lhs.type||rhs.type||lhs.g==rhs.g;}
    friend bool operator!=(const gap &lhs, const gap &rhs) {return !(lhs==rhs);}
};
gap opposite(gap o) { return gap(o.type, -o.g);}

struct segtree
{
    struct node
    {
        gap gapl, gapr;
        ll type, mx, mxl, mxr, vl, vr, sz;
        node(ll x=0, ll type=0): type(type), mx(1), mxl(1), mxr(1), vl(x), vr(x), gapl(gap(1)), gapr(gap(1)), sz(1) {}
        friend node operator+(const node &lhs, const node &rhs)
        {
            if (lhs.type) return rhs;
            if (rhs.type) return lhs;
            node res=node();
            gap gapl=gap(0, rhs.vl-lhs.vr), gapr=gap(0, lhs.vr-rhs.vl);
            res.vl=lhs.vl;
            res.vr=rhs.vr;
            res.sz=lhs.sz+rhs.sz;
            res.gapl=lhs.gapl.type?gapl:lhs.gapl;
            res.gapr=rhs.gapr.type?gapr:rhs.gapr;
            if (lhs.mxl!=lhs.sz||lhs.gapl!=gapl) res.mxl=lhs.mxl;
            else res.mxl=(gapl==rhs.gapl)?lhs.mxl+rhs.mxl:lhs.mxl+1;
            if (rhs.mxr!=rhs.sz||rhs.gapr!=gapr) res.mxr=rhs.mxr;
            else res.mxr=(gapr==lhs.gapr)?lhs.mxr+rhs.mxr:rhs.mxr+1;
            res.mx=max(lhs.mx, rhs.mx);
            if (opposite(lhs.gapr)==gapl) res.mx=max(res.mx, lhs.mxr+1);
            if (rhs.gapl==gapl) res.mx=max(res.mx, rhs.mxl+1);
            if (opposite(lhs.gapr)==gapl&&gapl==rhs.gapl) res.mx=max(res.mx, lhs.mxr+rhs.mxl);
            return res;
        }
    } d[4*nx];
    void build(int l, int r, int i)
    {
        if (l==r) return void(d[i]=node(v[l], 0));
        int md=(l+r)/2;
        build(l, md, 2*i);
        build(md+1, r, 2*i+1);
        d[i]=d[2*i]+d[2*i+1];
    }
    void show(int l, int r, int i)
    {
        cout<<"node "<<l<<' '<<r<<'\n';
        cout<<"max "<<d[i].mx<<' '<<d[i].mxl<<' '<<d[i].mxr<<'\n';
        cout<<"value "<<d[i].vl<<' '<<d[i].vr<<'\n';
        cout<<"gapl "<<d[i].gapl.type<<' '<<d[i].gapl.g<<'\n';
        cout<<"gapr "<<d[i].gapr.type<<' '<<d[i].gapr.g<<'\n';
        cout<<"sz "<<d[i].sz<<'\n';
        cout<<'\n';
        if (l==r) return;
        int md=(l+r)/2;
        show(l, md, 2*i);
        show(md+1, r, 2*i+1);
    }
    node query(int l, int r, int i, int ql, int qr)
    {
        if (qr<l||r<ql) return node(0, 1);
        if (ql<=l&&r<=qr) return d[i];
        int md=(l+r)/2;
        return query(l, md, 2*i, ql, qr)+query(md+1, r, 2*i+1, ql, qr);
    }
} s;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>q;
    for (int i=1; i<=n; i++) cin>>v[i];
    s.build(1, n, 1);
    //s.show(1, n, 1);
    while (q--)
    {
        cin>>t;
        if (t==1) continue;
        if (t==2) continue;
        if (t==3)
        {
            cin>>l>>r;
            cout<<s.query(1, n, 1, l, r).mx<<'\n';
        }
    }
}

Compilation message

Progression.cpp: In constructor 'segtree::node::node(long long int, long long int)':
Progression.cpp:24:36: warning: 'segtree::node::vr' will be initialized after [-Wreorder]
   24 |         ll type, mx, mxl, mxr, vl, vr, sz;
      |                                    ^~
Progression.cpp:23:13: warning:   'gap segtree::node::gapl' [-Wreorder]
   23 |         gap gapl, gapr;
      |             ^~~~
Progression.cpp:25:9: warning:   when initialized here [-Wreorder]
   25 |         node(ll x=0, ll type=0): type(type), mx(1), mxl(1), mxr(1), vl(x), vr(x), gapl(gap(1)), gapr(gap(1)), sz(1) {}
      |         ^~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 77 ms 106300 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 105052 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 228 ms 107092 KB Output is correct
2 Correct 94 ms 107860 KB Output is correct
3 Correct 93 ms 107864 KB Output is correct
4 Correct 87 ms 107848 KB Output is correct
5 Correct 91 ms 108116 KB Output is correct
6 Correct 100 ms 107964 KB Output is correct
7 Correct 93 ms 107860 KB Output is correct
8 Correct 14 ms 105052 KB Output is correct
9 Correct 15 ms 105052 KB Output is correct
10 Correct 14 ms 105208 KB Output is correct
11 Correct 261 ms 111832 KB Output is correct
12 Correct 233 ms 113088 KB Output is correct
13 Correct 250 ms 111728 KB Output is correct
14 Correct 258 ms 111828 KB Output is correct
15 Correct 229 ms 113064 KB Output is correct
16 Correct 262 ms 113792 KB Output is correct
17 Correct 256 ms 113748 KB Output is correct
18 Correct 266 ms 113708 KB Output is correct
19 Correct 279 ms 113132 KB Output is correct
20 Correct 239 ms 113040 KB Output is correct
21 Correct 250 ms 112968 KB Output is correct

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 88 ms 106128 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 107092 KB Output is correct
2 Correct 94 ms 107860 KB Output is correct
3 Correct 93 ms 107864 KB Output is correct
4 Correct 87 ms 107848 KB Output is correct
5 Correct 91 ms 108116 KB Output is correct
6 Correct 100 ms 107964 KB Output is correct
7 Correct 93 ms 107860 KB Output is correct
8 Correct 14 ms 105052 KB Output is correct
9 Correct 15 ms 105052 KB Output is correct
10 Correct 14 ms 105208 KB Output is correct
11 Correct 261 ms 111832 KB Output is correct
12 Correct 233 ms 113088 KB Output is correct
13 Correct 250 ms 111728 KB Output is correct
14 Correct 258 ms 111828 KB Output is correct
15 Correct 229 ms 113064 KB Output is correct
16 Correct 262 ms 113792 KB Output is correct
17 Correct 256 ms 113748 KB Output is correct
18 Correct 266 ms 113708 KB Output is correct
19 Correct 279 ms 113132 KB Output is correct
20 Correct 239 ms 113040 KB Output is correct
21 Correct 250 ms 112968 KB Output is correct
22 Incorrect 134 ms 110852 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 77 ms 106300 KB Output isn't correct
2 Halted 0 ms 0 KB -