Submission #909411

#	Time	Username	Problem	Language	Result	Execution time	Memory
909411		danikoynov	Progression (NOI20_progression)	C++14	15 / 100	3072 ms	73620 KiB

Progression

/**
 ____ ____ ____ ____ ____ ____
||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 li_chao[4 * maxn], 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);
        }
        set_tag[root] = 0;
        set_lazy[root] = line(0, 0);
    }
    if (add_tag[root] == 1)
    {
        li_chao[root].add_line(add_lazy[root]);
        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]);
        }
        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);
}

void build(int root, int left, int right)
{
    if (left == right)
    {
        li_chao[root] = line(0, d[left]);
        return;
    }

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

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

    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 ()
}*/



void simulate()
{
    build(1, 1, n);
    for (int i = 1; i <= q; i ++)
    {
        int type, l, r;
        ll s, c;
        cin >> type >> l >> r;
        if (type == 3)
        {
            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;
            }*/
            b[l] += s;
            for (int j = l + 1; j <= r; j ++)
                b[j] += c;
            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;
            }*/
            for (int j = l + 1; j <= r; j ++)
                b[j] = c;
            b[l] = query(1, 1, n, l) - query(1, 1, n, l - 1); ///d[l] - d[l - 1];
            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 (stderr)

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: 0 / 9
• Subtask 2: 15 / 15
• Subtask 3: 0 / 35
• Subtask 4: 0 / 11
• Subtask 5: 0 / 13
• Subtask 6: 0 / 17