Submission #1209847

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209847		andrej246	Mosaic (IOI24_mosaic)	C++20	27 / 100	126 ms	54596 KiB

mosaic

#include "mosaic.h"

#include <bits/stdc++.h>
using namespace std;

#define NL "\n"
#define EL cout << NL
#define FOR(i,n) for (long long i = 0; i < (n); i++)
#define FORS(i,s,n) for (long long i = (s); i < (n); i++)
#define FORR(i,n) for (long long i = (n)-1; i >= 0; i--)
#define PRINTV(v) for (auto a: v) {cout << a << " ";} EL;
#define PRINTVV(v) for (auto a: v) {PRINTV(a);}
#define f first
#define s second
#define all(v) (v).begin(),(v).end()

typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> pl;
typedef vector<pl> vpl;
typedef vector<vpl> vvpl;

ll get(vvl& table, ll x, ll y) {
    if (x >= 2 && y >= 2) return 0;
    if (x < 0 || y < 0) return 0;
    if (x >= (ll)table.size() || y >= (ll)table.size()) return 0;
    return table[x][y];
}

void propagate(ll x, ll y, vvl& table) {
    if (x == 0 || y == 0) return;
    table[x][y] = !(get(table,x-1,y) || get(table,x,y-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) {
    ll q = (int)t.size();
    ll n = x.size();

    if (n <= 200) {
        vvl table(n,vl(n));
        FOR(i,n) table[i][0] = x[i];
        FOR(i,n) table[0][i] = y[i];
        FORS(x,1,n) {
            FORS(y,1,n) {
                table[x][y] = !(table[x-1][y] || table[x][y-1]);
            }
        }
        vl ans(q);
        FOR(i,q) {
            FORS(x,l[i],r[i]+1) {
                FORS(y,t[i],b[i]+1) {
                    ans[i] += table[x][y];
                }
            }
        }
        return ans;
    }

    vvl table;
    FOR(i,n) {
        if (i <= 2) table.push_back(vl(n));
        else table.push_back(vl(3));
    }
    FOR(i,n) table[i][0] = x[i];
    FOR(i,n) table[0][i] = y[i];

    FOR(i,n) propagate(1,i,table);
    FOR(i,n) propagate(i,1,table);
    FOR(i,n) propagate(i,2,table);
    FOR(i,n) propagate(2,i,table);
    
    vl diags(2*n-5);
    FORS(i,2,n) {
        diags[i-2+n-3] = table[i][2];
    }
    FORS(i,2,n) {
        diags[2-i+n-3] = table[2][i];
    }

    vl dpsum(2*n-5);
    ll sum = 0;
    FOR(i,2*n-5) {
        sum += diags[i];
        dpsum[i] = sum;
    }

    vl dtsum(2*n-5);
    vl drsum(2*n-5);
    ll tsum = 0;
    ll rsum = 0;
    FOR(i,2*n-5) {
        tsum += diags[i]*(i+1);
        dtsum[i] = tsum;
    }

    FORR(i,2*n-5) {
        rsum += diags[i]*(2*n-5-i);
        drsum[i] = rsum;
    }

    vvl rectsum;
    FOR(i,n) {
        if (i <= 1) rectsum.push_back(vl(n));
        else rectsum.push_back(vl(2));
    }
    FORR(y,n) {
        ll maxx = 2;
        if (y <= 1) maxx = n;
        FORR(x,maxx) {
            rectsum[x][y] = get(rectsum,x+1,y)+get(rectsum,x,y+1)-get(rectsum,x+1,y+1)+table[x][y];
        }
    }

    vl res(q);
    FOR(i,q) {
        ll ans = 0;
        if (!(b[i] >= 2 && r[i] >= 2)) {
            ans = rectsum[l[i]][t[i]]-get(rectsum,r[i]+1,t[i])-get(rectsum,l[i],b[i]+1)+get(rectsum,r[i]+1,b[i]+1);
            res[i] = ans;
            continue;
        }
        if (t[i] <= 1 || l[i] <= 1) {
            ans += rectsum[l[i]][t[i]];
        }
        if (t[i] <= 1 && r[i] < n-1) {
            ans -= rectsum[r[i]+1][t[i]];
        }
        if (l[i] <= 1 && b[i] < n-1) {
            ans -= rectsum[l[i]][b[i]+1];
        }

        ll x1 = max(2,l[i]);
        ll y1 = max(2,t[i]);
        ll x2 = r[i];
        ll y2 = b[i];
        if (x1 > x2 || y1 > y2) {
            res[i] = ans;
            continue;
        }

        ll left = x1-y2 +n-3;
        ll right = x2-y1 +n-3;
        ll w = min(abs(x2-x1),abs(y2-y1))+1;

        if (w > 1) {
            ans += dtsum[left+w-2]-left*dpsum[left+w-2];
            if (left >= 1) {
                ans -= dtsum[left-1]-left*dpsum[left-1];
            }

            ans += drsum[right-(w-2)]-(2*n-5-1-right)*dpsum[right];
            if (right < 2*n-5-1) ans -= drsum[right+1];
            if (right-(w-1) >= 0) ans += (2*n-5-1-right)*dpsum[right-(w-1)];
        }

        ans += w*dpsum[right-w+1];
        if (left+w-1 > 0) ans -= w*dpsum[left+w-2];

        res[i] = ans;
    }
 
    return res;
}

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 7 / 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