oj.uz

Submission #909944

# Submission time Handle Problem Language Result Execution time Memory
909944 2024-01-17T16:11:06 Z danikoynov Progression (NOI20_progression) C++14
61 / 100
 3000 ms 113680 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 = 2; j <= n; j ++)
        {
            if (b[j] != query_range(1, 1, n, j, j).fs)
            {
                while(true);
            }
        }*/
        /**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;
      |         ^~~
Progression.cpp: In function 'void simulate()':
Progression.cpp:378:13: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  378 |             for (int j = l + 1; j <= r; j ++)
      |             ^~~
Progression.cpp:380:17: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  380 |                 if (r + 1 <= n)
      |                 ^~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3072 ms 93444 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 82524 KB Output is correct
2 Correct 17 ms 82556 KB Output is correct
3 Correct 16 ms 82524 KB Output is correct
4 Correct 16 ms 82524 KB Output is correct
5 Correct 15 ms 82524 KB Output is correct
6 Correct 17 ms 82524 KB Output is correct
7 Correct 15 ms 82524 KB Output is correct
8 Correct 17 ms 82520 KB Output is correct
9 Correct 17 ms 82524 KB Output is correct
10 Correct 20 ms 82524 KB Output is correct
11 Correct 18 ms 82524 KB Output is correct
12 Correct 18 ms 82520 KB Output is correct
13 Correct 17 ms 82524 KB Output is correct
14 Correct 17 ms 82520 KB Output is correct
15 Correct 17 ms 82524 KB Output is correct
16 Correct 17 ms 82520 KB Output is correct
17 Correct 19 ms 82524 KB Output is correct
18 Correct 18 ms 82484 KB Output is correct
19 Correct 16 ms 82524 KB Output is correct
20 Correct 16 ms 82428 KB Output is correct
21 Correct 16 ms 82520 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 282 ms 83792 KB Output is correct
2 Correct 97 ms 80976 KB Output is correct
3 Correct 93 ms 80980 KB Output is correct
4 Correct 94 ms 80980 KB Output is correct
5 Correct 95 ms 80976 KB Output is correct
6 Correct 99 ms 81108 KB Output is correct
7 Correct 115 ms 81008 KB Output is correct
8 Correct 15 ms 80476 KB Output is correct
9 Correct 15 ms 80344 KB Output is correct
10 Correct 15 ms 80436 KB Output is correct
11 Correct 312 ms 83452 KB Output is correct
12 Correct 286 ms 83740 KB Output is correct
13 Correct 343 ms 83540 KB Output is correct
14 Correct 316 ms 83464 KB Output is correct
15 Correct 278 ms 83796 KB Output is correct
16 Correct 324 ms 84136 KB Output is correct
17 Correct 313 ms 84052 KB Output is correct
18 Correct 315 ms 84348 KB Output is correct
19 Correct 278 ms 83284 KB Output is correct
20 Correct 292 ms 83684 KB Output is correct
21 Correct 282 ms 83284 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 892 ms 109264 KB Output is correct
2 Correct 192 ms 82612 KB Output is correct
3 Correct 194 ms 82520 KB Output is correct
4 Correct 187 ms 82520 KB Output is correct
5 Correct 187 ms 82552 KB Output is correct
6 Correct 186 ms 82520 KB Output is correct
7 Correct 186 ms 82676 KB Output is correct
8 Correct 16 ms 82520 KB Output is correct
9 Correct 15 ms 82524 KB Output is correct
10 Correct 16 ms 82524 KB Output is correct
11 Correct 886 ms 109272 KB Output is correct
12 Correct 914 ms 109404 KB Output is correct
13 Correct 888 ms 109424 KB Output is correct
14 Correct 925 ms 109460 KB Output is correct
15 Correct 932 ms 109136 KB Output is correct
16 Correct 998 ms 109328 KB Output is correct
17 Correct 993 ms 109328 KB Output is correct
18 Correct 970 ms 109432 KB Output is correct
19 Correct 970 ms 109132 KB Output is correct
20 Correct 941 ms 109296 KB Output is correct
21 Correct 934 ms 109352 KB Output is correct

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 282 ms 83792 KB Output is correct
2 Correct 97 ms 80976 KB Output is correct
3 Correct 93 ms 80980 KB Output is correct
4 Correct 94 ms 80980 KB Output is correct
5 Correct 95 ms 80976 KB Output is correct
6 Correct 99 ms 81108 KB Output is correct
7 Correct 115 ms 81008 KB Output is correct
8 Correct 15 ms 80476 KB Output is correct
9 Correct 15 ms 80344 KB Output is correct
10 Correct 15 ms 80436 KB Output is correct
11 Correct 312 ms 83452 KB Output is correct
12 Correct 286 ms 83740 KB Output is correct
13 Correct 343 ms 83540 KB Output is correct
14 Correct 316 ms 83464 KB Output is correct
15 Correct 278 ms 83796 KB Output is correct
16 Correct 324 ms 84136 KB Output is correct
17 Correct 313 ms 84052 KB Output is correct
18 Correct 315 ms 84348 KB Output is correct
19 Correct 278 ms 83284 KB Output is correct
20 Correct 292 ms 83684 KB Output is correct
21 Correct 282 ms 83284 KB Output is correct
22 Execution timed out 3046 ms 113680 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3072 ms 93444 KB Time limit exceeded
2 Halted 0 ms 0 KB -