oj.uz

Submission #1097162

# Submission time Handle Problem Language Result Execution time Memory
1097162 2024-10-06T10:50:33 Z gyg Hexagonal Territory (APIO21_hexagon) C++17
12 / 100
 921 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;
        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 < 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 + 1;
        }
        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 809 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 921 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 11 ms 23944 KB Output is correct
2 Incorrect 14 ms 24668 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 798 ms 143472 KB Output is correct
2 Correct 392 ms 96892 KB Output is correct
3 Correct 456 ms 119476 KB Output is correct
4 Correct 372 ms 98240 KB Output is correct
5 Correct 547 ms 127348 KB Output is correct
6 Correct 645 ms 145596 KB Output is correct
7 Correct 245 ms 69052 KB Output is correct
8 Correct 538 ms 97608 KB Output is correct
9 Correct 697 ms 116460 KB Output is correct
10 Correct 617 ms 117984 KB Output is correct
11 Correct 466 ms 119536 KB Output is correct
12 Correct 525 ms 118388 KB Output is correct
13 Correct 457 ms 120788 KB Output is correct
14 Correct 595 ms 99836 KB Output is correct
15 Correct 350 ms 69044 KB Output is correct
16 Correct 488 ms 90744 KB Output is correct
17 Correct 786 ms 148604 KB Output is correct
18 Correct 746 ms 148128 KB Output is correct
19 Correct 12 ms 23900 KB Output is correct

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 905 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 Incorrect 13 ms 24664 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 909 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 13 ms 23800 KB Output is correct
2 Runtime error 909 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -