oj.uz

Submission #909945

# Submission time Handle Problem Language Result Execution time Memory
909945 2024-01-17T16:11:28 Z danikoynov Progression (NOI20_progression) C++14
70 / 100
 1137 ms 117160 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;
      |         ^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 373 ms 100720 KB Output is correct
2 Correct 138 ms 85636 KB Output is correct
3 Correct 137 ms 85576 KB Output is correct
4 Correct 136 ms 85760 KB Output is correct
5 Correct 138 ms 85748 KB Output is correct
6 Correct 136 ms 85596 KB Output is correct
7 Correct 148 ms 85584 KB Output is correct
8 Correct 16 ms 82524 KB Output is correct
9 Correct 17 ms 82520 KB Output is correct
10 Correct 16 ms 82524 KB Output is correct
11 Correct 366 ms 103760 KB Output is correct
12 Correct 368 ms 103648 KB Output is correct
13 Correct 368 ms 104168 KB Output is correct
14 Correct 390 ms 104188 KB Output is correct
15 Correct 363 ms 103832 KB Output is correct
16 Correct 362 ms 103568 KB Output is correct
17 Correct 391 ms 103740 KB Output is correct
18 Correct 365 ms 103648 KB Output is correct

Subtask #2
15.0 / 15.0

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

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 280 ms 83828 KB Output is correct
2 Correct 99 ms 80904 KB Output is correct
3 Correct 99 ms 81080 KB Output is correct
4 Correct 88 ms 80888 KB Output is correct
5 Correct 100 ms 81036 KB Output is correct
6 Correct 114 ms 80976 KB Output is correct
7 Correct 94 ms 80916 KB Output is correct
8 Correct 16 ms 80476 KB Output is correct
9 Correct 16 ms 80328 KB Output is correct
10 Correct 16 ms 80476 KB Output is correct
11 Correct 334 ms 83572 KB Output is correct
12 Correct 282 ms 83980 KB Output is correct
13 Correct 285 ms 83540 KB Output is correct
14 Correct 308 ms 83792 KB Output is correct
15 Correct 275 ms 83816 KB Output is correct
16 Correct 323 ms 84328 KB Output is correct
17 Correct 297 ms 84084 KB Output is correct
18 Correct 328 ms 84224 KB Output is correct
19 Correct 263 ms 83424 KB Output is correct
20 Correct 283 ms 83284 KB Output is correct
21 Correct 263 ms 83304 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 793 ms 109396 KB Output is correct
2 Correct 172 ms 82552 KB Output is correct
3 Correct 176 ms 83076 KB Output is correct
4 Correct 172 ms 82688 KB Output is correct
5 Correct 172 ms 82552 KB Output is correct
6 Correct 179 ms 82568 KB Output is correct
7 Correct 173 ms 82600 KB Output is correct
8 Correct 16 ms 82520 KB Output is correct
9 Correct 16 ms 82520 KB Output is correct
10 Correct 18 ms 82776 KB Output is correct
11 Correct 791 ms 109164 KB Output is correct
12 Correct 835 ms 109232 KB Output is correct
13 Correct 824 ms 109120 KB Output is correct
14 Correct 820 ms 109264 KB Output is correct
15 Correct 789 ms 109264 KB Output is correct
16 Correct 869 ms 109392 KB Output is correct
17 Correct 833 ms 109392 KB Output is correct
18 Correct 838 ms 109292 KB Output is correct
19 Correct 786 ms 109184 KB Output is correct
20 Correct 823 ms 109292 KB Output is correct
21 Correct 815 ms 109092 KB Output is correct

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 280 ms 83828 KB Output is correct
2 Correct 99 ms 80904 KB Output is correct
3 Correct 99 ms 81080 KB Output is correct
4 Correct 88 ms 80888 KB Output is correct
5 Correct 100 ms 81036 KB Output is correct
6 Correct 114 ms 80976 KB Output is correct
7 Correct 94 ms 80916 KB Output is correct
8 Correct 16 ms 80476 KB Output is correct
9 Correct 16 ms 80328 KB Output is correct
10 Correct 16 ms 80476 KB Output is correct
11 Correct 334 ms 83572 KB Output is correct
12 Correct 282 ms 83980 KB Output is correct
13 Correct 285 ms 83540 KB Output is correct
14 Correct 308 ms 83792 KB Output is correct
15 Correct 275 ms 83816 KB Output is correct
16 Correct 323 ms 84328 KB Output is correct
17 Correct 297 ms 84084 KB Output is correct
18 Correct 328 ms 84224 KB Output is correct
19 Correct 263 ms 83424 KB Output is correct
20 Correct 283 ms 83284 KB Output is correct
21 Correct 263 ms 83304 KB Output is correct
22 Correct 1137 ms 117160 KB Output is correct
23 Incorrect 188 ms 85832 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 373 ms 100720 KB Output is correct
2 Correct 138 ms 85636 KB Output is correct
3 Correct 137 ms 85576 KB Output is correct
4 Correct 136 ms 85760 KB Output is correct
5 Correct 138 ms 85748 KB Output is correct
6 Correct 136 ms 85596 KB Output is correct
7 Correct 148 ms 85584 KB Output is correct
8 Correct 16 ms 82524 KB Output is correct
9 Correct 17 ms 82520 KB Output is correct
10 Correct 16 ms 82524 KB Output is correct
11 Correct 366 ms 103760 KB Output is correct
12 Correct 368 ms 103648 KB Output is correct
13 Correct 368 ms 104168 KB Output is correct
14 Correct 390 ms 104188 KB Output is correct
15 Correct 363 ms 103832 KB Output is correct
16 Correct 362 ms 103568 KB Output is correct
17 Correct 391 ms 103740 KB Output is correct
18 Correct 365 ms 103648 KB Output is correct
19 Correct 17 ms 82520 KB Output is correct
20 Correct 17 ms 82528 KB Output is correct
21 Correct 17 ms 82524 KB Output is correct
22 Correct 17 ms 82524 KB Output is correct
23 Correct 16 ms 82520 KB Output is correct
24 Correct 16 ms 82524 KB Output is correct
25 Correct 17 ms 82520 KB Output is correct
26 Correct 18 ms 82520 KB Output is correct
27 Correct 18 ms 82524 KB Output is correct
28 Correct 19 ms 82520 KB Output is correct
29 Correct 17 ms 82524 KB Output is correct
30 Correct 18 ms 82524 KB Output is correct
31 Correct 16 ms 82524 KB Output is correct
32 Correct 17 ms 82388 KB Output is correct
33 Correct 17 ms 82524 KB Output is correct
34 Correct 17 ms 82448 KB Output is correct
35 Correct 18 ms 82524 KB Output is correct
36 Correct 18 ms 82524 KB Output is correct
37 Correct 19 ms 82520 KB Output is correct
38 Correct 19 ms 82436 KB Output is correct
39 Correct 18 ms 82520 KB Output is correct
40 Correct 280 ms 83828 KB Output is correct
41 Correct 99 ms 80904 KB Output is correct
42 Correct 99 ms 81080 KB Output is correct
43 Correct 88 ms 80888 KB Output is correct
44 Correct 100 ms 81036 KB Output is correct
45 Correct 114 ms 80976 KB Output is correct
46 Correct 94 ms 80916 KB Output is correct
47 Correct 16 ms 80476 KB Output is correct
48 Correct 16 ms 80328 KB Output is correct
49 Correct 16 ms 80476 KB Output is correct
50 Correct 334 ms 83572 KB Output is correct
51 Correct 282 ms 83980 KB Output is correct
52 Correct 285 ms 83540 KB Output is correct
53 Correct 308 ms 83792 KB Output is correct
54 Correct 275 ms 83816 KB Output is correct
55 Correct 323 ms 84328 KB Output is correct
56 Correct 297 ms 84084 KB Output is correct
57 Correct 328 ms 84224 KB Output is correct
58 Correct 263 ms 83424 KB Output is correct
59 Correct 283 ms 83284 KB Output is correct
60 Correct 263 ms 83304 KB Output is correct
61 Correct 793 ms 109396 KB Output is correct
62 Correct 172 ms 82552 KB Output is correct
63 Correct 176 ms 83076 KB Output is correct
64 Correct 172 ms 82688 KB Output is correct
65 Correct 172 ms 82552 KB Output is correct
66 Correct 179 ms 82568 KB Output is correct
67 Correct 173 ms 82600 KB Output is correct
68 Correct 16 ms 82520 KB Output is correct
69 Correct 16 ms 82520 KB Output is correct
70 Correct 18 ms 82776 KB Output is correct
71 Correct 791 ms 109164 KB Output is correct
72 Correct 835 ms 109232 KB Output is correct
73 Correct 824 ms 109120 KB Output is correct
74 Correct 820 ms 109264 KB Output is correct
75 Correct 789 ms 109264 KB Output is correct
76 Correct 869 ms 109392 KB Output is correct
77 Correct 833 ms 109392 KB Output is correct
78 Correct 838 ms 109292 KB Output is correct
79 Correct 786 ms 109184 KB Output is correct
80 Correct 823 ms 109292 KB Output is correct
81 Correct 815 ms 109092 KB Output is correct
82 Correct 1137 ms 117160 KB Output is correct
83 Incorrect 188 ms 85832 KB Output isn't correct
84 Halted 0 ms 0 KB -