oj.uz

Submission #1097179

# Submission time Handle Problem Language Result Execution time Memory
1097179 2024-10-06T11:38:11 Z gyg Hexagonal Territory (APIO21_hexagon) C++17
42 / 100
 924 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 < 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.0

# Verdict Execution time Memory Grader output
1 Runtime error 845 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 832 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23896 KB Output is correct
2 Correct 12 ms 24668 KB Output is correct
3 Correct 14 ms 24920 KB Output is correct
4 Correct 12 ms 24664 KB Output is correct
5 Correct 13 ms 24876 KB Output is correct
6 Correct 14 ms 24668 KB Output is correct
7 Correct 13 ms 24668 KB Output is correct
8 Correct 15 ms 24452 KB Output is correct
9 Correct 14 ms 24664 KB Output is correct
10 Correct 15 ms 24820 KB Output is correct
11 Correct 14 ms 24892 KB Output is correct
12 Correct 16 ms 25084 KB Output is correct
13 Correct 13 ms 24668 KB Output is correct
14 Correct 15 ms 24924 KB Output is correct
15 Correct 14 ms 24640 KB Output is correct
16 Correct 14 ms 24668 KB Output is correct
17 Correct 12 ms 24400 KB Output is correct
18 Correct 14 ms 25180 KB Output is correct
19 Correct 14 ms 25180 KB Output is correct
20 Correct 11 ms 23944 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 770 ms 143284 KB Output is correct
2 Correct 350 ms 96972 KB Output is correct
3 Correct 402 ms 119476 KB Output is correct
4 Correct 324 ms 98240 KB Output is correct
5 Correct 496 ms 127412 KB Output is correct
6 Correct 562 ms 145452 KB Output is correct
7 Correct 223 ms 69056 KB Output is correct
8 Correct 541 ms 97716 KB Output is correct
9 Correct 677 ms 116404 KB Output is correct
10 Correct 639 ms 117940 KB Output is correct
11 Correct 492 ms 119476 KB Output is correct
12 Correct 509 ms 118316 KB Output is correct
13 Correct 460 ms 120640 KB Output is correct
14 Correct 593 ms 99948 KB Output is correct
15 Correct 319 ms 69048 KB Output is correct
16 Correct 478 ms 90812 KB Output is correct
17 Correct 768 ms 148560 KB Output is correct
18 Correct 709 ms 148020 KB Output is correct
19 Correct 10 ms 23900 KB Output is correct

Subtask #5
0 / 15.0

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

Subtask #6
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23896 KB Output is correct
2 Correct 12 ms 24668 KB Output is correct
3 Correct 13 ms 24924 KB Output is correct
4 Correct 12 ms 24668 KB Output is correct
5 Correct 13 ms 24868 KB Output is correct
6 Correct 13 ms 24668 KB Output is correct
7 Correct 16 ms 24744 KB Output is correct
8 Correct 11 ms 24412 KB Output is correct
9 Correct 13 ms 24668 KB Output is correct
10 Correct 14 ms 24804 KB Output is correct
11 Correct 14 ms 24864 KB Output is correct
12 Correct 14 ms 24924 KB Output is correct
13 Correct 12 ms 24908 KB Output is correct
14 Correct 13 ms 24924 KB Output is correct
15 Correct 13 ms 24668 KB Output is correct
16 Correct 15 ms 24408 KB Output is correct
17 Correct 12 ms 24408 KB Output is correct
18 Correct 701 ms 143328 KB Output is correct
19 Correct 366 ms 96792 KB Output is correct
20 Correct 472 ms 119408 KB Output is correct
21 Correct 365 ms 98240 KB Output is correct
22 Correct 545 ms 127428 KB Output is correct
23 Correct 591 ms 145600 KB Output is correct
24 Correct 268 ms 69104 KB Output is correct
25 Correct 481 ms 97820 KB Output is correct
26 Correct 635 ms 116408 KB Output is correct
27 Correct 612 ms 117944 KB Output is correct
28 Correct 487 ms 119540 KB Output is correct
29 Correct 527 ms 118488 KB Output is correct
30 Correct 489 ms 120784 KB Output is correct
31 Correct 565 ms 99848 KB Output is correct
32 Correct 301 ms 69056 KB Output is correct
33 Correct 449 ms 90676 KB Output is correct
34 Correct 309 ms 85652 KB Output is correct
35 Correct 304 ms 90968 KB Output is correct
36 Correct 266 ms 86972 KB Output is correct
37 Correct 414 ms 123060 KB Output is correct
38 Correct 501 ms 124520 KB Output is correct
39 Correct 509 ms 131396 KB Output is correct
40 Correct 528 ms 122300 KB Output is correct
41 Correct 525 ms 97716 KB Output is correct
42 Correct 618 ms 115380 KB Output is correct
43 Correct 607 ms 117940 KB Output is correct
44 Correct 447 ms 117144 KB Output is correct
45 Correct 472 ms 110392 KB Output is correct
46 Correct 400 ms 109116 KB Output is correct
47 Correct 434 ms 93976 KB Output is correct
48 Correct 529 ms 91988 KB Output is correct
49 Correct 512 ms 92028 KB Output is correct
50 Correct 727 ms 148428 KB Output is correct
51 Correct 686 ms 148088 KB Output is correct
52 Correct 10 ms 23900 KB Output is correct
53 Correct 727 ms 148336 KB Output is correct
54 Correct 692 ms 147892 KB Output is correct
55 Correct 14 ms 25180 KB Output is correct
56 Correct 17 ms 25180 KB Output is correct
57 Correct 10 ms 23900 KB Output is correct

Subtask #7
0 / 18.0

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