oj.uz

Submission #1103450

# Submission time Handle Problem Language Result Execution time Memory
1103450 2024-10-21T02:50:26 Z cccc Nile (IOI24_nile) C++17
38 / 100
 145 ms 19392 KB 
#include <bits/stdc++.h>
//#include "nile.h"
#define ld long double
#define f(i, a, b) for(int i = a; i <= b; i++)
#define fr(i, a, b) for(int i = a; i >= b; i--)
#define pii pair <int, int>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define in insert
#define arr(x) array <int, x>
#define vvec vector<vector<int>>
#define Keiiiii ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ___ 1000 * clock() / CLOCKS_PER_SEC

using namespace std;

const int N = 1e5 + 5;
const int mod = 1e9 + 7;
const int inf = 1e9 + 7;
int n, q;
long long res, s[N];
int p[N], L[N], R[N];
vector <pii> ee;
arr(3) a[N];
pii t[N];

struct ST
{
    int st[N * 4];
    void up(int i, int l, int r, int x, int y)
    {
        if(x > r || x < l) return;
        if(l == r) { st[i] = y; return; }
        int mid = (l + r) >> 1;
        up(i << 1, l, mid, x, y);
        up(i << 1 | 1, mid + 1, r, x, y);
        st[i] = min(st[i << 1], st[i << 1 | 1]);
    }

    int get(int i, int l, int r, int x, int y)
    {
        if(x > r || y < l) return inf;
        if(x <= l && r <= y) return st[i];
        int mid = (l + r) >> 1;
        return min(get(i << 1, l, mid, x, y), get(i << 1 | 1, mid + 1, r, x, y));
    }
} F[2], G[2];

int Find(int v) { return v == p[v] ? v : p[v] = Find(p[v]); }

long long get(int l, int r)
{
    if(l == r) return a[l][1];
    long long ans = s[r] - s[l - 1], ex = 0, len = r - l + 1;
    if(len % 2 == 1 && len > 2)
    {
        ex = F[(r - 1) % 2].get(1, 1, n, l, r - 1);
        ex = min(ex, (long long)G[r % 2].get(1, 1, n, l + 1, r - 1));
        ex = min({ex, 1LL * a[l][1] - a[l][2], 1LL * a[r][1] - a[r][2]});
    }
    return ans + ex;
}

void Us(int u, int v)
{
    u = Find(u); v = Find(v);
    if(u == v) return;
    res -= get(L[u], R[u]) + get(L[v], R[v]);
    L[u] = min(L[u], L[v]); R[u] = max(R[u], R[v]);
    res += get(L[u], R[u]); p[v] = u;
}

vector<long long> calculate_costs(
    vector<int> W, vector<int> A,
    vector<int> B, vector<int> E)
{
    n = W.size(); q = E.size();
    f(i, 1, n) a[i][0] = W[i - 1], a[i][1] = A[i - 1], a[i][2] = B[i - 1];
    f(i, 1, q) t[i].fi = E[i - 1], t[i].se = i;
    vector <long long> cc(q); //cerr << q << "\n";
    vector <arr(3)> e;
    f(i, 1, 4 * n)  F[0].st[i] = F[1].st[i] = G[0].st[i] = G[1].st[i] = inf;

    sort(a + 1, a + n + 1);
    sort(t + 1, t + q + 1);
    f(i, 1, n) p[i] = i, L[i] = R[i] = i;
    res = 0;
    f(i, 1, n)
    {
        res += a[i][1];
        s[i] = s[i - 1] + a[i][2];
        if(i % 2 == 0) F[0].up(1, 1, n, i, a[i][1] - a[i][2]);
        else F[1].up(1, 1, n, i, a[i][1] - a[i][2]);
    }
    f(i, 1, n - 1) e.pb({a[i + 1][0] - a[i][0], i, i + 1});
    f(i, 2, n - 1) ee.eb(a[i + 1][0] - a[i - 1][0], i);
    sort(e.begin(), e.end());
    sort(ee.begin(), ee.end());

    int j = 0, j2 = 0;
    f(i, 1, q)
    {
        auto [d, id] = t[i];
        while(j2 < (int)ee.size() && ee[j2].fi <= d)
        {
            int u = ee[j2].se;
            G[u % 2].up(1, 1, n, u, a[u][1] - a[u][2]);
            j2++;
        }

        while(j < n - 1 && e[j][0] <= d) Us(e[j][1], e[j][2]), j++;
        cc[id - 1] = res;
        //cerr << res << "\n";
    }

    return cc;
}

//signed main()
//{
//    Keiiiii
//    if(fopen("TASK.INP", "r"))
//    {
//        freopen("TASK.INP", "r", stdin);
//        freopen("TASK.OUT", "w", stdout);
//    }
//    int n, q; cin >> n;
//    vector <int> A(n), B(n), W(n);
//    f(i, 0, n - 1) cin >> W[i] >> A[i] >> B[i];
//    cin >> q;
//    vector <int> E(q);
//    f(i, 0, q - 1) cin >> E[i];
//    vector <long long> ans = calculate_costs(W, A, B, E);
//    for(auto x : ans) cout << x << "\n";
//}

Subtask #0
0.0 / 0.0

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

Subtask #1
6.0 / 6.0

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

Subtask #2
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 69 ms 15816 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 72 ms 15880 KB Output is correct
2 Correct 72 ms 15816 KB Output is correct
3 Correct 132 ms 17228 KB Output is correct
4 Correct 112 ms 17088 KB Output is correct
5 Correct 77 ms 15820 KB Output is correct
6 Correct 99 ms 16964 KB Output is correct

Subtask #4
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8784 KB Output is correct
2 Correct 2 ms 8784 KB Output is correct
3 Correct 2 ms 8784 KB Output is correct
4 Correct 3 ms 8784 KB Output is correct
5 Correct 3 ms 8784 KB Output is correct
6 Correct 5 ms 8784 KB Output is correct
7 Incorrect 3 ms 8784 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 3 ms 8784 KB Output is correct
2 Correct 2 ms 8784 KB Output is correct
3 Correct 2 ms 8784 KB Output is correct
4 Correct 3 ms 8784 KB Output is correct
5 Correct 3 ms 8784 KB Output is correct
6 Correct 5 ms 8784 KB Output is correct
7 Incorrect 69 ms 15816 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 72 ms 15880 KB Output is correct
2 Correct 72 ms 15816 KB Output is correct
3 Correct 132 ms 17228 KB Output is correct
4 Correct 112 ms 17088 KB Output is correct
5 Correct 77 ms 15820 KB Output is correct
6 Correct 99 ms 16964 KB Output is correct
7 Correct 117 ms 17360 KB Output is correct
8 Correct 98 ms 17344 KB Output is correct
9 Correct 114 ms 17356 KB Output is correct
10 Correct 106 ms 19392 KB Output is correct
11 Correct 113 ms 19392 KB Output is correct
12 Correct 132 ms 17608 KB Output is correct
13 Correct 110 ms 17452 KB Output is correct
14 Correct 145 ms 19136 KB Output is correct
15 Correct 143 ms 19392 KB Output is correct

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8528 KB Output is correct
2 Correct 3 ms 8784 KB Output is correct
3 Correct 2 ms 8784 KB Output is correct
4 Correct 2 ms 8784 KB Output is correct
5 Correct 3 ms 8784 KB Output is correct
6 Correct 3 ms 8784 KB Output is correct
7 Correct 5 ms 8784 KB Output is correct
8 Incorrect 69 ms 15816 KB Output isn't correct
9 Halted 0 ms 0 KB -