oj.uz

Submission #909411

# Submission time Handle Problem Language Result Execution time Memory
909411 2024-01-17T07:56:18 Z danikoynov Progression (NOI20_progression) C++14
15 / 100
 3000 ms 73620 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 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

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.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 59996 KB Output is correct
2 Correct 12 ms 60000 KB Output is correct
3 Correct 12 ms 59740 KB Output is correct
4 Correct 12 ms 59740 KB Output is correct
5 Correct 12 ms 59976 KB Output is correct
6 Correct 12 ms 59736 KB Output is correct
7 Correct 12 ms 59744 KB Output is correct
8 Correct 13 ms 59992 KB Output is correct
9 Correct 12 ms 59996 KB Output is correct
10 Correct 13 ms 59876 KB Output is correct
11 Correct 13 ms 59996 KB Output is correct
12 Correct 14 ms 59992 KB Output is correct
13 Correct 13 ms 59996 KB Output is correct
14 Correct 13 ms 59996 KB Output is correct
15 Correct 13 ms 59992 KB Output is correct
16 Correct 13 ms 59992 KB Output is correct
17 Correct 13 ms 59996 KB Output is correct
18 Correct 12 ms 59996 KB Output is correct
19 Correct 12 ms 59740 KB Output is correct
20 Correct 12 ms 59920 KB Output is correct
21 Correct 12 ms 59876 KB Output is correct

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 66792 KB Output is correct
2 Correct 73 ms 61776 KB Output is correct
3 Correct 67 ms 61780 KB Output is correct
4 Correct 73 ms 61648 KB Output is correct
5 Correct 68 ms 61828 KB Output is correct
6 Correct 72 ms 61868 KB Output is correct
7 Correct 74 ms 61692 KB Output is correct
8 Correct 13 ms 59912 KB Output is correct
9 Correct 12 ms 59792 KB Output is correct
10 Correct 13 ms 59892 KB Output is correct
11 Execution timed out 3050 ms 63596 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 403 ms 73620 KB Output is correct
2 Correct 120 ms 61728 KB Output is correct
3 Correct 102 ms 61856 KB Output is correct
4 Correct 102 ms 61852 KB Output is correct
5 Correct 102 ms 61816 KB Output is correct
6 Correct 105 ms 61788 KB Output is correct
7 Correct 104 ms 61888 KB Output is correct
8 Correct 12 ms 59980 KB Output is correct
9 Correct 12 ms 59740 KB Output is correct
10 Correct 13 ms 59980 KB Output is correct
11 Execution timed out 3072 ms 69588 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 66792 KB Output is correct
2 Correct 73 ms 61776 KB Output is correct
3 Correct 67 ms 61780 KB Output is correct
4 Correct 73 ms 61648 KB Output is correct
5 Correct 68 ms 61828 KB Output is correct
6 Correct 72 ms 61868 KB Output is correct
7 Correct 74 ms 61692 KB Output is correct
8 Correct 13 ms 59912 KB Output is correct
9 Correct 12 ms 59792 KB Output is correct
10 Correct 13 ms 59892 KB Output is correct
11 Execution timed out 3050 ms 63596 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

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