oj.uz

Submission #426510

# Submission time Handle Problem Language Result Execution time Memory
426510 2021-06-14T05:49:10 Z xiaowuc1 수족관 3 (KOI13_aqua3) C++17
100 / 100
 521 ms 57928 KB 
#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.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 29036 KB Output is correct
2 Correct 17 ms 29064 KB Output is correct
3 Correct 18 ms 29192 KB Output is correct
4 Correct 22 ms 29108 KB Output is correct
5 Correct 17 ms 29192 KB Output is correct
6 Correct 20 ms 29132 KB Output is correct
7 Correct 19 ms 29124 KB Output is correct
8 Correct 18 ms 29132 KB Output is correct
9 Correct 17 ms 29132 KB Output is correct
10 Correct 19 ms 29104 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 29392 KB Output is correct
2 Correct 21 ms 29316 KB Output is correct
3 Correct 21 ms 29452 KB Output is correct
4 Correct 21 ms 29388 KB Output is correct
5 Correct 26 ms 29472 KB Output is correct
6 Correct 23 ms 29500 KB Output is correct
7 Correct 24 ms 29516 KB Output is correct
8 Correct 25 ms 29448 KB Output is correct
9 Correct 21 ms 29388 KB Output is correct
10 Correct 21 ms 29432 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 280 ms 42992 KB Output is correct
2 Correct 308 ms 46772 KB Output is correct
3 Correct 262 ms 50992 KB Output is correct
4 Correct 309 ms 51120 KB Output is correct
5 Correct 261 ms 51040 KB Output is correct
6 Correct 330 ms 57832 KB Output is correct
7 Correct 292 ms 55624 KB Output is correct
8 Correct 293 ms 55532 KB Output is correct
9 Correct 340 ms 48736 KB Output is correct
10 Correct 357 ms 48524 KB Output is correct
11 Correct 309 ms 57848 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 325 ms 43116 KB Output is correct
2 Correct 296 ms 46924 KB Output is correct
3 Correct 278 ms 51076 KB Output is correct
4 Correct 271 ms 51072 KB Output is correct
5 Correct 269 ms 50992 KB Output is correct
6 Correct 332 ms 57928 KB Output is correct
7 Correct 312 ms 55604 KB Output is correct
8 Correct 293 ms 55612 KB Output is correct
9 Correct 425 ms 48740 KB Output is correct
10 Correct 390 ms 48656 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 384 ms 43120 KB Output is correct
2 Correct 461 ms 46808 KB Output is correct
3 Correct 327 ms 51076 KB Output is correct
4 Correct 384 ms 51012 KB Output is correct
5 Correct 380 ms 51120 KB Output is correct
6 Correct 325 ms 55424 KB Output is correct
7 Correct 318 ms 55572 KB Output is correct
8 Correct 442 ms 48856 KB Output is correct
9 Correct 521 ms 48736 KB Output is correct