oj.uz

Submission #909421

# Submission time Handle Problem Language Result Execution time Memory
909421 2024-01-17T08:03:31 Z danikoynov Progression (NOI20_progression) C++14
15 / 100
 3000 ms 49744 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 ()
}*/



void simulate()
{

    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 3030 ms 45828 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 41308 KB Output is correct
2 Correct 9 ms 41308 KB Output is correct
3 Correct 9 ms 41452 KB Output is correct
4 Correct 9 ms 41308 KB Output is correct
5 Correct 9 ms 41304 KB Output is correct
6 Correct 9 ms 41308 KB Output is correct
7 Correct 10 ms 41308 KB Output is correct
8 Correct 10 ms 41304 KB Output is correct
9 Correct 9 ms 41308 KB Output is correct
10 Correct 10 ms 41308 KB Output is correct
11 Correct 10 ms 41308 KB Output is correct
12 Correct 9 ms 41308 KB Output is correct
13 Correct 10 ms 41308 KB Output is correct
14 Correct 9 ms 41464 KB Output is correct
15 Correct 10 ms 41308 KB Output is correct
16 Correct 10 ms 41308 KB Output is correct
17 Correct 10 ms 41304 KB Output is correct
18 Correct 11 ms 41308 KB Output is correct
19 Correct 9 ms 41308 KB Output is correct
20 Correct 9 ms 41416 KB Output is correct
21 Correct 9 ms 41308 KB Output is correct

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 44584 KB Output is correct
2 Correct 69 ms 41956 KB Output is correct
3 Correct 62 ms 42032 KB Output is correct
4 Correct 60 ms 42064 KB Output is correct
5 Correct 63 ms 42068 KB Output is correct
6 Correct 66 ms 42068 KB Output is correct
7 Correct 80 ms 42068 KB Output is correct
8 Correct 9 ms 41308 KB Output is correct
9 Correct 8 ms 41408 KB Output is correct
10 Correct 9 ms 41436 KB Output is correct
11 Execution timed out 3048 ms 43736 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 392 ms 49744 KB Output is correct
2 Correct 104 ms 41532 KB Output is correct
3 Correct 99 ms 41680 KB Output is correct
4 Correct 101 ms 41556 KB Output is correct
5 Correct 100 ms 41552 KB Output is correct
6 Correct 100 ms 41560 KB Output is correct
7 Correct 102 ms 41528 KB Output is correct
8 Correct 10 ms 41408 KB Output is correct
9 Correct 9 ms 41308 KB Output is correct
10 Correct 9 ms 41304 KB Output is correct
11 Execution timed out 3095 ms 49528 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 44584 KB Output is correct
2 Correct 69 ms 41956 KB Output is correct
3 Correct 62 ms 42032 KB Output is correct
4 Correct 60 ms 42064 KB Output is correct
5 Correct 63 ms 42068 KB Output is correct
6 Correct 66 ms 42068 KB Output is correct
7 Correct 80 ms 42068 KB Output is correct
8 Correct 9 ms 41308 KB Output is correct
9 Correct 8 ms 41408 KB Output is correct
10 Correct 9 ms 41436 KB Output is correct
11 Execution timed out 3048 ms 43736 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 3030 ms 45828 KB Time limit exceeded
2 Halted 0 ms 0 KB -