Submission #1211748

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211748		Adomas08	Nile (IOI24_nile)	C++20	17 / 100	2095 ms	13440 KiB

nile

#include "nile.h"
#include <bits/stdc++.h>

using namespace std;

std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A,
                                       std::vector<int> B, std::vector<int> E) {
  int Q = (int)E.size(), n = (int)A.size();
  long long sum = 0, diff, diffe = 0;
  std::vector<long long> R(Q, 0);
  vector <pair<int, int>> F;
  for (int i = 0; i < Q; i++){
    F.push_back({E[i], i});
  }
  vector <long long> diffs;
  sort(F.begin(), F.end());
  vector <pair<int, long long>> C;
  for (int i = 0; i < A.size(); i++){
    C.push_back({W[i], A[i] - B[i]});
    diff = B[i];
    sum += diff;
  }
  sort(C.begin(), C.end());
  vector <pair<long long, pair<int, int>>> costs;
  for (int i = 0; i < n - 1; i++){
     costs.push_back({C[i+1].first - C[i].first, {i, i + 1}});
     if (i < n - 2) costs.push_back({C[i+2].first - C[i].first, {i, i + 2}});
  }
  sort(costs.begin(), costs.end());
  vector <pair<int, int>> segments;
  vector<long long> mino, mine, mins;
  for (int i = 0; i < n; i++){
    segments.push_back({i, i});
    diffs.push_back(C[i].second);
    diffe += C[i].second;
    if (i % 2 == 0){
        mine.push_back(C[i].second);
        mino.push_back(INT_MAX);
        mins.push_back(INT_MAX);
    }
    else{
        mino.push_back(C[i].second);
        mine.push_back(INT_MAX);
        mins.push_back(INT_MAX);
    }
  }
  int cur = 0;
  for (int i = 0; i < Q; i++){
        int q = F[i].first, s = F[i].second;
        while (cur != costs.size() && costs[cur].first <= q){
            int a = costs[cur].second.first;
            int b = costs[cur].second.second;
            if (b - a == 1){
                int start = 0, ends = segments.size() - 2;
                while (segments[start].second != a){
                    int k = (start + ends + 1) / 2;
                    if (segments[k].second <= a){
                        start = k;
                    }
                    else ends = k - 1;
                }
                diffe -= diffs[start];
                diffe -= diffs[start+1];
                segments.insert(segments.begin() + start, {segments[start].first, segments[start+1].second});
                segments.erase(segments.begin() + start + 1);
                segments.erase(segments.begin() + start + 1);
                diffs.erase(diffs.begin() + start);
                diffs.erase(diffs.begin() + start);
                mins.insert(mins.begin() + start, min(mins[start], mins[start+1]));
                mins.erase(mins.begin() + start + 1);
                mins.erase(mins.begin() + start + 1);
                mino.insert(mino.begin() + start, min(mino[start], mino[start+1]));
                mino.erase(mino.begin() + start + 1);
                mino.erase(mino.begin() + start + 1);
                mine.insert(mine.begin() + start, min(mine[start], mine[start+1]));
                mine.erase(mine.begin() + start + 1);
                mine.erase(mine.begin() + start + 1);
                if ((segments[start].second + 1 - segments[start].first) % 2 == 0) diffs.insert(diffs.begin() + start, 0);
                else{
                    long long g;
                    if (segments[start].first % 2 == 0){
                        g = mine[start];
                    }
                    else g = mino[start];
                    g = min(g, mins[start]);
                    diffs.insert(diffs.begin() + start, g);
                    diffe += g;
                }
            }
            else{
                int start = 0, ends = segments.size() - 1;
                while (start != ends){
                    int k = (start + ends + 1) / 2;
                    if (segments[k].first <= a){
                        start = k;
                    }
                    else ends = k - 1;
                }
                mins[start] = min(mins[start], C[a+1].second);
                diffe -= diffs[start];
                diffs[start] = min(diffs[start], mins[start]);
                diffe += diffs[start];
            }
            cur++;
        }
        R[s] = sum + diffe;
  }
  return R;
}

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