Submission #1109896

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109896		Trisanu_Das	Nile (IOI24_nile)	C++17	100 / 100	86 ms	14024 KiB

nile

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
using pii = pair<int, int>;
 
const int MAXN = 1e5 + 5;
 
int max_val[MAXN] = {0};
int sz[MAXN] = {0};
int parent[MAXN] = {0};
int value[MAXN][2] = {0};
 
int find(int r) {
    return parent[r] == r ? r : parent[r] = find(parent[r]);
}
 
int calculate(int u) {
    if (sz[u] % 2 == 0) return 0;
    return max(value[u][u & 1], max_val[u]);
}
 
vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
    int n = W.size();
    int m = E.size();
    vector<pair<int, pii>> v;
 
    for (int i = 0; i < n; i++) {
        v.push_back({W[i], {A[i], B[i]}});
    }
    sort(v.begin(), v.end());
 
    for (int i = 0; i < n; i++) {
        W[i] = v[i].first;
        A[i] = v[i].second.first;
        B[i] = v[i].second.second;
    }
 
    vector<pii> q1, q2;
    for (int i = 0; i < n; i++) {
        parent[i] = i;
        sz[i] = 1;
        value[i][i & 1] = B[i] - A[i];
        max_val[i] = -2e9;
        value[i][(i + 1) & 1] = -2e9;
    }
 
    for (int i = 0; i < n - 1; i++) {
        q1.push_back({W[i + 1] - W[i], i});
    }
    for (int i = 1; i < n - 1; i++) {
        q2.push_back({W[i + 1] - W[i - 1], i});
    }
    sort(q1.begin(), q1.end());
    sort(q2.begin(), q2.end());
 
    ll result_sum = 0;
    for (int i = 0; i < n; i++) {
        result_sum += A[i];
    }
 
    vector<pii> queries;
    for (int i = 0; i < m; i++) {
        queries.push_back({E[i], i});
    }
    sort(queries.begin(), queries.end());
    int id1 = 0, id2 = 0;
    vector<ll> res(m, 0);
    for (auto [d, i] : queries) {
        while (id1 < q1.size() && q1[id1].first <= d) {
            int u = find(q1[id1].second), v = find(q1[id1].second + 1);
            result_sum += calculate(u) + calculate(v);
            parent[u] = v;
            sz[v] += sz[u];
            value[v][0] = max(value[v][0], value[u][0]);
            value[v][1] = max(value[v][1], value[u][1]);
            max_val[v] = max(max_val[v], max_val[u]);
            result_sum -= calculate(v);
            id1++;
        }
        while (id2 < q2.size() && q2[id2].first <= d) {
            int u = find(q2[id2].second);
            result_sum += calculate(u);
            max_val[u] = max(max_val[u], B[q2[id2].second] - A[q2[id2].second]);
            result_sum -= calculate(u);
            id2++;
        }
        res[i] = result_sum;
    }
    return res;
}

Compilation message (stderr)

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:70:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |         while (id1 < q1.size() && q1[id1].first <= d) {
      |                ~~~~^~~~~~~~~~~
nile.cpp:81:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |         while (id2 < q2.size() && q2[id2].first <= d) {
      |                ~~~~^~~~~~~~~~~

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 13 / 13
• Subtask 3: 17 / 17
• Subtask 4: 11 / 11
• Subtask 5: 20 / 20
• Subtask 6: 15 / 15
• Subtask 7: 18 / 18