oj.uz

Submission #1097177

# Submission time Handle Problem Language Result Execution time Memory
1097177 2024-10-06T11:35:28 Z gyg Hexagonal Territory (APIO21_hexagon) C++17
0 / 100
 893 ms 1048576 KB 
#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 + 1 < 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);
                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.0

# Verdict Execution time Memory Grader output
1 Runtime error 862 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 883 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23896 KB Output is correct
2 Correct 12 ms 24668 KB Output is correct
3 Correct 14 ms 24892 KB Output is correct
4 Correct 12 ms 24668 KB Output is correct
5 Correct 14 ms 24760 KB Output is correct
6 Correct 14 ms 24668 KB Output is correct
7 Correct 13 ms 24668 KB Output is correct
8 Correct 13 ms 24412 KB Output is correct
9 Correct 19 ms 24668 KB Output is correct
10 Correct 15 ms 24668 KB Output is correct
11 Correct 15 ms 24708 KB Output is correct
12 Correct 13 ms 24924 KB Output is correct
13 Correct 15 ms 24920 KB Output is correct
14 Correct 14 ms 24924 KB Output is correct
15 Runtime error 36 ms 49728 KB Execution killed with signal 6
16 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 747 ms 143276 KB Output is correct
2 Correct 360 ms 96968 KB Output is correct
3 Correct 421 ms 119480 KB Output is correct
4 Correct 322 ms 98244 KB Output is correct
5 Correct 486 ms 127376 KB Output is correct
6 Correct 575 ms 145496 KB Output is correct
7 Runtime error 251 ms 137868 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 824 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23896 KB Output is correct
2 Correct 13 ms 24668 KB Output is correct
3 Correct 16 ms 25056 KB Output is correct
4 Correct 13 ms 24712 KB Output is correct
5 Correct 14 ms 24924 KB Output is correct
6 Correct 13 ms 24784 KB Output is correct
7 Correct 14 ms 24668 KB Output is correct
8 Correct 11 ms 24348 KB Output is correct
9 Correct 14 ms 24720 KB Output is correct
10 Correct 16 ms 24668 KB Output is correct
11 Correct 14 ms 24668 KB Output is correct
12 Correct 13 ms 24924 KB Output is correct
13 Correct 14 ms 24924 KB Output is correct
14 Correct 13 ms 24920 KB Output is correct
15 Runtime error 36 ms 49664 KB Execution killed with signal 6
16 Halted 0 ms 0 KB -

Subtask #7
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 893 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23900 KB Output is correct
2 Runtime error 867 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -