Submission #1278657

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278657		ducdev	Progression (NOI20_progression)	C++17	24 / 100	90 ms	8264 KiB

Progression

// Author: 4uckd3v - Nguyen Cao Duc
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAX_N = 3e5;
const int MOD = 1e9 + 7;

struct Query {
    int type, l, r, s, c;

    Query() {};
    Query(int type, int l, int r) : type(type), l(l), r(r) {};
    Query(int type, int l, int r, int s, int c) : type(type), l(l), r(r), s(s), c(c) {};
};

int n, q;
int a[MAX_N + 5];
vector<Query> queries;

namespace SUBTASK_1 {
    const int N = MAX_N;

    bool checkSubtask() {
        for (const Query &query : queries)
            if (query.l != 1 || query.r != n) return false;
        return true;
    };

    void Solve() {
        int res = 1, cnt = 1;
        if (n > 1) res = 2, cnt = 2;

        for (int i = 3; i <= n; i++) {
            if (a[i] - a[i - 1] == a[i - 1] - a[i - 2])
                cnt++;
            else
                cnt = 2;
            res = max(res, cnt);
        };

        for (const Query &query : queries) {
            int type = query.type, l = query.l, r = query.r;
            if (type == 3) {
                cout << res << '\n';
                continue;
            };

            if (type == 2) res = n;
        };
    };
};  // namespace SUBTASK_1

namespace SUBTASK_2 {
    const int N = 1000;
    const int Q = 1000;

    ll d[N + 5];

    void Solve() {
        for (int i = 1; i <= n; i++) d[i] = a[i];

        for (Query &query : queries) {
            int type = query.type, l = query.l, r = query.r;

            if (type == 3) {
                int res = 1, cnt = 1;
                if (r - l + 1 > 1) res = 2, cnt = 2;

                for (int i = l + 2; i <= r; i++) {
                    if (d[i] - d[i - 1] == d[i - 1] - d[i - 2])
                        cnt++;
                    else
                        cnt = 2;
                    res = max(res, cnt);
                };

                cout << res << '\n';

                continue;
            };

            int s = query.s, c = query.c;
            for (int i = l; i <= r; i++) {
                if (type == 2) d[i] = 0;
                d[i] += (ll)s + (ll)(i - l) * c;
            };
        };
    };
};  // namespace SUBTASK_2

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if (fopen("MAIN.INP", "r")) {
        freopen("MAIN.INP", "r", stdin);
        freopen("MAIN.OUT", "w", stdout);
    };

    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    };

    queries.resize(q);
    for (Query &query : queries) {
        cin >> query.type >> query.l >> query.r;
        if (query.type != 3) cin >> query.s >> query.c;
    };

    if (SUBTASK_1::checkSubtask())
        return SUBTASK_1::Solve(), 0;
    SUBTASK_2::Solve();
};

Compilation message (stderr)

Progression.cpp: In function 'int main()':
Progression.cpp:97:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |         freopen("MAIN.INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Progression.cpp:98:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |         freopen("MAIN.OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 15 / 15
• Subtask 3: 0 / 35
• Subtask 4: 0 / 11
• Subtask 5: 0 / 13
• Subtask 6: 0 / 17