Submission #1105459

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105459		jerzyk	Mosaic (IOI24_mosaic)	C++17	100 / 100	147 ms	63868 KiB

mosaic

#include <bits/stdc++.h>
#include "mosaic.h"

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL;
const int II = 2 * 1000 * 1000 * 1000;
const ll M = 1000LL * 1000LL * 1000LL + 7LL;
const int N = 1000 * 1000 + 7;
ll tab[N][5], sum[N][5];
ll ar[N], rev[N];

bool F(int a, int b)
{
    return !(a | b);
}

void DoBas(int n)
{
    int r = min(3, n);
    for(int j = 2; j <= r; ++j)
    {
        tab[n - j + 1][j] = F(tab[n - j + 1][j - 1], tab[n - j + 3][j - 1]);
        for(int i = n - j; i >= 1; --i)
            tab[i][j] = F(tab[i + 1][j], tab[i][j - 1]);
        for(int i = n - j + 2; i <= 2 * (n - j + 1) - 1; ++i)
            tab[i][j] = F(tab[i - 1][j], tab[i + 2][j - 1]);
    }
    for(int j = 1; j <= r; ++j)
        for(int i = 1; i <= 2 * (n - j + 1) - 1; ++i)
            sum[i][j] = tab[i][j] + sum[i - 1][j];

    /*for(int j = 1; j <= 3; ++j)
    {
        for(int i = 1; i <= 2 * (n - j + 1) - 1; ++i)
            cerr << tab[i][j] << " ";
        cerr << "\n";
    }*/

    if(r < 3) return;

    for(int i = 1; i <= 2 * n - 5; ++i)
        ar[i] = ar[i - 1] + (ll)i * (ll)tab[i][3];
    for(int i = 1; i <= 2 * n - 5; ++i)
        rev[i] = rev[i - 1] + (ll)(-i) * (ll)tab[i][3];

}

inline ll S(int a, int b, int r)
{
    return sum[b][r] - sum[a - 1][r];
}

ll A(int a, int b, int s)
{
    ll ans = ar[b] - ar[a - 1];
    ans += (ll)(s - a) * (ll)(sum[b][3] - sum[a - 1][3]);
    return ans;
}

ll R(int a, int b, int s)
{
    ll ans = rev[b] - rev[a - 1];
    ans += (ll)(s + b) * (ll)(sum[b][3] - sum[a - 1][3]);
    return ans;
}

ll WS(int a, int b, int d)
{
    ll ans = A(a, a + d - 2, 1);
    ans += R(b - d + 2, b, 1);
    ans += (ll)d * (ll)(sum[b - d + 1][3] - sum[a + d - 2][3]);
    return ans;
}

ll Query(int n, int i1, int i2, int j1, int j2)
{
    ll ans = 0LL;
    if(i1 == 1)
    {
        ans += S(n + j1 - 1, n + j2 - 1, 1);
        i1 = 2;
    }
    //cerr << j1 << " " << j2 << " Xd " << ans << "\n";
    if(i1 > i2) return ans;
    if(j1 == 1)
    {
        ans += S(n - i2 + 1, n - i1 + 1, 1);
        j1 = 2;
    }
    //cerr << j1 << " " << j2 << " Xd " << ans << "\n";
    if(j1 > j2) return ans;
    //cerr << "??? " << i2 << "\n";
    if(i1 == 2)
    {
        ans += S(n - 1 + j1 - 2, n - 1 + j2 - 2, 2);
        i1 = 3;
    }
    //cerr << sum[n - 1 + j1 - 2][2] << " " << sum[n - 1 + j2 - 2][2] << "\n";
    //cerr << n - 1 + j1 - 2 << " " << n - 1 + j2 - 2 << " Xd " << ans << "\n";
    if(i1 > i2) return ans;
    
    if(j1 == 2)
    {
        ans += S(n - 1 - i2 + 2, n - 1 - i1 + 2, 2);
        j1 = 3;
    }
    if(j1 > j2) return ans;
    //cerr << "First " << ans << " " << i1 << " " << i2 << " " << j1 << " " << j2 << "\n";
    int d = i1 - 3, r = (i2 - i1);
    j1 -= d; j2 -= d;
    ans += WS(n - 2 + j1 - 3 - r, n - 2 + j2 - 3, min(j2 - j1 + 1, i2 - i1 + 1));
    return ans;
}

vector<long long> mosaic(vector<int> X, vector<int> Y, vector<int> T, vector<int> B, vector<int> L, vector<int> R)
{
    vector<ll> ans;
    int n = X.size(), q = T.size();
    for(int i = 1; i <= n; ++i)
        tab[i][1] = Y[n - i];
    for(int i = n + 1; i <= 2 * n - 1; ++i)
        tab[i][1] = X[i - n];
    DoBas(n);
    for(int i = 0; i < q; ++i)
        ans.pb(Query(n, T[i] + 1, B[i] + 1, L[i] + 1, R[i] + 1));
    return ans;
}

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