Submission #1243159

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243159		fskarica	Mosaic (IOI24_mosaic)	C++20	20 / 100	92 ms	26808 KiB

mosaic

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define fi first
#define se second
#define pii pair<int, int>

const int MAX = 4e5 + 10;
vector <int> v;
int n, m, q;
ll pref[MAX], prefStep[MAX], sufStep[MAX];
ll prefX[MAX], prefY[MAX];

int pos(int a, int b) {
    return n - 2 - (a - b);
}

ll fPref(int lt, int rt) {
    return pref[rt] - pref[lt] + v[lt];
}

ll fPrefStep(int lt, int rt) {
    ll ret = prefStep[rt] - prefStep[lt] + v[lt] * (lt + 1);
    ret -= lt * fPref(lt, rt);

    return ret;
}

ll fSufStep(int lt, int rt) {
    ll ret = sufStep[lt] - sufStep[rt] + v[rt] * (m - rt);
    ret -= (m - rt - 1) * fPref(lt, rt);

    return ret;
}

vector<long long> mosaic(vector<int> X, vector<int> Y, vector<int> R, vector<int> R2, vector<int> S, vector<int> S2) {
    n = X.size();

    int last = X[1];
    for (int i = 1; i < n; i++) {
        v.push_back((1 - last) * (1 - Y[i]));
        last = v.back();
    }
    reverse(v.begin(), v.end());

    for (int i = 2; i < n; i++) {
        v.push_back((1 - v.back()) * (1 - X[i]));
    }

    prefX[0] = X[0], prefY[0] = Y[0];
    for (int i = 1; i < n; i++) {
        prefX[i] = prefX[i - 1] + X[i];
        prefY[i] = prefY[i - 1] + Y[i];
    }

    m = v.size();
    if (m > 0) pref[0] = v[0], prefStep[0] = v[0], sufStep[m - 1] = v[m - 1];
    for (int i = 1; i < m; i++) {
        pref[i] = pref[i - 1] + v[i];
        prefStep[i] = prefStep[i - 1] + v[i] * (i + 1);
        sufStep[m - i - 1] = sufStep[m - i] + v[m - i - 1] * (i + 1);
    }

    vector <ll> ret;
    q = R.size();
    for (int i = 0; i < q; i++) {
        int x = R[i];
        int x2 = R2[i];
        int y = S[i];
        int y2 = S2[i];

        ll sol = 0;
        if (x == 0) {
            sol += prefX[y2] - prefX[y] + X[y];
            x++;
        }
        if (y == 0 && x <= x2) {
            sol += prefY[x2] - prefY[x] + Y[x];
            y++;
        }

        if (x > x2 || y > y2) {
            ret.push_back(sol);
            continue;
        }

        int lt = pos(x2, y);
        int rt = pos(x, y2);
        int stepSz = min(x2 - x, y2 - y);

        ll sredina = fPref(lt + stepSz, rt - stepSz) * (stepSz + 1);
        ll pocetak = fPrefStep(lt, lt + stepSz - 1);
        ll kraj    = fSufStep(rt - stepSz + 1, rt);

        sol += sredina + pocetak + kraj;

        ret.push_back(sol);
    }

    return ret;
}

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 0 / 7
• Subtask 3: 7 / 7
• Subtask 4: 0 / 10
• Subtask 5: 8 / 8
• Subtask 6: 0 / 22
• Subtask 7: 0 / 19
• Subtask 8: 0 / 22