oj.uz

Submission #1088053

# Submission time Handle Problem Language Result Execution time Memory
1088053 2024-09-13T19:06:09 Z nguyen31hoang08minh2003 Drzava (COCI15_drzava) C++17
160 / 160
 764 ms 16080 KB 
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <math.h>
#include <bitset>
#include <vector>
#include <string>
#include <cstdio>
#include <cctype>
#include <numeric>
#include <fstream>
#include <sstream>
#include <cstdlib>
#include <iomanip>
#include <cassert>
#include <cstring>
#include <stdio.h>
#include <string.h>
#include <iterator>
#include <iostream>
#include <algorithm>
#include <strings.h>
#include <functional>
#include <unordered_set>
#include <unordered_map>
#define fore(i, a, b) for (int i = (a), i##_last = (b); i < i##_last; ++i)
#define fort(i, a, b) for (int i = (a), i##_last = (b); i <= i##_last; ++i)
#define ford(i, a, b) for (int i = (a), i##_last = (b); i >= i##_last; --i)
#define fi first
#define se second
#define pb push_back
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;
using ll = long long;
using ld = long double;

template<class A, class B> bool maxi(A &a, const B &b) {return (a < b) ? (a = b, true):false;};
template<class A, class B> bool mini(A &a, const B &b) {return (a > b) ? (a = b, true):false;};

typedef unsigned long long ull;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;

class FenwickTree {
private:
    int n;
    std::vector<int> bit;
public:

    FenwickTree(): n(0) {};
    FenwickTree(const int n): n(n), bit(n + 1) {};

    void resize(const int newSize) {
        n = newSize;
        bit.resize(newSize + 1);
    }

    void reload() {
        for (int i = 1; i <= n; ++i)
            bit[i] = 0;
    }

    void update(int q, const int val) {
        for (++q; q <= n; q += q & -q)
            bit[q] += val;
    }

    int query(int q) const {
        int result = 0;
        for (++q; q; q -= q & -q)
            result += bit[q];
        return result;
    };

    int query(const int l, const int r) const {
        return query(r) - query(l - 1);
    };
};

constexpr int MAX_N = 50'004, MAX_K = 31, INF = 0X3F3F3F3F;
const double EPSILON = 1E-9;

bool checkSmaller(const double l, const double r) {
    return l + EPSILON < r;
}

bool checkEqual(const double l, const double r) {
    return fabs(r - l) <= EPSILON;
}

bool checkSmallerOrEqual(const double l, const double r) {
    return checkEqual(l, r) || checkSmaller(l, r);
}

signed nx, ny, bound, before[MAX_N], under[MAX_N], above[MAX_N], height[MAX_N];
bool visited[MAX_N], possible[MAX_K], newlyPossible[MAX_K];
vi vx, vy, rows[MAX_N], columns[MAX_N], graph[MAX_N];
int N, K, x[MAX_N], y[MAX_N], k[MAX_N];
double upperBound;
FenwickTree bit;

double calculateSquare(const double t) {
    return t * t;
}

double calculateDistance(const int u, const int v) {
    return sqrt(calculateSquare(vx[x[u]] - vx[x[v]]) + calculateSquare(vy[y[u]] - vy[y[v]]));
}

int getSubtraction(int x, const int y) {
    if ((x -= y) < 0)
        x += K;
    return x;
}

bool check(const double limit) {
    set<int> positions;

    upperBound = limit;

    fore(i, 0, N) {
        graph[i].clear();
        visited[i] = false;
    }

    for (int g = 0, j = 0; j < nx; ++j) {
        for (; checkSmaller(limit, vx[j] - vx[g]); ++g);
        under[j] = above[j] = 0;
        before[j] = g;
    }

    bit.reload();

    for (int l = 0, i = 0, r = 0, newHeight; i < ny; ++i) {

        for (; r < ny && checkSmallerOrEqual(vy[r] - vy[i], limit); ++r)
            for (const int &z : rows[r]) {
                const int &p = x[z];
                for (; y[columns[p][above[p]]] <= r; ++above[p]);
                --above[p];
                newHeight = above[p] - under[p] + 1;
                bit.update(p, newHeight);
                height[p] = newHeight;
                positions.insert(p);
            }

        for (; checkSmaller(limit, vy[i] - vy[l]); ++l)
            for (const int &z : rows[l]) {
                const int &p = x[z];
                for (; y[columns[p][under[p]]] <= l; ++under[p]);
                newHeight = above[p] - under[p] + 1;
                bit.update(p, newHeight);
                height[p] = newHeight;
                if (newHeight == 0)
                    positions.erase(p);
            }

        for (const int &u : rows[i]) {
            const int &t = x[u];
            if (bit.query(before[t], t) > bound)
                return true;
            for (set<int>::iterator e = positions.lower_bound(before[t]); e != positions.end(); ++e) {
                const auto p = *e;
                if (p > t)
                    break;
                fort(z, under[p], above[p]) {
                    const int &v = columns[p][z];
                    if (u == v || (x[u] == x[v] && y[v] < y[u]))
                        continue;
                    if (checkSmallerOrEqual(calculateDistance(u, v), upperBound)) {
                        graph[u].pb(v);
                        graph[v].pb(u);
                    }
                }
            }
        }
    }

    queue<int> q;

    fore(u, 0, N) {
        if (visited[u])
            continue;
        fore(k, 0, K)
            possible[k] = false;

        q.push(u);
        visited[u] = true;

        for (; !q.empty(); q.pop()) {
            const int &u = q.front();

            fore(t, 0, K)
                newlyPossible[t] = possible[t] || possible[getSubtraction(t, k[u])];

            fore(t, 0, K)
                possible[t] = newlyPossible[t];

            possible[k[u]] = true;

            for (const int &v : graph[u]) {
                if (visited[v])
                    continue;
                visited[v] = true;
                q.push(v);
            }
        }

        if (possible[0])
            return true;
    }

    return false;
}

signed main() {

    double low = 0, middle, high = 2E9;

    #ifdef LOCAL
    freopen("input.INP", "r", stdin);
    #endif // LOCAL
    cin.tie(0) -> sync_with_stdio(0);
    cout.tie(0);
    cout.precision(3);
    cout.setf(ios::fixed, ios::floatfield);

    cin >> N >> K;

    fore(i, 0, N) {
        cin >> x[i] >> y[i] >> k[i];
        vx.pb(x[i]);
        vy.pb(y[i]);
        k[i] %= K;
    }

    sort(all(vx));
    sort(all(vy));
    vx.erase(unique(all(vx)), vx.end());
    vy.erase(unique(all(vy)), vy.end());
    nx = vx.size();
    ny = vy.size();
    bit.resize(nx);

    fore(i, 0, N) {
        x[i] = lower_bound(all(vx), x[i]) - vx.begin();
        y[i] = lower_bound(all(vy), y[i]) - vy.begin();
        rows[y[i]].pb(i);
    }

    fore(i, 0, ny)
        for (const auto &z : rows[i])
            columns[x[z]].push_back(z);

    x[N] = y[N] = INF;

    fore(j, 0, nx)
        columns[j].pb(N);

    bound = 8 * K;

    for (; low + 1E-5 < high;) {
        middle = (low + high) / 2;
        if (check(middle))
            high = middle;
        else
            low = middle;
    }

    cout << high << '\n';

    return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3928 KB Output is correct
2 Correct 2 ms 3932 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3932 KB Output is correct
2 Correct 2 ms 3932 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3992 KB Output is correct
2 Correct 9 ms 4184 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3932 KB Output is correct
2 Correct 8 ms 4264 KB Output is correct

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3928 KB Output is correct
2 Correct 6 ms 4308 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3932 KB Output is correct
2 Correct 8 ms 4188 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3984 KB Output is correct
2 Correct 11 ms 4188 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3932 KB Output is correct
2 Correct 6 ms 4184 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3932 KB Output is correct
2 Correct 229 ms 7676 KB Output is correct

Subtask #10
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3928 KB Output is correct
2 Correct 764 ms 16080 KB Output is correct

Subtask #11
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3932 KB Output is correct
2 Correct 737 ms 15268 KB Output is correct

Subtask #12
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3928 KB Output is correct
2 Correct 649 ms 12872 KB Output is correct

Subtask #13
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3928 KB Output is correct
2 Correct 690 ms 14080 KB Output is correct

Subtask #14
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3928 KB Output is correct
2 Correct 718 ms 14444 KB Output is correct

Subtask #15
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3988 KB Output is correct
2 Correct 652 ms 10968 KB Output is correct

Subtask #16
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3932 KB Output is correct
2 Correct 656 ms 11484 KB Output is correct

Subtask #17
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3932 KB Output is correct
2 Correct 576 ms 11644 KB Output is correct

Subtask #18
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3932 KB Output is correct
2 Correct 629 ms 11712 KB Output is correct

Subtask #19
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3988 KB Output is correct
2 Correct 622 ms 10956 KB Output is correct

Subtask #20
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3932 KB Output is correct
2 Correct 608 ms 10816 KB Output is correct