Submission #1199804

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199804		Nelt	Mosaic (IOI24_mosaic)	C++20	100 / 100	950 ms	182304 KiB

mosaic

#include "mosaic.h"
#include <bits/stdc++.h>
#define ll long long
// #define endl "\n"
using namespace std;
const ll N = 2e5 + 5;
ll t[N];
void upd(ll i, ll d)
{
    for (; i < N; i |= (i + 1)) t[i] += d;
}
ll sum(ll i)
{
    ll ans = 0;
    for (; i >= 0; i = (i & (i + 1)) - 1) ans += t[i];
    return ans;
}
vector<ll> neg, pos, pneg, ppos;
map<ll, ll> mp[N];
map<ll, vector<pair<ll, ll>>> diag;
vector<array<ll, 3>> inc;
ll n, q;
void precomp()
{
    for (ll i = 1; i < n; i++)
    for (ll j = 1; j < n; j++)
    {
        if (i > 2 and j > 2) break;
        mp[i][j] = !mp[i - 1][j] and !mp[i][j - 1];
        diag[j - i].push_back(make_pair(i, j));
    }
    pos.push_back(0);
    for (auto [x, v] : diag)
        if (v.size() == 1)
        {
            if (mp[v[0].first][v[0].second]) 
                inc.push_back({v[0].first, v[0].second, 1});
        }
        else
        {
            assert(v[0].first < v[1].first);
            if (mp[v[0].first][v[0].second]) 
            {
                if (x < 0) neg.push_back(-x);
                else pos.push_back(x);
            }
            else if (mp[v[1].first][v[1].second])
            {
                inc.push_back({v[0].first, v[0].second, -1});
                if (x < 0) neg.push_back(-x);
                else pos.push_back(x);
            }
        }
    neg.push_back(0);
    reverse(neg.begin(), neg.end());
    // for (auto [a, b, c] : inc) cout << a << " " << b << " " << c << endl;
    pneg.push_back(0);
    ppos.push_back(0);
    // cout << pos.size() << " " << neg.size() << endl;
    // for (ll i : pos) cout << i << " ";
    // cout << endl;
    // for (ll i : neg) cout << i << " ";
    // cout << endl;
    for (ll i = 1; i < neg.size(); i++) pneg.push_back(pneg.back() + neg[i]);
    for (ll i = 1; i < pos.size(); i++) ppos.push_back(ppos.back() + pos[i]);
    sort(inc.begin(), inc.end());
}
ll sum(ll l, ll r, vector<ll> &pref)
{
    r = min(r, (ll)pref.size() - 1);
    l = max(0ll, l - 1);
    return l >= r ? 0 : pref[r] - pref[l];
}
ll calc(ll i, ll j, vector<ll> &v, vector<ll> &pref)
{
    if (j < 0 or i < 0) return 0;
    ll l = upper_bound(v.begin() + 1, v.end(), j - i) - v.begin(), r = upper_bound(v.begin() + 1, v.end(), j) - v.begin();
    return (l - 1) * i + j * (r - l) - sum(l, r - 1, pref);
    // ll ans = (l - 1) * i + (r - l) * j;
    // ans -= sum(l, r - 1, pref);
    // return ans;
}
ll f(ll i, ll j)
{
    return calc(i, j, pos, ppos) + calc(j, i, neg, pneg);
}
// i <= j - x -> x <= j - i
// i <= j - x -> i + x <= j -> x <= j - i
// i > j - x, +j * sz pref[]
// i <= j - x, then i > j - x (j - x might become less than 0, so need to keep track)
// max(i, j - x) -> x > 0
// max(i + x, j) -> x <= 0 (max(i, j - x), ij swapped, negative turned to positive)
vector<long long> mosaic(vector<int> X, vector<int> Y,
                         vector<int> T, vector<int> B,
                         vector<int> L, vector<int> R)
{
    n = X.size(), q = T.size();
    for (ll i = 0; i < n; i++) mp[0][i] = X[i], mp[i][0] = Y[i];
    for (ll i = 0; i < n; i++)
    {
        if (X[i])
            inc.push_back({0, i, 1});
        if (Y[i] and i) inc.push_back({i, 0, 1});
    }
    precomp();
    array<ll, 3> qs[q << 2];
    vector<ll> ans(q, 0);
    // cout << "all good\n";
    for (ll i = 0; i < q; i++)
    {
        qs[i * 4] = {T[i] - 1, L[i] - 1, i * 4};
        qs[i * 4 + 1] = {B[i], R[i], i * 4 + 1};
        qs[i * 4 + 2] = {T[i] - 1, R[i], i * 4 + 2};
        qs[i * 4 + 3] = {B[i], L[i] - 1, i * 4 + 3};
    }
    sort(qs, qs + q * 4);
    ll ptr = 0;
    for (auto [x, y, ind] : qs)
    {
        ll id = (ind >> 2), tp = (ind & 3) < 2 ? 1 : -1;
        while (ptr < inc.size() and inc[ptr][0] <= x) upd(inc[ptr][1], inc[ptr][2]), ptr++;
        ans[id] += tp * (sum(y) + f(x, y));
    }
    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