Submission #1227022

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227022		jasonic	Progression (NOI20_progression)	C++20	9 / 100	81 ms	7496 KiB

Progression

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define fastIO cin.tie(0); ios::sync_with_stdio(false)

const int s = 550;

struct SD{
    int n;
    vector<ll> arr;
    vector<ll> pref;
    vector<ll> suff;
    vector<ll> longest;

    SD(vector<ll> a) {
        n = a.size()-2;
        if(n <= 0) return;
        arr = vector<ll>(n, 0);
        pref = vector<ll>(n/s + 1, -1);
        suff = vector<ll>(n/s + 1, 0);
        longest = vector<ll>(n/s + 1, 0);

        for(int i = 0; i < n; i++) {
            arr[i] = a[i+2] - a[i+1] - a[i+1] + a[i];
        }

        for(int i = 0; i*s < n; i++) {
            ll curr = 0;
            for(int j = 0; j < s && j + i*s < n; j++) {
                if(arr[j + i*s] == 0) curr++;
                else {
                    if(pref[i] == -1) pref[i] = curr;
                    curr = 0;
                }
                longest[i] = max(longest[i], curr);
            }
            if(pref[i] == -1) pref[i] = curr;
            suff[i] = curr;
        }

        // for(auto &i : arr) cout << i << ' '; cout << '\n';
        // for(auto &i : pref) cout << i << ' '; cout << '\n';
        // for(auto &i : suff) cout << i << ' '; cout << '\n';
        // for(auto &i : longest) cout << i << ' '; cout << '\n';
    }

    int qry(int ql, int qr) {

        if(ql < 0 || n <= qr) exit(0);

        ll ans = 0;

        // cout << ql << ' ' << qr << '\n';

        ll curr = 0;
        for(int i = ql; i <= qr;) {
            if(i % s == 0 && i + s - 1 <= qr) {
                curr += pref[i/s];
                if(pref[i/s] != s) {
                    ans = max(curr, ans);
                    curr = suff[i/s];
                }
                ans = max(ans, longest[i/s]);
                i += s;
            } else {
                if(arr[i] == 0) curr++;
                else {
                    ans = max(curr, ans);
                    curr = 0;
                }
                i++;
            }
            ans = max(curr, ans);
        }

        // cout << ans << '\n';
        
        return ans;
    }
};

int main() {
    fastIO;
    
    int n, q; cin >> n >> q;
    vector<ll> a(n); for(auto &i : a) cin >> i;

    SD sqrtdecomp(a);

    ll entire = n>2?sqrtdecomp.qry(0, n-3)+2:n;

    for(int qq = 1; qq <= q; qq++) {
        int op; cin >> op;

        if(op == 1) { // patch, i.e. add
            ll l, r, s, c; cin >> l >> r >> s >> c; l--, r--;
            // do nothing
        } else if (op == 2) { // rewrite, i.e. overwrite
            ll l, r, s, c; cin >> l >> r >> s >> c; l--, r--;
            entire = n;
        } else { // evaluate, i.e. find longest zero
            int l, r; cin >> l >> r; l--, r--;
            cout << entire << '\n';
        }
    }
    
    return 0;
}

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