oj.uz

Submission #1088048

# Submission time Handle Problem Language Result Execution time Memory
1088048 2024-09-13T18:47:20 Z nguyen31hoang08minh2003 Drzava (COCI15_drzava) C++14
72 / 160
 1000 ms 61672 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;

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];
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;

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]]));
}

template<class T>
class SegmentTree {
private:

    int length;
    std::vector<T> total;

    void modify(const int q, const T value, const int i, const int l, const int r) {
        if (q < l || r < q)
            return;
        if (l == r) {
            total[i] = value;
            return;
        }
        const int m = l + r >> 1;
        modify(q, value, i << 1, l, m);
        modify(q, value, i << 1 | 1, m + 1, r);
        total[i] = total[i << 1] + total[i << 1 | 1];
    }

    void update(const int q, const T value, const int i, const int l, const int r) {
        if (q < l || r < q)
            return;
        total[i] += value;
        if (l == r)
            return;
        const int m = l + r >> 1;
        update(q, value, i << 1, l, m);
        update(q, value, i << 1 | 1, m + 1, r);
    }

    T query(const int ql, const int qr, const int i, const int l, const int r) const {
        if (qr < l || r < ql)
            return 0;
        if (ql <= l && r <= qr)
            return total[i];
        const int m = l + r >> 1;
        return query(ql, qr, i << 1, l, m) + query(ql, qr, i << 1 | 1, m + 1, r);
    }

    void build(const int i, const int l, const int r) {
        total[i] = 0;
        if (l == r)
            return;
        const int m = l + r >> 1;
        build(i << 1, l, m);
        build(i << 1 | 1, m + 1, r);
    }

    void connect(const int ql, const int qr, const int u, const int i, const int l, const int r) const {
        if (qr < l || r < ql || total[i] == 0)
            return;
        if (l == r) {
            fort(z, under[l], above[r]) {
                const int &v = columns[r][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);
                }
            }
            return;
        }
        const int m = l + r >> 1;
        connect(ql, qr, u, i << 1, l, m);
        connect(ql, qr, u, i << 1 | 1, m + 1, r);
    }

public:

    SegmentTree(): length(0) {};
    SegmentTree(const int n): length(n), total(n + 5 << 2) {};

    void resize(int m) {
        length = m;
        m = length + 5 << 2;
        total.resize(m);
    }

    void reload() {
        std::fill(total.begin(), total.end(), 0);
    }

    void modify(const int q, const T value) {
        modify(q, value, 1, 0, length - 1);
    }

    void update(const int q, const T value) {
        update(q, value, 1, 0, length - 1);
    }

    T query(const int ql, const int qr) const {
        return query(ql, qr, 1, 0, length - 1);
    }

    void connect(const int ql, const int qr, const int id) const {
        connect(ql, qr, id, 1, 0, length - 1);
    }

    void build() {
        build(1, 0, length - 1);
    }

    T top() const {
        return total[1];
    }

    int getLength() const {
        return this -> length;
    }

    virtual ~SegmentTree() {}

};

SegmentTree<int> segmentTree;

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

bool check(const double limit) {

    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;
    }

    segmentTree.reload();

    for (int l = 0, i = 0, r = 0; 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];
                segmentTree.modify(p, above[p] - under[p] + 1);
            }

        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]);
                segmentTree.modify(p, above[p] - under[p] + 1);
            }

        for (const int &z : rows[i]) {
            if (segmentTree.query(before[x[z]], x[z]) > bound)
                return true;
            segmentTree.connect(before[x[z]], x[z], z);
        }
    }

    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();
    segmentTree.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-4 < high;) {
        middle = (low + high) / 2;
        if (check(middle))
            high = middle;
        else
            low = middle;
    }

    cout << high << '\n';

    return 0;
}

Compilation message

drzava.cpp: In instantiation of 'void SegmentTree<T>::resize(int) [with T = int]':
drzava.cpp:310:26:   required from here
drzava.cpp:157:20: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
  157 |         m = length + 5 << 2;
      |             ~~~~~~~^~~
drzava.cpp: In instantiation of 'void SegmentTree<T>::modify(int, T, int, int, int) [with T = int]':
drzava.cpp:166:15:   required from 'void SegmentTree<T>::modify(int, T) [with T = int]'
drzava.cpp:229:62:   required from here
drzava.cpp:95:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   95 |         const int m = l + r >> 1;
      |                       ~~^~~
drzava.cpp: In instantiation of 'T SegmentTree<T>::query(int, int, int, int, int) const [with T = int]':
drzava.cpp:174:21:   required from 'T SegmentTree<T>::query(int, int) const [with T = int]'
drzava.cpp:240:53:   required from here
drzava.cpp:117:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  117 |         const int m = l + r >> 1;
      |                       ~~^~~
drzava.cpp: In instantiation of 'void SegmentTree<T>::connect(int, int, int, int, int, int) const [with T = int]':
drzava.cpp:178:16:   required from 'void SegmentTree<T>::connect(int, int, int) const [with T = int]'
drzava.cpp:242:54:   required from here
drzava.cpp:145:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  145 |         const int m = l + r >> 1;
      |                       ~~^~~

Subtask #1
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 #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 3932 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3932 KB Output is correct
2 Correct 12 ms 4780 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 11 ms 4296 KB Output is correct

Subtask #5
8.0 / 8.0

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

Subtask #6
8.0 / 8.0

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

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3928 KB Output is correct
2 Correct 14 ms 4700 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 8 ms 4348 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 474 ms 10324 KB Output is correct

Subtask #10
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3928 KB Output is correct
2 Execution timed out 1025 ms 58620 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #11
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3928 KB Output is correct
2 Execution timed out 1069 ms 57900 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #12
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3932 KB Output is correct
2 Execution timed out 1088 ms 25912 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #13
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3932 KB Output is correct
2 Execution timed out 1088 ms 29952 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #14
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3932 KB Output is correct
2 Execution timed out 1092 ms 61672 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #15
8.0 / 8.0

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

Subtask #16
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3932 KB Output is correct
2 Execution timed out 1082 ms 17984 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #17
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3932 KB Output is correct
2 Execution timed out 1052 ms 28304 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #18
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3932 KB Output is correct
2 Execution timed out 1058 ms 28448 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #19
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3932 KB Output is correct
2 Execution timed out 1030 ms 15052 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #20
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3928 KB Output is correct
2 Execution timed out 1020 ms 16276 KB Time limit exceeded
3 Halted 0 ms 0 KB -