Submission #1209790

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209790		andrej246	Mosaic (IOI24_mosaic)	C++20	5 / 100	1101 ms	163180 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;

void propagate(ll x, ll y, map<pl,ll>& table) {
    if(table.count({x,y}) > 0) return;
    table[{x,y}] = !(table[{x-1,y}] || 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 <= 2) {
        vvl table(n,vl(n));
        FOR(i,n) table[i][0] = x[i];
        FOR(i,n) table[0][i] = y[i];
        if (n >= 2) table[1][1] = !(table[1][0] || table[0][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;
    }

    map<pl,ll> table;
    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;
    }

    priority_queue<pl> todo;
    FOR(x,n) {
        FOR(y,2) {
            todo.push({x,y});
            todo.push({y,x});
        }
    }

    map<pl,ll> rectsum;
    while (!todo.empty()) {
        auto [x,y] = todo.top();
        todo.pop();
        rectsum[{x,y}] = rectsum[{x+1,y}]+rectsum[{x,y+1}]-rectsum[{x+1,y+1}]+table[{x,y}];
    }

    vl res(q);
    FOR(i,q) {
        ll ans = 0;
        if (t[i] <= 1 || l[i] <= 1) {
            ans += rectsum[{l[i],t[i]}];
        }
        if (t[i] <= 1) {
            ans -= rectsum[{r[i]+1,t[i]}];
        }
        if (l[i] <= 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 || x2 > y2) {
            res[i] = ans;
            continue;
        }

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

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

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

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

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

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