제출 #1243135

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1243135		fskarica	모자이크 (IOI24_mosaic)	C++20	0 / 100	72 ms	30276 KiB

mosaic

#include <bits/stdc++.h>

using namespace std;

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

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

ll pos(ll a, ll b) {
//    cout << "pos - " << a << " " << b << "\n";

    return n - 2 - (a - b);
}

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

    for (ll i = 1; i <= n; i++) {
        mat[1][i] = X[i - 1];
        mat[i][1] = Y[i - 1];
    }

    for (ll i = 2; i <= n; i++) {
        for (ll j = 2; j <= n; j++) {
            mat[i][j] = (1 - mat[i - 1][j]) * (1 - mat[i][j - 1]);
        }
    }

//    cout << "mat:\n";
//    for (ll i = 1; i <= n; i++) {
//        for (ll j = 1; j <= n; j++) cout << mat[i][j] << " ";
//        cout << "\n";
//    }
//    cout << "\n";

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

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

//    for (auto e : v) cout << e << " "; cout << "\n";

//    cout << pos(R2[1], S[1] + 1) << " " << pos(R[1], S2[1]) << "\n";

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

    m = v.size();
    pref[0] = v[0], prefStep[0] = v[0], sufStep[m - 1] = v[m - 1];
    for (ll 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);
    }

//    cout << "\n";
//    cout << "pref     - "; for (ll i = 0; i < m; i++) cout << pref[i] << " "; cout << "\n";
//    cout << "prefStep - "; for (ll i = 0; i < m; i++) cout << prefStep[i] << " "; cout << "\n";
//    cout << "sufStep  - "; for (ll i = 0; i < m; i++) cout << sufStep[i] << " "; cout << "\n";
//    cout << "\n";

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

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

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

//        cout << "query " << i << " -> " << lt << " " << rt << " " << stepSz << "\n";

        ll sredina = (pref[rt - stepSz] - pref[lt + stepSz - 1]) * (stepSz + 1);
        ll pocetak = (prefStep[lt + stepSz - 1] - prefStep[lt] + v[lt] * (lt + 1)) - lt * (pref[lt + stepSz - 1] - prefStep[lt] + v[lt]);
        ll kraj    = (sufStep[rt - stepSz + 1] - sufStep[rt] + v[rt] * (m - rt)) - (m - rt - 1) * (pref[rt] - pref[rt - stepSz + 1] + v[rt - stepSz + 1]);

//        cout << sredina << " " << pocetak << " " << kraj << "\n";

        sol += sredina + pocetak + kraj;

        ret.push_back(sol);
    }

    return ret;
}

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