oj.uz

Submission #1100075

# Submission time Handle Problem Language Result Execution time Memory
1100075 2024-10-12T16:03:26 Z fve5 Nile (IOI24_nile) C++17
38 / 100
 88 ms 20424 KB 
#include "nile.h"
#include <bits/stdc++.h>
using namespace std;

#define int i64
typedef long long i64;

struct CC {
    static vector<int> A, B;
    static vector<i64> S;

    int par, size, l, r, best;

    void skip(int i) { best = min(best, A[i] - B[i]); }

    int get_best() const { return min({best, A[l] - B[l], A[r] - B[r]}); }
    i64 get_cost() const { return S[r + 1] - S[l] + (size & 1) * get_best(); }
};
vector<int> CC::A = {};
vector<int> CC::B = {};
vector<i64> CC::S = {};

struct DSU {
    vector<CC> arr;
    i64 cost;

    int find(int u) {
        if (arr[u].par == u) return u;
        return arr[u].par = find(arr[u].par);
    }

    void join(int i) {
        int u = find(i);
        int v = find(i + 1);
        
        if (u == v) return;
        if (arr[u].size < arr[v].size) swap(u, v);

        cost -= arr[u].get_cost();
        cost -= arr[v].get_cost();

        arr[u].size += arr[v].size;
        arr[u].r = max(arr[u].r, arr[v].r);
        arr[u].l = min(arr[u].l, arr[v].l);
        arr[u].best = max(arr[u].best, arr[v].best);

        arr[v].par = u;

        cost += arr[u].get_cost();
    }

    void skip(int i) {
        int u = find(i);

        cost -= arr[u].get_cost();
        arr[u].skip(i);
        cost += arr[u].get_cost();
    }

    DSU(int N) : arr(N), cost(0) {
        for (int i = 0; i < N; i++) {
            arr[i] = {i, 1, i, i, (int)2e9};
            cost += arr[i].get_cost();
        }
    }
};

enum EventType { JOIN, SKIP, QUERY };
struct Event {
    EventType type;
    int time, position;
};

bool operator<(const Event &a, const Event &b) { return tie(a.time, a.type) < tie(b.time, b.type); }

vector<long long> calculate_costs(vector<signed> W, vector<signed> A, vector<signed> B, vector<signed> E) {
    vector<int> order(W.size());
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int u, int v) { return W[u] < W[v]; });
    sort(W.begin(), W.end());

    CC::A.resize(W.size());
    CC::B.resize(W.size());
    CC::S.resize(W.size() + 1);

    for (int i = 0; i < W.size(); i++) {
        CC::A[i] = A[order[i]];
        CC::B[i] = B[order[i]];
        CC::S[i + 1] = CC::S[i] + B[order[i]];
    }

    vector<Event> events;
    for (int i = 0; i < E.size(); i++)
        events.push_back({QUERY, E[i], i});
    for (int i = 0; i < W.size() - 1; i++)
        events.push_back({JOIN, W[i + 1] - W[i], i});
    for (int i = 1; i < W.size() - 1; i++)
        events.push_back({SKIP, W[i + 1] - W[i - 1], i});
    
    DSU dsu(W.size());
    vector<i64> ans(E.size());
    sort(events.begin(), events.end());

    for (auto [type, _, idx]: events) {
        switch (type) {
        case JOIN:
            dsu.join(idx);
            break;
        case SKIP:
            dsu.skip(idx);
            break;
        case QUERY:
            ans[idx] = dsu.cost;
            break;
        }
    }

    return ans;
}

Compilation message

nile.cpp: In function 'std::vector<long long int> calculate_costs(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
nile.cpp:86:23: warning: comparison of integer expressions of different signedness: 'i64' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |     for (int i = 0; i < W.size(); i++) {
      |                     ~~^~~~~~~~~~
nile.cpp:93:23: warning: comparison of integer expressions of different signedness: 'i64' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |     for (int i = 0; i < E.size(); i++)
      |                     ~~^~~~~~~~~~
nile.cpp:95:23: warning: comparison of integer expressions of different signedness: 'i64' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |     for (int i = 0; i < W.size() - 1; i++)
      |                     ~~^~~~~~~~~~~~~~
nile.cpp:97:23: warning: comparison of integer expressions of different signedness: 'i64' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |     for (int i = 1; i < W.size() - 1; i++)
      |                     ~~^~~~~~~~~~~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 352 KB Output is correct

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 612 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 612 KB Output is correct
4 Correct 1 ms 704 KB Output is correct
5 Correct 1 ms 608 KB Output is correct
6 Correct 1 ms 608 KB Output is correct

Subtask #2
0.0 / 13.0

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

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 15296 KB Output is correct
2 Correct 44 ms 15560 KB Output is correct
3 Correct 55 ms 15700 KB Output is correct
4 Correct 56 ms 15508 KB Output is correct
5 Correct 49 ms 15540 KB Output is correct
6 Correct 55 ms 15564 KB Output is correct

Subtask #4
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 612 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 612 KB Output is correct
4 Correct 1 ms 704 KB Output is correct
5 Correct 1 ms 608 KB Output is correct
6 Correct 1 ms 608 KB Output is correct
7 Incorrect 1 ms 608 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 612 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 612 KB Output is correct
4 Correct 1 ms 704 KB Output is correct
5 Correct 1 ms 608 KB Output is correct
6 Correct 1 ms 608 KB Output is correct
7 Incorrect 42 ms 16180 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 15296 KB Output is correct
2 Correct 44 ms 15560 KB Output is correct
3 Correct 55 ms 15700 KB Output is correct
4 Correct 56 ms 15508 KB Output is correct
5 Correct 49 ms 15540 KB Output is correct
6 Correct 55 ms 15564 KB Output is correct
7 Correct 71 ms 20160 KB Output is correct
8 Correct 75 ms 20424 KB Output is correct
9 Correct 76 ms 20416 KB Output is correct
10 Correct 76 ms 20328 KB Output is correct
11 Correct 88 ms 20188 KB Output is correct
12 Correct 78 ms 20420 KB Output is correct
13 Correct 76 ms 20244 KB Output is correct
14 Correct 70 ms 19984 KB Output is correct
15 Correct 81 ms 20420 KB Output is correct

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 352 KB Output is correct
2 Correct 1 ms 612 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 612 KB Output is correct
5 Correct 1 ms 704 KB Output is correct
6 Correct 1 ms 608 KB Output is correct
7 Correct 1 ms 608 KB Output is correct
8 Incorrect 42 ms 16180 KB Output isn't correct
9 Halted 0 ms 0 KB -