oj.uz

Submission #1100072

# Submission time Handle Problem Language Result Execution time Memory
1100072 2024-10-12T15:56:23 Z fve5 Nile (IOI24_nile) C++17
38 / 100
 81 ms 13560 KB 
#include "nile.h"
#include <bits/stdc++.h>
using namespace std;

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

    i64 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<int> W, vector<int> A, vector<int> B, vector<int> 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:85:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |     for (int i = 0; i < W.size(); i++) {
      |                     ~~^~~~~~~~~~
nile.cpp:92:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |     for (int i = 0; i < E.size(); i++)
      |                     ~~^~~~~~~~~~
nile.cpp:94:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |     for (int i = 0; i < W.size() - 1; i++)
      |                     ~~^~~~~~~~~~~~~~
nile.cpp:96:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |     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 348 KB Output is correct

Subtask #1
6.0 / 6.0

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

Subtask #2
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 38 ms 9168 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 39 ms 9168 KB Output is correct
2 Correct 40 ms 9160 KB Output is correct
3 Correct 47 ms 9680 KB Output is correct
4 Correct 48 ms 9160 KB Output is correct
5 Correct 46 ms 9676 KB Output is correct
6 Correct 55 ms 8936 KB Output is correct

Subtask #4
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Incorrect 1 ms 600 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 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Incorrect 38 ms 9168 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 39 ms 9168 KB Output is correct
2 Correct 40 ms 9160 KB Output is correct
3 Correct 47 ms 9680 KB Output is correct
4 Correct 48 ms 9160 KB Output is correct
5 Correct 46 ms 9676 KB Output is correct
6 Correct 55 ms 8936 KB Output is correct
7 Correct 67 ms 12996 KB Output is correct
8 Correct 67 ms 12744 KB Output is correct
9 Correct 74 ms 13560 KB Output is correct
10 Correct 73 ms 13256 KB Output is correct
11 Correct 81 ms 12228 KB Output is correct
12 Correct 75 ms 13000 KB Output is correct
13 Correct 75 ms 12484 KB Output is correct
14 Correct 63 ms 13552 KB Output is correct
15 Correct 75 ms 12740 KB Output is correct

Subtask #7
0.0 / 18.0

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