Submission #1105446

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105446		LaMatematica14	Nile (IOI24_nile)	C++17	100 / 100	126 ms	34924 KiB

nile

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1<<18;
vector<int> par(1e6);
int fr(int a) {
    if (a == par[a]) return a;
    return par[a] = fr(par[a]);
}

void unite(int a, int b) {
    if (fr(a) == fr(b)) return;
    par[par[a]] = b;
}

long long qq(int a, int l, int r, int lq, int rq, vector<long long> &s) {
    if (l >= lq && r <= rq) return s[a];
    int m = (l+r)/2;
    long long p = 1000000000LL;
    if (m > lq) p = min(p, qq(a<<1, l, m, lq, rq, s));
    if (m < rq) p = min(p, qq(a<<1|1, m, r, lq, rq, s));
    return p;
}


vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
    int N = W.size();
    vector<array<long long, 3>> stt(N); 
    for (int i = 0; i < N; i++) stt[i] = {W[i], B[i], A[i]-B[i]};
    sort(stt.begin(), stt.end());
    
    int Q = E.size();
    par.resize(N); iota(par.begin(), par.end(), 0);
    vector<array<long long, 3>> od;
    for (int i = 0; i < Q; i++) od.push_back({E[i], 3, i});
    for (int i = 0; i < N-1; i++) {
        if (i < N-2) od.push_back({stt[i+2][0]-stt[i][0], 2, i});
        od.push_back({stt[i+1][0]-stt[i][0], 1, i});
    }
    sort(od.begin(), od.end());

    vector<long long> mn(N, 1000000000LL); //pari, dispari, ci sono solo quelli centrali i bordi sono a mano
    vector<long long> s(N);
    for (int i = 0; i < N; i++) {
        s[i] = stt[i][1]+stt[i][2];
    }
    vector<array<long long, 2>> infn(N);
    for (int i = 0; i < N; i++) infn[i][0] = i;
    for (int i = 0; i < N; i++) infn[i][1] = i+1;
    vector<long long> sp(maxn<<1, 1000000000LL), sd(maxn<<1, 1000000000LL);
    for (int i = 0; i < N; i+=2) sp[i+maxn] = stt[i][2];
    for (int i = 1; i < N; i+=2) sd[i+maxn] = stt[i][2];
    for (int i = maxn-1; i > 0; i--) {
        sp[i] = min(sp[i<<1], sp[i<<1|1]);
        sd[i] = min(sd[i<<1], sd[i<<1|1]);
    }

    vector<long long>  ris(Q);
    long long sum = 0;
    for (int i = 0; i < N; i++) sum += A[i];

    vector<long long> pr(N+1, 0);
    for (int i = 1; i <= N; i++) pr[i] = pr[i-1]+stt[i-1][1];

    for (int k = 0; k < od.size(); k++) {
        array<long long, 3> att = od[k];
        if (att[1] == 1) {
            long long a = fr(att[2]), b = fr(att[2]+1);
            sum -= s[a]; sum -= s[b];
            mn[b] = min(mn[a], mn[b]);
            infn[b] = {min(infn[a][0], infn[b][0]), max(infn[a][1], infn[b][1])};
            s[b] = pr[infn[b][1]]-pr[infn[b][0]];
            if ((infn[b][1]-infn[b][0])%2) {
                long long md;
                if (infn[b][0] % 2) md = qq(1, 0, maxn, infn[b][0], infn[b][1], sd);
                else md = qq(1, 0, maxn, infn[b][0], infn[b][1], sp);
                s[b] += min(mn[b], md);
            }
            sum += s[b];
            unite(a, b);
        }
        else if (att[1] == 2) {
            int r = fr(att[2]+1);
            sum -= s[r];
            mn[r] = min(mn[r], stt[att[2]+1][2]);
            s[r] = pr[infn[r][1]]-pr[infn[r][0]];
            if ((infn[r][1]-infn[r][0])%2) {
                long long md;
                if (infn[r][0] % 2) md = qq(1, 0, maxn, infn[r][0], infn[r][1], sd);
                else md = qq(1, 0, maxn, infn[r][0], infn[r][1], sp);
                s[r] += min(mn[r], md);
            }
            sum += s[r];
        }
        else ris[att[2]] = sum;
    }
    return ris;
}

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:64:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     for (int k = 0; k < od.size(); k++) {
      |                     ~~^~~~~~~~~~~

• 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