Submission #426510

#	Time	Username	Problem	Language	Result	Execution time	Memory
426510		xiaowuc1	수족관 3 (KOI13_aqua3)	C++17	100 / 100	521 ms	57928 KiB

aqua3

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <vector>

using namespace std;

// BEGIN NO SAD
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
typedef vector<int> vi;
#define f first
#define s second
#define derr if(0) cerr
// END NO SAD

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<vector<ll>> matrix;

const int SZ = 1 << 19;

pair<ll, int> ragetree[2*SZ];
ll ragetreelazy[2*SZ];
void apply(int idx, ll val) {
  ragetree[idx].f += val;
  if(idx < SZ) ragetreelazy[idx] += val;
}
void pushdown(int idx) {
  if(ragetreelazy[idx]) {
    apply(2*idx, ragetreelazy[idx]);
    apply(2*idx+1, ragetreelazy[idx]);
    ragetreelazy[idx] = 0;
  }
}
void pullup(int idx) {
  ragetree[idx] = max(ragetree[2*idx], ragetree[2*idx+1]);
}
void upd(int idx, int start, int sz, int lhs, int rhs, ll delta) {
  int end = start + sz - 1;
  if(start > rhs || end < lhs) return;
  if(start >= lhs && end <= rhs) apply(idx, delta);
  else {
    pushdown(idx);
    upd(2*idx, start, sz/2, lhs, rhs, delta);
    upd(2*idx+1, start+sz/2, sz/2, lhs, rhs, delta);
    pullup(idx);
  }
}
void upd(int lhs, int rhs, ll delta) {
  upd(1, 0, SZ, lhs, rhs, delta);
}
pii vertices[300000];
int n;
ll vertexweight[SZ];
vector<int> treechild[SZ];
int treepar[SZ];
bool consumed[SZ];
int starttov[SZ];
int treestart[SZ];
int treesz[SZ];
int numnodes = 1;

void dfsforeuler(int curr, int& t) {
  starttov[t] = curr;
  treestart[curr] = t++;
  treesz[curr] = 1;
  for(int out: treechild[curr]) {
    dfsforeuler(out, t);
    treesz[curr] += treesz[out];
  }
}

void solve() {
  for(int i = SZ; i < 2*SZ; i++) ragetree[i].s = i-SZ;
  for(int i = SZ-1; i > 0; i--) pullup(i);
  cin >> n;
  for(int i = 0; i < n; i++) cin >> vertices[i].f >> vertices[i].s;
  set<array<int, 4>> sections; // maxx, sz to left, height, id
  sections.insert({vertices[n-1].f, vertices[n-1].f, 0, 0});
  vector<array<int, 3>> horizontalsegs; // height, lhs, rhs
  for(int i = 1; i+1 < n; i += 2) {
    horizontalsegs.pb({vertices[i].s, vertices[i].f, vertices[i+1].f});
  }
  sort(all(horizontalsegs));
  for(auto seg: horizontalsegs) {
    auto it = sections.lb({seg[1], -1, -1, -1});
    assert(it != sections.end());
    auto section = *it;
    sections.erase(section);
    vertexweight[section[3]] = (seg[0] - section[2]) * (ll)(section[1]);
    derr << "horizontal segment is " << seg[0] << " from " << seg[1] << " to " << seg[2] << endl;
    derr << section[3] << ": " << vertexweight[section[3]] << endl;
    int sectionlhs = section[0] - section[1];
    int sectionrhs = section[0];
    if(seg[1] > sectionlhs) {
      treechild[section[3]].pb(numnodes);
      treepar[numnodes] = section[3];
      sections.insert({seg[1], seg[1] - sectionlhs, seg[0], numnodes++});
    }
    if(seg[2] < sectionrhs) {
      treechild[section[3]].pb(numnodes);
      treepar[numnodes] = section[3];
      sections.insert({sectionrhs, sectionrhs - seg[2], seg[0], numnodes++});
    }
  }
  {
    int start = 0;
    dfsforeuler(0, start);
  }
  for(int i = 0; i < numnodes; i++) {
    upd(treestart[i], treestart[i] + treesz[i] - 1, vertexweight[i]);
  }
  assert(numnodes <= SZ);
  int k;
  cin >> k;
  ll ret = 0;
  while(k--) {
    auto curr = ragetree[1];
    if(curr.f == 0) break;
    ret += curr.f;
    int v = starttov[curr.s];
    derr << "drain " << curr.f << " " << curr.s << endl;
    while(!consumed[v]) {
      derr << "consume " << treestart[v] << " " << treesz[v] << " of weight " << vertexweight[v] << endl;
      upd(treestart[v], treestart[v] + treesz[v] - 1, -vertexweight[v]);
      consumed[v] = true;
      v = treepar[v];
    }
  }
  cout << ret << "\n";
}

// what would chika do
// are there edge cases (N=1?)
// are array sizes proper (scaled by proper constant, for example 2* for koosaga tree)
// integer overflow?
// DS reset properly between test cases
// are you doing geometry in floating points

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  solve();
}

• Subtask 1: 18 / 18
• Subtask 2: 30 / 30
• Subtask 3: 21 / 21
• Subtask 4: 15 / 15
• Subtask 5: 16 / 16