oj.uz

Submission #909595

# Submission time Handle Problem Language Result Execution time Memory
909595 2024-01-17T09:39:18 Z danikoynov Progression (NOI20_progression) C++14
55 / 100
 1245 ms 122904 KB 
/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
const int maxn = 3e5 + 10;

int n, q;
ll d[maxn], b[maxn];

void input()
{
    cin >> n >> q;
    for (int i = 1; i <= n; i ++)
    {
        cin >> d[i];
        b[i] = d[i] - d[i - 1];
    }
}

int query(int l, int r)
{
    if (l == r)
        return 1;

    int cnt = 1, mx = 0;
    for (int i = l + 2; i <= r; i ++)
    {
        if (b[i] == b[i -1])
            cnt ++;
        else
        {
            if (cnt > mx)
                mx = cnt;
            cnt = 1;
        }
    }
    if (cnt > mx)
        mx = cnt;
    return mx + 1;
}

const ll inf = 1e18;

struct line
{
    ll k, m;

    line(ll _k = 0, ll _m = -inf)
    {
        k = _k;
        m = _m;
    }

    ll math(ll x)
    {
        return k * x + m;
    }

    void add_line(line cur)
    {
        k += cur.k;
        m += cur.m;
    }

    void set_line(line cur)
    {
        k = cur.k;
        m = cur.m;
    }
};

line set_lazy[4 * maxn], add_lazy[4 * maxn];
int set_tag[4 * maxn], add_tag[4 * maxn];

void push_lazy(int root, int left, int right)
{
    int mid = (left + right) / 2;
    if (set_tag[root] == 1)
    {
        ///li_chao[root].set_line(set_lazy[root]);
        if (left != right)
        {
            set_tag[root * 2] = 1;
            set_tag[root * 2 + 1] = 1;
            add_tag[root * 2] = 0;
            add_tag[root * 2 + 1] = 0;
            set_lazy[root * 2] = set_lazy[root];
            set_lazy[root * 2 + 1] = set_lazy[root];
            add_lazy[root * 2] = line(0, 0);
            add_lazy[root * 2 + 1] = line(0, 0);
        }
        else
        {
            d[left] = set_lazy[root].math(left);
        }
        set_tag[root] = 0;
        set_lazy[root] = line(0, 0);
    }
    if (add_tag[root] == 1)
    {

        if (left != right)
        {
            add_tag[root * 2] = 1;
            add_tag[root * 2 + 1] = 1;
            add_lazy[root * 2].add_line(add_lazy[root]);
            add_lazy[root * 2 + 1].add_line(add_lazy[root]);
        }
                else
        {
            d[left] += add_lazy[root].math(left);
        }
        add_tag[root] = 0;
        add_lazy[root] = line(0, 0);
    }
}

void set_line(int root, int left, int right, int qleft, int qright, line cur)
{
    push_lazy(root, left, right);
    if (left > qright || right < qleft)
        return;

    if (left >= qleft && right <= qright)
    {
        set_tag[root] = 1;
        set_lazy[root] = cur;
        push_lazy(root, left, right);
        return;
    }

    int mid = (left + right) / 2;
    set_line(root * 2, left, mid, qleft, qright, cur);
    set_line(root * 2 + 1, mid + 1, right, qleft, qright, cur);
}

void add_line(int root, int left, int right, int qleft, int qright, line cur)
{
    push_lazy(root, left, right);
    if (left > qright || right < qleft)
        return;

    if (left >= qleft && right <= qright)
    {
        add_tag[root] = 1;
        add_lazy[root] = cur;
        push_lazy(root, left, right);
        return;
    }

    int mid = (left + right) / 2;
    add_line(root * 2, left, mid, qleft, qright, cur);
    add_line(root * 2 + 1, mid + 1, right, qleft, qright, cur);
}


ll query(int root, int left, int right, int pos)
{
    push_lazy(root, left, right);
    if (left == right)
        return d[left];

    int mid = (left + right) / 2;
    if (pos <= mid)
        return query(root * 2, left, mid, pos);
    return query(root * 2 + 1, mid + 1, right, pos);
}
/**void add_line_concious(int root, int left, int right, line cur)
{
    push_lazy(root, left, right);
    int mid = (left + right) / 2;
    if (li_chao[root].math(mid) < cur.math(mid))
        swap(li_chao[root], cur);

    if (left == right)
        return;

    if ()
}*/

struct node
{
    int pref, suff, lon, len;
    ll fs, ls;

    node(int _pref = 0, int _suff = 0, int _lon = 0, ll _fs = -inf, ll _ls = inf, int _len = 0)
    {
        len = _len;
        pref = _pref;
        suff = _suff;
        lon = _lon;
        fs = _fs;
        ls = _ls;
    }
};

node merge_nodes(node lf, node rf)
{
    if (lf.ls == inf)
    return rf;
    if (rf.fs == -inf)
        return lf;

    node mf;
    mf.fs = lf.fs;
    mf.ls = rf.ls;

    mf.pref = lf.pref;
    if (lf.pref == lf.len && lf.ls == rf.fs)
        mf.pref += rf.pref;
    mf.suff = rf.suff;
    if (rf.suff == rf.len && rf.fs == lf.ls)
        mf.suff += lf.suff;

    mf.lon = max(lf.lon, rf.lon);
    if (lf.ls == rf.fs)
        mf.lon = max(mf.lon, lf.suff + rf.pref);

    mf.len = lf.len + rf.len;
    return mf;
}

node tree[4 * maxn];

pair < ll, ll > lazy[4 * maxn];
pair < int, int > tag[4 * maxn];
void make_lazy(int root, int left, int right)
{
    if (tag[root].first)
    {
        int len = right - left + 1;
        tree[root] = node(len, len, len, lazy[root].first, lazy[root].first, len);
        if (left != right)
        {
            tag[root * 2].first = 1;
            tag[root * 2 + 1].first = 1;
            tag[root * 2].second = 0;
            tag[root * 2 + 1].second = 0;
            lazy[root * 2].second = 0;
            lazy[root * 2 + 1].second = 0;

            lazy[root * 2].first = lazy[root].first;
            lazy[root * 2 + 1].first = lazy[root].first;
        }
        lazy[root].first = 0;
        tag[root].first = 0;
    }
    if (tag[root].second)
    {
        tree[root].fs += lazy[root].second;
        tree[root].ls += lazy[root].second;
        if (left != right)
        {
            tag[root * 2].second = 1;
            tag[root * 2 + 1].second = 1;
            lazy[root * 2].second = lazy[root].second;
            lazy[root * 2 + 1].second = lazy[root].second;
        }
        tag[root].second = 0;
        lazy[root].second = 0;
    }
}

void range_update_set(int root, int left, int right, int qleft, int qright, ll val)
{
    make_lazy(root, left, right);
    if (left > qright || right < qleft)
        return;

    if (left >= qleft && right <= qright)
    {
        lazy[root].first =val;
        tag[root].first = 1;
        make_lazy(root, left, right);
        return;
    }

    int mid = (left + right) / 2;
    range_update_set(root * 2, left, mid, qleft, qright, val);
    range_update_set(root * 2 + 1, mid + 1, right, qleft, qright, val);

    tree[root] = merge_nodes(tree[root * 2], tree[root * 2 + 1]);
}

void range_update_add(int root, int left, int right, int qleft, int qright, ll val)
{
    make_lazy(root, left, right);
    if (left > qright || right < qleft)
        return;

    if (left >= qleft && right <= qright)
    {
        lazy[root].second =val;
        tag[root].second = 1;
        make_lazy(root, left, right);
        return;
    }

    int mid = (left + right) / 2;
    range_update_add(root * 2, left, mid, qleft, qright, val);
    range_update_add(root * 2 + 1, mid + 1, right, qleft, qright, val);

    tree[root] = merge_nodes(tree[root * 2], tree[root * 2 + 1]);
}

node query_range(int root, int left, int right, int qleft, int qright)
{
    push_lazy(root, left, right);
    if (left > qright || right < qleft)
        return node();

    if (left >= qleft && right <= qright)
    {
        return tree[root];
    }

    int mid = (left + right) / 2;
    return merge_nodes(query_range(root * 2, left, mid, qleft, qright),
                       query_range(root * 2 + 1, mid + 1, right, qleft, qright));
}

void build_tree(int root, int left, int right)
{
    if (left == right)
    {
        tree[root] = node(1, 1, 1, b[left], b[left], 1);
        return;
    }

    int mid = (left + right) / 2;
    build_tree(root * 2, left, mid);
    build_tree(root * 2 + 1, mid + 1, right);

    tree[root] = merge_nodes(tree[root * 2], tree[root * 2 + 1]);
}

void simulate()
{
    build_tree(1, 1, n);
    for (int i = 1; i <= q; i ++)
    {
        int type, l, r;
        ll s, c;
        cin >> type >> l >> r;
        if (type == 3)
        {
            node cur = query_range(1, 1, n, l + 1, r);
            cout << cur.lon + 1 << endl;
            ///cout << query(l, r) << endl;
        }
        else if (type == 1)
        {
            cin >> s >> c;
            add_line(1, 1, n, l, r, line(c, - l * c + s));
            /*for (int j = l; j <= r; j ++)
            {
                d[j] += s + (ll)(j - l) * c;
            }*/
            range_update_add(1, 1, n, l + 1, r, c);
            range_update_add(1, 1, n, l, l, s);
            /**b[l] += s;
            for (int j = l + 1; j <= r; j ++)
                b[j] += c;*/
                if (r + 1 <= n)
            range_update_set(1, 1, n, r + 1, r + 1, query(1, 1, n, r + 1) - query(1, 1, n, r));
            ///b[r + 1] = query(1, 1, n, r + 1) - query(1, 1, n, r); ///d[r + 1] - d[r];
        }
        else
        {
            cin >> s >> c;
            set_line(1, 1, n, l, r, line(c, - l * c + s));
            /**for (int j = l; j <= r; j ++)
            {
                d[j] = s + (ll)(j - l) * c;
            }*/
            range_update_set(1, 1, n, l + 1, r, c);
            //for (int j = l + 1; j <= r; j ++)
              //  b[j] = c;
            range_update_set(1, 1, n, l, l, query(1, 1, n, l) - query(1, 1, n, l - 1));
            ///b[l] = query(1, 1, n, l) - query(1, 1, n, l - 1); ///d[l] - d[l - 1];
            if (r + 1 <= n)
            range_update_set(1, 1, n, r + 1, r + 1, query(1, 1, n, r + 1) - query(1, 1, n, r));
            ///b[r + 1] = query(1, 1, n, r + 1) - query(1, 1, n, r); ///d[r + 1] - d[r];
        }

        /**for (int j = 1; j <= n; j ++)
        {

            b[j] = d[j] - d[j - 1];
        }*/
        /**for (int j = 1; j <= n; j ++)
            cout << d[j] << " ";
        cout << endl;*/
    }
}
void solve()
{
    input();
    simulate();
}

int main()
{
    speed();
    solve();
    return 0;
}

Compilation message

Progression.cpp: In function 'void push_lazy(int, int, int)':
Progression.cpp:93:9: warning: unused variable 'mid' [-Wunused-variable]
   93 |     int mid = (left + right) / 2;
      |         ^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 361 ms 99576 KB Output is correct
2 Correct 137 ms 85732 KB Output is correct
3 Correct 137 ms 85588 KB Output is correct
4 Correct 137 ms 85588 KB Output is correct
5 Correct 136 ms 85840 KB Output is correct
6 Correct 136 ms 85700 KB Output is correct
7 Correct 136 ms 85612 KB Output is correct
8 Correct 17 ms 82524 KB Output is correct
9 Correct 17 ms 82712 KB Output is correct
10 Correct 17 ms 82524 KB Output is correct
11 Correct 378 ms 99692 KB Output is correct
12 Correct 386 ms 99584 KB Output is correct
13 Correct 381 ms 99920 KB Output is correct
14 Correct 371 ms 100328 KB Output is correct
15 Correct 361 ms 99924 KB Output is correct
16 Correct 364 ms 99532 KB Output is correct
17 Correct 358 ms 99460 KB Output is correct
18 Correct 385 ms 99208 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 82512 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 304 ms 89732 KB Output is correct
2 Correct 99 ms 83028 KB Output is correct
3 Correct 93 ms 83028 KB Output is correct
4 Correct 92 ms 82928 KB Output is correct
5 Correct 93 ms 83280 KB Output is correct
6 Correct 94 ms 83164 KB Output is correct
7 Correct 98 ms 83072 KB Output is correct
8 Correct 17 ms 80472 KB Output is correct
9 Correct 18 ms 80476 KB Output is correct
10 Correct 17 ms 80476 KB Output is correct
11 Correct 316 ms 88416 KB Output is correct
12 Correct 365 ms 89848 KB Output is correct
13 Correct 301 ms 88436 KB Output is correct
14 Correct 398 ms 88508 KB Output is correct
15 Correct 286 ms 89648 KB Output is correct
16 Correct 348 ms 90460 KB Output is correct
17 Correct 374 ms 90364 KB Output is correct
18 Correct 383 ms 90456 KB Output is correct
19 Correct 317 ms 89656 KB Output is correct
20 Correct 301 ms 89680 KB Output is correct
21 Correct 336 ms 89696 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 862 ms 119080 KB Output is correct
2 Correct 178 ms 85840 KB Output is correct
3 Correct 176 ms 85856 KB Output is correct
4 Correct 172 ms 85752 KB Output is correct
5 Correct 174 ms 86096 KB Output is correct
6 Correct 189 ms 85764 KB Output is correct
7 Correct 175 ms 85776 KB Output is correct
8 Correct 17 ms 82524 KB Output is correct
9 Correct 17 ms 82524 KB Output is correct
10 Correct 17 ms 82524 KB Output is correct
11 Correct 834 ms 115412 KB Output is correct
12 Correct 846 ms 118648 KB Output is correct
13 Correct 821 ms 115536 KB Output is correct
14 Correct 849 ms 115572 KB Output is correct
15 Correct 852 ms 118960 KB Output is correct
16 Correct 884 ms 118804 KB Output is correct
17 Correct 876 ms 118792 KB Output is correct
18 Correct 836 ms 119084 KB Output is correct
19 Correct 851 ms 118776 KB Output is correct
20 Correct 863 ms 118608 KB Output is correct
21 Correct 836 ms 118608 KB Output is correct

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 304 ms 89732 KB Output is correct
2 Correct 99 ms 83028 KB Output is correct
3 Correct 93 ms 83028 KB Output is correct
4 Correct 92 ms 82928 KB Output is correct
5 Correct 93 ms 83280 KB Output is correct
6 Correct 94 ms 83164 KB Output is correct
7 Correct 98 ms 83072 KB Output is correct
8 Correct 17 ms 80472 KB Output is correct
9 Correct 18 ms 80476 KB Output is correct
10 Correct 17 ms 80476 KB Output is correct
11 Correct 316 ms 88416 KB Output is correct
12 Correct 365 ms 89848 KB Output is correct
13 Correct 301 ms 88436 KB Output is correct
14 Correct 398 ms 88508 KB Output is correct
15 Correct 286 ms 89648 KB Output is correct
16 Correct 348 ms 90460 KB Output is correct
17 Correct 374 ms 90364 KB Output is correct
18 Correct 383 ms 90456 KB Output is correct
19 Correct 317 ms 89656 KB Output is correct
20 Correct 301 ms 89680 KB Output is correct
21 Correct 336 ms 89696 KB Output is correct
22 Incorrect 1245 ms 122904 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 361 ms 99576 KB Output is correct
2 Correct 137 ms 85732 KB Output is correct
3 Correct 137 ms 85588 KB Output is correct
4 Correct 137 ms 85588 KB Output is correct
5 Correct 136 ms 85840 KB Output is correct
6 Correct 136 ms 85700 KB Output is correct
7 Correct 136 ms 85612 KB Output is correct
8 Correct 17 ms 82524 KB Output is correct
9 Correct 17 ms 82712 KB Output is correct
10 Correct 17 ms 82524 KB Output is correct
11 Correct 378 ms 99692 KB Output is correct
12 Correct 386 ms 99584 KB Output is correct
13 Correct 381 ms 99920 KB Output is correct
14 Correct 371 ms 100328 KB Output is correct
15 Correct 361 ms 99924 KB Output is correct
16 Correct 364 ms 99532 KB Output is correct
17 Correct 358 ms 99460 KB Output is correct
18 Correct 385 ms 99208 KB Output is correct
19 Incorrect 19 ms 82512 KB Output isn't correct
20 Halted 0 ms 0 KB -