Submission #1257285

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257285		nerrrmin	Nile (IOI24_nile)	C++20	0 / 100	28 ms	10432 KiB

nile

#include "nile.h"
#define pb push_back
#include<bits/stdc++.h>
using namespace std;
const int maxn = 3e5 + 10;
int n, q;
long long w[maxn], a[maxn], b[maxn];

long long dp[maxn]; /// best match count
long long r[maxn];
long long ans;
long long pa[maxn], sz[maxn], res[maxn];
int find_leader(int i)
{
    if(pa[i] == i)return i;
    return (pa[i] = find_leader(pa[i]));
}
void unite(int i, int j)
{
    i = find_leader(i);
    j = find_leader(j);
    ans -= res[i];
    ans -= res[j];
    sz[i] += sz[j];
    pa[j] = i;
    res[i] = sz[i] + (sz[i] % 2);
    ans += res[i];
}
vector < pair < int, int > > u;
void solve()
{

   vector < pair < int, int > > g;
   for (int i = 1; i < n; ++ i)
   {
       int d = w[i] - w[i-1];
       g.push_back(make_pair(d, i-1));
   }
   sort(g.begin(), g.end());
   int i = 0;
    for (auto &[dif, pos]: u)
    {
        while(i < g.size() && g[i].first <= dif)
        {
            int posx = g[i].second;
            int posy = posx + 1;
            unite(posx, posy);
            i ++;
        }
        r[pos] = ans;
    }
}

struct p
{
    int w, a, b;
    p(){};
    p(int _w, int _a, int _b)
    {
        w = _w;
        a = _a;
        b = _b;
    }
};

bool cmp(p p1, p p2)
{
    return (p1.w < p2.w);
}
std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A,
                                       std::vector<int> B, std::vector<int> E)
{
    n = W.size();
    for (int i = 0; i < n; ++ i)
        w[i] = W[i];
    for (int i = 0; i < n; ++ i)
        a[i] = A[i];
    for (int i = 0; i < n; ++ i)
        b[i] = B[i];
    vector < p > g;
    for (int i = 0; i < n; ++ i)
        g.pb(p(w[i], a[i], b[i]));
    sort(g.begin(), g.end(), cmp);
    int i = 0;
    for (auto &[ww, aa, bb]: g)
    {

        w[i] = ww;
        a[i] = aa;
        b[i] = bb;
        i ++;
    }
    for (int i = 0; i < n; ++ i)
    {
        pa[i] = i;
        sz[i] = 1;
        res[i] = a[i];
        ans += a[i];
    }
    q = (int)E.size();
    vector < long long > result;
    for (int i = 0; i < E.size(); ++ i)
    {
        u.pb(make_pair(E[i], i));
       // res.pb(solve(d));
    }
    solve();

    for (int i = 0; i < q; ++ i)
        result.pb(r[i]);
    return result;
}

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