Submission #1097179

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097179		gyg	Hexagonal Territory (APIO21_hexagon)	C++17	42 / 100	924 ms	1048576 KiB

hexagon

#include "hexagon.h"
#include <bits/stdc++.h>
using namespace std;
#define lint long long
#define arr array 
#define vct vector
#define hmap unordered_map 
#define hset unordered_set
#define pll pair<lint, lint>
#define fir first 
#define sec second
#define lb lower_bound
const lint MD = 1e9 + 7, N_NDS = 1e6 + 5, INF = 1e18, INV = 5e8 + 4;

lint n, a, b;
vct<lint> drc, lng;

lint md(lint x) { return (x + MD) % MD; }

pll mv(pll pt, lint drc, lint lng) {
    pll dlt;
    if (drc == 1) dlt = {0, 1};
    if (drc == 2) dlt = {1, 1};
    if (drc == 3) dlt = {1, 0};
    if (drc == 4) dlt = {0, -1};
    if (drc == 5) dlt = {-1, -1};
    if (drc == 6) dlt = {-1, 0};
    return {pt.fir + dlt.fir * lng, pt.sec + dlt.sec * lng};
}
vct<pll> gt_pts() {
    pll pt = {0, 0};
    vct<pll> ans;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < lng[i]; j++) {
            pt = mv(pt, drc[i], 1);
            ans.push_back(pt);
        }
    }
    return ans;
}
vct<pll> nghbrs(pll pt) {
    vct<pll> ans;
    for (int i = 1; i <= 6; i++) ans.push_back(mv(pt, i, 1));
    return ans;
}
set<pll> pt_nds, pth_nds, vs;
void dfs(pll pt) {
    vs.insert(pt);
    for (pll nw_pt : nghbrs(pt))
        if (pt_nds.count(nw_pt) && !vs.count(nw_pt) && !pth_nds.count(nw_pt)) dfs(nw_pt);
}
hmap<lint, vct<pll>> clmns;
int n_nds;
arr<lint, N_NDS> x;
arr<pll, N_NDS> y;
lint prcmp1() {
    vct<pll> pts = gt_pts();
    for (pll pt : pts) {
        pt_nds.insert(pt), pth_nds.insert(pt);
        for (pll nw_pt : nghbrs(pt)) pt_nds.insert(nw_pt);
    }
    
    pll mn_x;
    for (pll pt : pt_nds) mn_x = min(mn_x, pt);
    dfs(mn_x);

    for (pll pt : pts) clmns[pt.fir].push_back(pt);
    for (pair<lint, vct<pll>> clmn : clmns) {
        sort(clmn.sec.begin(), clmn.sec.end());
        for (pll pt : clmn.sec) {
            if (vs.count({pt.fir, pt.sec - 1})) n_nds++, x[n_nds] = clmn.fir, y[n_nds] = {pt.sec, 0};
            if (vs.count({pt.fir, pt.sec + 1})) y[n_nds].sec = pt.sec;
        }
    }

    // for (int u = 1; u <= n_nds; u++) {
    //     cout << u << ": " << x[u] << " " << y[u].fir << " " << y[u].sec << endl;
    // }

    lint ans = 0;
    for (int u = 1; u <= n_nds; u++) ans += y[u].sec - y[u].fir + 1;
    return ans;
}

hmap<lint, map<pll, int>> nd;
hmap<lint, set<pll>> ys;
arr<vct<int>, N_NDS> adj;
int rt;
arr<lint, N_NDS> lw;
arr<pll, N_NDS> rng;
arr<bool, N_NDS> sn;
void dfs2(int u) {
    sn[u] = true;
    for (int v : adj[u]) {
        if (sn[v]) continue;
        if (x[v] > x[u]) {
            pll intr = {max(rng[u].fir, y[v].fir), min(rng[u].sec + 1, y[v].sec)};
            if (intr.fir <= intr.sec) rng[v] = intr, lw[v] = lw[u] + 1;
            else if (rng[u].sec + 1 < y[v].fir) rng[v] = {y[v].fir, y[v].fir}, lw[v] = lw[u] + y[v].fir - rng[u].sec;
            else {
                assert(y[v].sec < rng[u].fir);
                rng[v] = {y[v].sec, y[v].sec}, lw[v] = lw[u] + rng[u].fir - y[v].sec + 1;
            }
        } else {
            pll intr = {max(rng[u].fir - 1, y[v].fir), min(rng[u].sec, y[v].sec)};
            if (intr.fir <= intr.sec) rng[v] = intr, lw[v] = lw[u] + 1;
            else if (rng[u].sec < y[v].fir) rng[v] = {y[v].fir, y[v].fir}, lw[v] = lw[u] + y[v].fir - rng[u].sec + 1;
            else {
                assert(y[v].sec < rng[u].fir - 1);
                rng[v] = {y[v].sec, y[v].sec}, lw[v] = lw[u] + rng[u].fir - y[v].sec;
            }
        }
        dfs2(v);
    }
}
 
void prcmp2() {
    for (int u = 1; u <= n_nds; u++)
        nd[x[u]][y[u]] = u, ys[x[u]].insert(y[u]);
    
    for (int u = 1; u <= n_nds; u++) {
        for (lint nw_x : {x[u] - 1, x[u] + 1}) {
            auto it1 = ys[nw_x].lb({y[u].fir, -INF}); 
            if (it1 != ys[nw_x].begin())
                if (next(it1, -1)->sec >= y[u].fir)
                    adj[u].push_back(nd[nw_x][*next(it1, -1)]);

            for (auto it2 = it1; it2 != ys[nw_x].end() && it2->fir <= y[u].sec; it2++)
                adj[u].push_back(nd[nw_x][*it2]);
        }
    }

    rt = nd[0][*next(ys[0].lb({1, -1}), -1)];
    lw[rt] = 0, rng[rt] = {0, 0};
    dfs2(rt);

    // cout << y[rt].fir << " " << y[rt].sec << endl;

    // for (int u = 1; u <= n_nds; u++) {
    //     cout << x[u] << "," << y[u].fir << "," << y[u].sec << ": ";
    //     for (int v : adj[u]) cout << x[v] << "," << y[v].fir << "," << y[v].sec << " ";
    //     // for (int v : adj[u]) cout << v << " ";
    //     cout << endl; 
    // }
}

lint sm(lint x, lint y) {
    if (x > y) return 0;
    return md(md(md(x + y) * md(y - x + 1)) * INV);
}

int draw_territory(int _n, int _a, int _b, vct<int> _drc, vct<int> _lng) {
    n = _n, a = _a, b = _b;
    for (int i = 0; i < n; i++) drc.push_back(_drc[i]), lng.push_back(_lng[i]);

    lint ar = prcmp1();
    lint ans = md(ar * a);
    prcmp2();

    // for (int u = 1; u <= n_nds; u++) {
    //     cout << x[u] << "," << y[u].fir << "," << y[u].sec << ": " << lw[u] << "," << rng[u].fir << "," << rng[u].sec << endl;
    // }

    for (int u = 1; u <= n_nds; u++) {
        lint inc_ans = md(b * md(lw[u] * (rng[u].sec - rng[u].fir + 1) + 
                          sm(lw[u] + 1, lw[u] + rng[u].fir - y[u].fir) +
                          sm(lw[u] + 1, lw[u] + y[u].sec - rng[u].sec)));
        ans = md(ans + inc_ans);
    }
    return ans;
}

• Subtask 1: 0 / 3
• Subtask 2: 0 / 6
• Subtask 3: 11 / 11
• Subtask 4: 12 / 12
• Subtask 5: 0 / 15
• Subtask 6: 19 / 19
• Subtask 7: 0 / 18
• Subtask 8: 0 / 16