Submission #1257309

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257309		nerrrmin	Nile (IOI24_nile)	C++20	67 / 100	2093 ms	12884 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];
long long best[maxn], bs[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;
    best[i] = min(best[i], best[j]);
    bs[i] += bs[j];
    res[i] = bs[i] + best[i];//(sz[i] % 2);
    ans += res[i];
}
vector < pair < int, int > > u;
long long solve(int d)
{
    vector < pair < int, int > > pack;
    pack.pb({w[0], 0});
    long long ans = 0;
    for (int i = 1; i < n; ++ i)
    {
        int last = pack[pack.size()-1].first;

         if(w[i] - last <= d)
         {
             pack.pb({w[i], i});
             continue;
         }

         long long sumb = 0, best = 1e17;
         for (int j = 0; j < pack.size(); ++ j)
         {
             int index = pack[j].second;
             sumb += b[index];

             if(j % 2 == 0)best = min(best, a[index] - b[index]);
             else if(j != pack.size()-1)
             {
                 int pre = pack[j-1].first;
                 int nxt = pack[j+1].first;
                 if(nxt - pre <= d)best = min(best, a[index] - b[index]);
             }
         }
         ans += sumb;
         if(pack.size() % 2 == 1)ans += best;
         pack.clear();
         pack.pb({w[i], i});
    }
    long long sumb = 0, best = 1e17;
         for (int j = 0; j < pack.size(); ++ j)
         {
             int index = pack[j].second;
             sumb += b[index];

             if(j % 2 == 0)best = min(best, a[index] - b[index]);
             else if(j != pack.size()-1)
             {
                 int pre = pack[j-1].first;
                 int nxt = pack[j+1].first;
                 if(nxt - pre <= d)best = min(best, a[index] - b[index]);
             }
         }
         ans += sumb;
         if(pack.size() % 2 == 1)ans += best;
         pack.clear();
         return ans;
   /*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];
        bs[i] = b[i];
        best[i] = a[i] - b[i];
        ans += a[i];
    }
    q = (int)E.size();
    vector < long long > result;



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

• 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: 0 / 15
• Subtask 7: 0 / 18