Submission #1262727

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262727		nerrrmin	Mosaic (IOI24_mosaic)	C++20	53 / 100	354 ms	93344 KiB

mosaic

#include "mosaic.h"
#define pb push_back
#include <vector>
#include<bits/stdc++.h>
using namespace std;
const long long maxn = 400005;
//pref[maxn][maxn];
long long n;
vector < long long > a[maxn];

vector < long long > arr, state;
map < long long, long long > pos;

vector < long long > pref, suff;
vector < long long > pp, ss;


int colpref[maxn][3], rowpref[maxn][3];
long long getprefsum(long long l, long long r) /// 1 2 3 4 5
{
    if(r < l)return 0;
    long long sz = r - l + 1;
    long long sum = pp[r] - pp[l-1] - pref[l-1] * sz;
    return sum;
}

long long getsuffsum(long long l, long long r)
{
    if(r < l)return 0;
    long long sz = r - l + 1;

    long long sum = ss[l] - ss[r+1] - suff[r+1] * sz;
    return sum;
}
long long getsum(long long l, long long r)
{
    if(r < l)return 0;
    return pref[r] - pref[l-1];
}
std::vector<long long> mosaic(std::vector<int> X, std::vector<int> Y,
                              std::vector<int> T, std::vector<int> B,
                              std::vector<int> L, std::vector<int> R)
{
    long long q = (long long)T.size();
    std::vector<long long> C(q, 0);


    n = X.size();

    a[0].resize(n+1, 0);
    a[1].resize(n+1, 0);
    a[2].resize(n+1, 0);
    a[3].resize(n+1, 0);
    a[4].resize(n+1, 0);
    for (long long j = 5; j <= n; ++ j)
        a[j].resize(6, 0);
    for (long long i = 1; i <= n; ++ i)
        a[1][i] = X[i-1];

    for (long long i = 1; i <= n; ++ i)
        a[i][1] = Y[i-1];

    for (long long i = 2; i <= 3; ++ i)
    {
        for (long long j = i; j <= n; ++ j)
        {
            if(!a[i-1][j] && !a[i][j-1])a[i][j] = 1;
            else a[i][j] = 0;
        }
        for (long long j = i; j <= n; ++ j)
        {
            if(!a[j-1][i] && !a[j][i-1])a[j][i] = 1;
            else a[j][i] = 0;
        }
    }

    for (int col = 1; col <= 2; ++ col)
    {
        for (int i = 1 ; i <= n; ++ i)
            colpref[i][col] = colpref[i-1][col] + a[i][col];
    }
    for (int row = 1; row <= 2; ++ row)
    {
        for (int i = 1; i <= n; ++ i)
            rowpref[i][row] = rowpref[i-1][row] + a[row][i];
    }
    vector < long long > hor, ver;


    arr.pb(0);
    state.pb(0);
    for (long long i = n; i >= 3; -- i)
    {
        arr.pb(a[i][3]);
        state.pb(i - 3);
    }

    for (long long j = 4; j <= n; ++ j)
    {
        arr.pb(a[3][j]);
        state.pb(3 - j);
    }
    arr.pb(0);
    state.pb(0);
    pref.resize(2*n+2, 0);
    suff.resize(2*n+2, 0);
    long long sz = arr.size()-1;
    for (long long i = 1; i < arr.size()-1; ++ i)
        pref[i] = pref[i-1] + arr[i];
    for (long long i = arr.size()-2; i >= 1; -- i)
        suff[i] = suff[i+1] + arr[i];
    pp.resize(2*n+2, 0);
    ss.resize(2*n+2, 0);
    for (long long i = 1; i < sz; ++ i)
        pp[i] = pp[i-1] + pref[i];
    for (long long i = sz-1; i >= 1; -- i)
        ss[i] = ss[i+1] + suff[i];

    for (long long i = 1; i < arr.size()-1; ++ i)
    {
        //cout << arr[i] << " ";
        pos[state[i]] = i;

       // cout << state[i] << " " << i << endl;
    }
    /* cout << endl;
     cout << "state " << endl;
     for (long long i = 0; i < state.size(); ++ i)
         cout << state[i] << " ";
     cout << endl;
     cout << "hsdiehduie " << endl;
     cout << "pos " << endl;
     for (long long i = 1; i < arr.size()-1; ++ i)
     {

         cout << state[i] << "is " << i << endl;
     }*/
    /* cout << endl;
     cout << "****" << endl;
     cout << "pref " << endl;
     for (auto x: pref)
         cout << x << " ";
     cout << endl;
     for (auto x: pp)
         cout << x << " ";
     cout << endl;

     cout << "****" << endl;
     cout << "suff" << endl;
     for (auto x: suff)
         cout << x << " ";
     cout << endl;
     for (auto x: ss)
         cout << x << " ";
     cout << endl;
     cout << endl;*/
    q = (long long)T.size();
    vector < long long > res;
    for (long long i = 0; i < q; ++ i)
    {
        long long t = T[i] + 1;
        long long b = B[i] + 1;
        long long l = L[i] + 1;
        long long r = R[i] + 1;
        long long ans = 0;
        for (int j = t; j <= min(1LL * 2, b); ++ j)
        {
            ans += rowpref[r][j] - rowpref[l-1][j];
        }
        if(t < 3)t = min(1LL * 2, b) + 1;
        if(b < t)
        {
            res.pb(ans);
            continue;
        }
        for (int j = l; j <= min(1LL * 2, r); ++ j)
        {
            ans += colpref[b][j] - colpref[t-1][j];
        }
        if(l < 3)l = min(1LL * 2, r) + 1;
        if(l > r)
        {
            res.pb(ans);
            continue;
        }

        long long szh = r - l + 1;
        long long szv = b - t + 1;
        if(szh > szv)
        {

            if(szv > 1)
            {
                long long stateh0 = pos[b - l];
                long long stateh1 = pos[b - (l + szv - 2)]; /// rastat
                ans += getsuffsum(stateh0, stateh1);
            }
            long long const0 = pos[b - (l + szv - 1)];
            long long const1 = pos[b - r]; /// shte e konst
            long long mult = szv;
            if(szv > 1)
            {
                long long up0 =  pos[(b-1) - r];
                long long up1 = pos[t - r];
                ans += getprefsum(up0, up1);
            }

            ans += getsum(const0, const1) * mult;

            res.pb(ans);
        }
        else
        {

            if(szh > 1)
            {
                long long stateh0 = pos[b - l];
                long long stateh1 = pos[b - (r-1)]; /// rastat
                ans += getsuffsum(stateh0, stateh1);
            }
            long long const0 = pos[b - r];
            long long const1 = pos[(t + szh - 1) - r]; /// shte e konst
            long long mult = szh;
            if(szh > 1)
            {
                long long up0 =  pos[(t + szh) - r];
                long long up1 = pos[t - r];
                ans += getprefsum(up0, up1);
            }

            ans += getsum(const0, const1) * mult;

            res.pb(ans);
        }

    }
    //  cout << res.size() << endl;
    return res;
}
/**
4
1 0 1 0
1 1 0 1
2
0 0 3 3
2 2 3 3


8
0 1 0 1 0 0 1 0
0 1 0 0 1 0 1 0
3
4 4 4 4
2 2 5 5
0 0 1 1
*/

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