Submission #1224093

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224093		jasonic	Progression (NOI20_progression)	C++20	0 / 100	133 ms	7492 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;
        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;
                    longest[i] = max(longest[i], curr);
                    curr = 0;
                }
            }
            longest[i] = max(longest[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) {

        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);

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

        if(op == 1) { // patch, i.e. add
            assert(op == 3);
        } else if (op == 2) { // rewrite, i.e. override
            assert(op == 3);
        } else { // evaluate, i.e. find longest zero
            int l, r; cin >> l >> r; l--, r--;
            if(l < r-2) {
                cout << sqrtdecomp.qry(l, r-2)+2;
            } else {
                cout << r-l+1;
            }
        }
        if(qq < q) cout << "\n";
    }
    
    return 0;
}

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