Submission #1262717

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262717		nerrrmin	Mosaic (IOI24_mosaic)	C++20	0 / 100	410 ms	83792 KiB

mosaic

#include "mosaic.h"
#define pb push_back
#include <vector>
#include<bits/stdc++.h>
using namespace std;
const long long maxn = 200005;
//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;

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;
        }
    }
    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 << 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;
        if(t < 3 || l < 3)
        {
            res.pb(a[t][b]);
            continue;
        }
        long long szh = r - l + 1;
        long long szv = b - t + 1;
        if(szh >= szv)
        {
            long long stateh0 = pos[b - l];
            long long stateh1 = pos[b - (l + szv - 2)]; /// rastat
            long long const0 = pos[b - (l + szv - 1)];
            long long const1 = pos[b - r]; /// shte e konst
            long long mult = szv;
            long long up0 =  pos[(b-1) - r];
            long long up1 = pos[t - r];
            long long ans = 0;
            ans += getsuffsum(stateh0, stateh1);
            ans += getsum(const0, const1) * mult;
            ans += getprefsum(up0, up1);
            res.pb(ans);
        }
        else
        {
            long long stateh0 = pos[b - l];
            long long stateh1 = pos[b - (r-1)]; /// rastat
            long long const0 = pos[b - r];
            long long const1 = pos[(t + szh) - r]; /// shte e konst
            long long mult = szh;
            long long up0 =  pos[(t + szh - 1) - r];
            long long up1 = pos[t - r];
            long long ans = 0;
            ans += getsuffsum(stateh0, stateh1);
            ans += getsum(const0, const1) * mult;
            ans += getprefsum(up0, up1);
            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 1 0 0 1 0
1
3 7 3 5
*/

• 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