oj.uz

Submission #909604

# Submission time Handle Problem Language Result Execution time Memory
909604 2024-01-17T09:42:55 Z danikoynov Progression (NOI20_progression) C++14
55 / 100
 1172 ms 114048 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)
{
    make_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 353 ms 100056 KB Output is correct
2 Correct 140 ms 84560 KB Output is correct
3 Correct 138 ms 84560 KB Output is correct
4 Correct 133 ms 84488 KB Output is correct
5 Correct 142 ms 84700 KB Output is correct
6 Correct 141 ms 84564 KB Output is correct
7 Correct 138 ms 84576 KB Output is correct
8 Correct 17 ms 82520 KB Output is correct
9 Correct 17 ms 82524 KB Output is correct
10 Correct 17 ms 82524 KB Output is correct
11 Correct 349 ms 100184 KB Output is correct
12 Correct 375 ms 100212 KB Output is correct
13 Correct 361 ms 100296 KB Output is correct
14 Correct 360 ms 100820 KB Output is correct
15 Correct 352 ms 100180 KB Output is correct
16 Correct 371 ms 99920 KB Output is correct
17 Correct 352 ms 100076 KB Output is correct
18 Correct 349 ms 95860 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 82524 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 316 ms 83716 KB Output is correct
2 Correct 103 ms 80980 KB Output is correct
3 Correct 94 ms 80992 KB Output is correct
4 Correct 91 ms 81012 KB Output is correct
5 Correct 95 ms 81144 KB Output is correct
6 Correct 94 ms 81184 KB Output is correct
7 Correct 95 ms 80940 KB Output is correct
8 Correct 17 ms 80476 KB Output is correct
9 Correct 16 ms 80476 KB Output is correct
10 Correct 17 ms 80472 KB Output is correct
11 Correct 324 ms 83804 KB Output is correct
12 Correct 308 ms 83836 KB Output is correct
13 Correct 322 ms 83564 KB Output is correct
14 Correct 337 ms 83540 KB Output is correct
15 Correct 294 ms 84140 KB Output is correct
16 Correct 341 ms 84048 KB Output is correct
17 Correct 319 ms 84376 KB Output is correct
18 Correct 314 ms 84168 KB Output is correct
19 Correct 293 ms 83540 KB Output is correct
20 Correct 275 ms 83300 KB Output is correct
21 Correct 272 ms 83304 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 875 ms 109268 KB Output is correct
2 Correct 172 ms 82604 KB Output is correct
3 Correct 177 ms 82788 KB Output is correct
4 Correct 178 ms 82572 KB Output is correct
5 Correct 174 ms 82580 KB Output is correct
6 Correct 175 ms 82680 KB Output is correct
7 Correct 177 ms 82520 KB Output is correct
8 Correct 17 ms 82520 KB Output is correct
9 Correct 18 ms 82524 KB Output is correct
10 Correct 18 ms 82400 KB Output is correct
11 Correct 845 ms 109440 KB Output is correct
12 Correct 831 ms 109244 KB Output is correct
13 Correct 841 ms 109660 KB Output is correct
14 Correct 831 ms 109492 KB Output is correct
15 Correct 832 ms 109276 KB Output is correct
16 Correct 856 ms 109612 KB Output is correct
17 Correct 840 ms 109392 KB Output is correct
18 Correct 845 ms 109488 KB Output is correct
19 Correct 818 ms 109212 KB Output is correct
20 Correct 819 ms 109392 KB Output is correct
21 Correct 846 ms 109428 KB Output is correct

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 316 ms 83716 KB Output is correct
2 Correct 103 ms 80980 KB Output is correct
3 Correct 94 ms 80992 KB Output is correct
4 Correct 91 ms 81012 KB Output is correct
5 Correct 95 ms 81144 KB Output is correct
6 Correct 94 ms 81184 KB Output is correct
7 Correct 95 ms 80940 KB Output is correct
8 Correct 17 ms 80476 KB Output is correct
9 Correct 16 ms 80476 KB Output is correct
10 Correct 17 ms 80472 KB Output is correct
11 Correct 324 ms 83804 KB Output is correct
12 Correct 308 ms 83836 KB Output is correct
13 Correct 322 ms 83564 KB Output is correct
14 Correct 337 ms 83540 KB Output is correct
15 Correct 294 ms 84140 KB Output is correct
16 Correct 341 ms 84048 KB Output is correct
17 Correct 319 ms 84376 KB Output is correct
18 Correct 314 ms 84168 KB Output is correct
19 Correct 293 ms 83540 KB Output is correct
20 Correct 275 ms 83300 KB Output is correct
21 Correct 272 ms 83304 KB Output is correct
22 Incorrect 1172 ms 114048 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 353 ms 100056 KB Output is correct
2 Correct 140 ms 84560 KB Output is correct
3 Correct 138 ms 84560 KB Output is correct
4 Correct 133 ms 84488 KB Output is correct
5 Correct 142 ms 84700 KB Output is correct
6 Correct 141 ms 84564 KB Output is correct
7 Correct 138 ms 84576 KB Output is correct
8 Correct 17 ms 82520 KB Output is correct
9 Correct 17 ms 82524 KB Output is correct
10 Correct 17 ms 82524 KB Output is correct
11 Correct 349 ms 100184 KB Output is correct
12 Correct 375 ms 100212 KB Output is correct
13 Correct 361 ms 100296 KB Output is correct
14 Correct 360 ms 100820 KB Output is correct
15 Correct 352 ms 100180 KB Output is correct
16 Correct 371 ms 99920 KB Output is correct
17 Correct 352 ms 100076 KB Output is correct
18 Correct 349 ms 95860 KB Output is correct
19 Incorrect 18 ms 82524 KB Output isn't correct
20 Halted 0 ms 0 KB -