Submission #682165

#	Time	Username	Problem	Language	Result	Execution time	Memory
682165		vuavisao	Progression (NOI20_progression)	C++14	24 / 100	3087 ms	24140 KiB

Progression

#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define ll long long
using namespace std;

const ll N = 3e5 + 10;

struct que {
    ll type = 0;
    ll l = 0, r = 0;
    ll s = 0, c = 0;
    que() {};
    friend istream& operator >> (istream& is, que& other) {
        is >> other.type >> other.l >> other.r;
        if(other.type <= 2) is >> other.s >> other.c;
        return is;
    }
};

ll n, q;
ll a[N];
que qq[N];

namespace sub1 {
    bool check() {
        for(ll i = 1; i <= q; ++ i) {
            if(qq[i].l != 1 || qq[i].r != n) return false;
        }
        return true;
    }

    ll res = 1;
    void solve() {
        for(ll i = 1, j; i < n; i = j - 1) {
            j = i + 1;
            ll s = a[j] - a[i];
            while(j <= n && a[j] - a[j - 1] == s) ++ j;
            res = max(res, j - i);
        }
        for(ll i = 1; i <= q; ++ i) {
            const auto& psy = qq[i];
            if(psy.type == 3) cout << res << '\n';
            else if(psy.type == 2) {
                res = n;
            }
        }
    }
}

namespace sub2 {
    void solve() {
        auto get_far = [&] (ll l, ll r) -> ll {
            ll res = 1;
            for(ll i = l, j; i < r; i = j - 1) {
                j = i + 1;
                ll s = a[j] - a[i];
                while(j <= r && a[j] - a[j - 1] == s) ++ j;
                res = max(res, j - i);
            }
            return res;
        };
        for(ll i = 1; i <= q; ++ i) {
            const auto& psy = qq[i];
            ll type = psy.type;
            if(type == 1) {
                ll add[2] = {psy.s, psy.c};
                for(ll i = psy.l; i <= psy.r; ++ i) {
                    a[i] += add[0];
                    add[0] += add[1];
                }
            }
            else if(type == 2) {
                ll add[2] = {psy.s, psy.c};
                for(ll i = psy.l; i <= psy.r; ++ i) {
                    a[i] = add[0];
                    add[0] += add[1];
                }
            }
            else {
//                cout << psy.l << ' ' << psy.r << '\n';
                cout << get_far(psy.l, psy.r) << '\n';
            }
        }
    }
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if (fopen("Progression.inp", "r")) {
        freopen("Progression.inp", "r", stdin);
        freopen("Progression.out", "w", stdout);
    }
    cin >> n >> q;
    for(ll i = 1; i <= n; ++ i) cin >> a[i];
    for(ll i = 1; i <= q; ++ i) cin >> qq[i];
    if(sub1::check()) {
        sub1::solve();
        return 0;
    }
//    if(sub3::check()) {
//        sub3::solve();
//        return 0;
//    }
    sub2::solve();
    return 0;
}

/// Code by vuavisao

Compilation message (stderr)

Progression.cpp: In function 'int32_t main()':
Progression.cpp:93:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |         freopen("Progression.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Progression.cpp:94:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |         freopen("Progression.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