Submission #1126145

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126145		duckindog	Catfish Farm (IOI22_fish)	C++20	18 / 100	284 ms	78152 KiB

fish

#include <bits/stdc++.h>

using namespace std;

#ifndef LOCAL
#include "fish.h"
#endif

const int N = 300'000 + 10;
int n, m;
struct Fish { 
  int x, y, w;
} fish[N];

vector<int> pos[N];
vector<long long> h[N];
vector<long long> in[N], de[N];

long long max_weights(int inN, int inM, 
                        vector<int> inX, vector<int> inY, vector<int> inW) {
  { // input
    n = inM; m = inN;
    for (int i = 1; i <= n; ++i) 
      fish[i] = {inX[i - 1] + 1, inY[i - 1] + 1, inW[i - 1]};
  }
  
  for (int i = 1; i <= n; ++i) {
    pos[fish[i].x - 1].push_back(fish[i].y);
    pos[fish[i].x].push_back(fish[i].y);
    pos[fish[i].x + 1].push_back(fish[i].y);
  }
  for (int i = 0; i <= m + 1; ++i) { 
    pos[i].push_back(0);
    sort(pos[i].begin(), pos[i].end());
    pos[i].erase(unique(pos[i].begin(), pos[i].end()), pos[i].end());
    
    h[i].resize(pos[i].size() + 2);
    in[i].resize(pos[i].size() + 2);
    de[i].resize(pos[i].size() + 2);
  }

  for (int i = 1; i <= n; ++i) { 
    const auto& [x, y, w] = fish[i];
    int it = lower_bound(pos[x].begin(), pos[x].end(), y) - pos[x].begin();
    h[x][it] = w;
  }
  for (int i = 1; i <= m; ++i) { 
    for (int j = 1; j < (int)pos[i].size(); ++j) h[i][j] += h[i][j - 1];
  }
  
  for (int i = 1; i <= m; ++i) { 
    const int sz = pos[i].size() - 1;
    
    { // calculate sz
      if (i > 1) { // start of in
        { // best[<i][j] -> best i j
          long long small = 0;
          int it1 = 0, it2 = 0, it3 = 0, it4 = 0; // it1 for i - 2, it2 for i - 1, it3 for i - 1 it4 for i + 1
          for (int j = 1; j <= sz; ++j) { 
            auto& ret = in[i][j];

            while (it1 < (int)pos[i - 2].size() && pos[i - 2][it1] <= pos[i][j]) { 
              while (it2 < (int)pos[i - 1].size() && pos[i - 1][it2] <= pos[i - 2][it1]) it2 += 1;
              small = max(small, de[i - 2][it1] - h[i - 1][it2 - 1]);
              it1 += 1;
            }
            while (it3 < (int)pos[i - 1].size() && pos[i - 1][it3] <= pos[i][j]) it3 += 1;
            while (it4 < (int)pos[i + 1].size() && pos[i + 1][it4] <= pos[i][j]) it4 += 1;
            ret = max(ret, h[i - 1][it3 - 1] + small + h[i + 1][it4 - 1]);
          }
        }

        { // best[>i][j] -> best i j
          long long great = 0;
          int it1 = pos[i - 2].size() - 1, it2 = pos[i + 1].size() - 1; // it1 for i - 2, it2 for i + 1
          for (int j = sz; j >= 1; --j) { 
            auto& ret = in[i][j];

            while (it1 >= 0 && pos[i - 2][it1] >= pos[i][j]) { 
              great = max(great, de[i - 2][it1]);
              it1 -= 1;
            }
            while (it2 >= 0 && pos[i + 1][it2] > pos[i][j]) it2 -= 1;

            ret = max(ret, great + (it2 == -1 ? 0 : h[i + 1][it2]));
          }
        }
      }

      { // pre is in and now is in
        long long ma = 0;
        int it1 = 0, it2 = 0; //it1 for i - 1, it2 for i + 1;
        for (int j = 1; j <= sz; ++j) { 
          auto& ret = in[i][j];

          while (it1 < (int)pos[i - 1].size() && pos[i - 1][it1] <= pos[i][j]) { 
            if (i == 3 && j == 1) { 
              // cerr << pos[i - 1][it1] << " " << in[i - 1][it1] << " " << h[i - 1][it1] << " " << h[i][j] << "\n";
              // cerr << in[i - 1][it1] << "\n";
            }
            ma = max(ma, in[i - 1][it1] - h[i - 1][it1] - h[i][j]);
            it1 += 1;
          }
          while (it2 < (int)pos[i + 1].size() && pos[i + 1][it2] <= pos[i][j]) it2 += 1;
          if (i == 3 && j == 1) { 
            // cerr << ma << "\n";
            // cerr << it1 << " " << h[i - 1][it1] << "\n";
          }
          ret = max(ret, h[i - 1][it1 - 1] + ma + h[i + 1][it2 - 1]);
        }
      }
    }

    { // calculate de
      long long ma = 0;
      int it1 = pos[i - 1].size() - 1, it2 = pos[i + 1].size() - 1; // it1 for i + 1, it2 for i + 1;
      for (int j = sz; j >= 1; --j) { 
        auto& ret = de[i][j];
        
        while (it1 >= 0 && pos[i - 1][it1] >= pos[i][j]) { 
          ma = max(ma, de[i - 1][it1]);
          it1 -= 1;
        }
        while (it2 >= 0 && pos[i + 1][it2] > pos[i][j]) it2 -= 1;
        
        ret = max({ret, ma - h[i][j] + (it2 == -1 ? 0 : h[i + 1][it2]), in[i][j]});
      }

      for (int j = 0; j < (int)pos[i - 1].size(); ++j) de[i][0] = max(de[i][0], de[i - 1][j]);
    }
  }
  
  return *max_element(de[m].begin(), de[m].end());
}

#ifdef LOCAL
int main() {
  int N, M;
  assert(2 == scanf("%d %d", &N, &M));

  std::vector<int> X(M), Y(M), W(M);
  for (int i = 0; i < M; ++i) {
    assert(3 == scanf("%d %d %d", &X[i], &Y[i], &W[i]));
  }

  long long result = max_weights(N, M, X, Y, W);
  printf("%lld\n", result);
  return 0;
}
#endif

• Subtask 1: 3 / 3
• Subtask 2: 6 / 6
• Subtask 3: 9 / 9
• Subtask 4: 0 / 14
• Subtask 5: 0 / 21
• Subtask 6: 0 / 17
• Subtask 7: 0 / 14
• Subtask 8: 0 / 16