Submission #628828

#	Time	Username	Problem	Language	Result	Execution time	Memory
628828		cadmiumsky	Catfish Farm (IOI22_fish)	C++17	100 / 100	377 ms	25704 KiB

fish

#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
#define int ll

using ll = long long;
using pii = pair<int,int>;
const int nmax = 1e5 + 5, mmax = 3e5 + 5, inf = 1e15 + 5;
int n, m;
vector<pii> cat[nmax]; 

class DS {
  int l, r, flip;
  map<int,int> dp;
  void upd(int poz, int x) {
    if(dp.empty())
      return;
    auto it = dp.upper_bound(poz);
    if(prev(it) -> second >= x) {
      dp[poz] = x;
      return;
    }
    dp[poz] = x;
    while(it != dp.end()) {
      //cerr << poz << ' ' << x << " VS " << it -> first << ' ' << it -> second << '\n';
      if(it -> second <= x)
	dp.erase(it);
      else
	break;
      it = dp.upper_bound(poz);
    }
    return;
  }
  public:
    DS(int x, int val = 0) {
      flip = x;
      l = n + 1;
      r = 2 * n + 1;
      dp[l] = val; 
    }
    int get(int poz) {
      poz += l;
      if(flip) poz = r + l - poz;
      
      if(dp.empty()) return 0;
      auto it = dp.upper_bound(poz);
      if(it == dp.begin()) {
	print();
	assert(false); // oh golly gosh gee sper sa nu ma futa chestia asta cand poate debuggez; upd: da
      }
      
      return prev(it) -> second;
    } 
    void insert(int poz, int x) {
      poz += l;
      if(flip) poz = r + l - poz;
      
      upd(poz, x);
    }
    
    void push_front(int x) {
      l--;
      r--;
      
      if(!dp.empty() && dp.rbegin() -> first > r)
	dp.erase(dp.rbegin() -> first);
      if(dp.empty()) {
	dp[l] = x;
	return; 
      }
      dp[l] = x - 1;
      //cerr << flip << ": ";
      //print();
      upd(l, x);
    }
    void print() {
      cerr << "> " << l << ' ' << r << '\n';
      for(auto [p, x] : dp) {
	cerr << p << ' ' << x << '\n';
      }
      cerr << '\n';
    }
};

#undef int
long long max_weights(int N, int M, std::vector<int> x, std::vector<int> y, std::vector<int> cost) { // rezultatul este: Crescendo[N - 2].fin, Descrescendo[N - 1].deb (adica pune stalp inainte de ultima pozitie)
  #define int ll
  tie(n, m) = pii{N, M};
  for(int i = 0; i < m; i++) {
    cat[x[i]].emplace_back(y[i], cost[i]);
  }
  for(int i = 0; i < n; i++)
    sort(cat[i].begin(), cat[i].end());
  DS cresc(0), decresc(1, -inf);
  int mx = 0, lastcresc = 0, lastdecresc = 0;
  for(int i = 0; i < n; i++) {
    mx = max(lastcresc, mx);
    for(auto [h, w] : cat[i])
      cresc.insert(h, cresc.get(h) + w);
    for(int it = cat[i].size() - 1, h, w; it >= 0; it--) {
      tie(h, w) = cat[i][it];
      decresc.insert(h, decresc.get(h) + w);
    }
    
    //cerr << "<<<<<<<<<<<<<<<<<\n";
    //cerr << lastdecresc << ' ' << lastcresc << '\n';
    //cresc.print();
    //decresc.print();
    
    //cerr << ">>>>>>>>>>>>>>>>>\n";
    
    mx = max(decresc.get(0), mx);
    int temp  = max(0LL, decresc.get(0));
    decresc.push_front(max(lastcresc, lastdecresc));
    lastdecresc = max(0LL, temp);
    int temp2 = cresc.get(n - 1);
    cresc.push_front(max(lastcresc, temp));
    lastcresc = temp2;
  }
  return mx;
}
#undef int


//9 9
//0 0 1
//1 1 2
//2 2 3
//4 0 4
//4 2 5
//6 2 6
//7 1 7
//7 0 8
//8 0 9

//10 10
//0 0 2
//0 9 2
//2 0 2
//2 9 2
//4 0 2
//4 9 2
//6 0 2
//6 9 2
//8 0 2
//8 9 2

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