oj.uz

Submission #909943

# Submission time Handle Problem Language Result Execution time Memory
909943 2024-01-17T16:09:16 Z danikoynov Progression (NOI20_progression) C++14
46 / 100
 3000 ms 119236 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 3003 ms 93808 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 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 292 ms 87288 KB Output is correct
2 Correct 96 ms 83024 KB Output is correct
3 Correct 112 ms 82932 KB Output is correct
4 Correct 95 ms 83028 KB Output is correct
5 Correct 96 ms 83240 KB Output is correct
6 Correct 95 ms 83168 KB Output is correct
7 Correct 97 ms 83280 KB Output is correct
8 Correct 16 ms 80476 KB Output is correct
9 Correct 16 ms 80368 KB Output is correct
10 Correct 15 ms 80496 KB Output is correct
11 Correct 306 ms 88432 KB Output is correct
12 Correct 285 ms 89824 KB Output is correct
13 Correct 306 ms 88404 KB Output is correct
14 Correct 311 ms 88700 KB Output is correct
15 Correct 287 ms 89672 KB Output is correct
16 Correct 312 ms 90496 KB Output is correct
17 Correct 307 ms 90196 KB Output is correct
18 Correct 322 ms 90388 KB Output is correct
19 Correct 283 ms 89640 KB Output is correct
20 Correct 283 ms 90264 KB Output is correct
21 Correct 290 ms 89752 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 942 ms 116304 KB Output is correct
2 Correct 191 ms 85756 KB Output is correct
3 Correct 187 ms 85860 KB Output is correct
4 Correct 189 ms 85844 KB Output is correct
5 Correct 188 ms 85996 KB Output is correct
6 Correct 190 ms 85888 KB Output is correct
7 Correct 187 ms 85868 KB Output is correct
8 Correct 16 ms 82524 KB Output is correct
9 Correct 15 ms 82460 KB Output is correct
10 Correct 17 ms 82524 KB Output is correct
11 Correct 934 ms 115572 KB Output is correct
12 Correct 911 ms 119192 KB Output is correct
13 Correct 925 ms 115500 KB Output is correct
14 Correct 930 ms 115552 KB Output is correct
15 Correct 913 ms 118864 KB Output is correct
16 Correct 955 ms 118668 KB Output is correct
17 Correct 938 ms 118864 KB Output is correct
18 Correct 924 ms 119120 KB Output is correct
19 Correct 903 ms 119176 KB Output is correct
20 Correct 928 ms 118736 KB Output is correct
21 Correct 909 ms 118900 KB Output is correct

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 292 ms 87288 KB Output is correct
2 Correct 96 ms 83024 KB Output is correct
3 Correct 112 ms 82932 KB Output is correct
4 Correct 95 ms 83028 KB Output is correct
5 Correct 96 ms 83240 KB Output is correct
6 Correct 95 ms 83168 KB Output is correct
7 Correct 97 ms 83280 KB Output is correct
8 Correct 16 ms 80476 KB Output is correct
9 Correct 16 ms 80368 KB Output is correct
10 Correct 15 ms 80496 KB Output is correct
11 Correct 306 ms 88432 KB Output is correct
12 Correct 285 ms 89824 KB Output is correct
13 Correct 306 ms 88404 KB Output is correct
14 Correct 311 ms 88700 KB Output is correct
15 Correct 287 ms 89672 KB Output is correct
16 Correct 312 ms 90496 KB Output is correct
17 Correct 307 ms 90196 KB Output is correct
18 Correct 322 ms 90388 KB Output is correct
19 Correct 283 ms 89640 KB Output is correct
20 Correct 283 ms 90264 KB Output is correct
21 Correct 290 ms 89752 KB Output is correct
22 Execution timed out 3050 ms 119236 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 3003 ms 93808 KB Time limit exceeded
2 Halted 0 ms 0 KB -