Submission #426518

#	Time	Username	Problem	Language	Result	Execution time	Memory
426518		xiaowuc1	수족관 1 (KOI13_aqua1)	C++17	100 / 100	14 ms	13076 KiB

aqua1

#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;

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 solve() {
  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));
  map<pii, int> segmenttoidx;
  for(auto seg: horizontalsegs) {
    auto it = sections.lb({seg[1], -1, -1, -1});
    assert(it != sections.end());
    auto section = *it;
    sections.erase(section);
    segmenttoidx[{seg[1], seg[2]}] = section[3];
    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++});
    }
  }
  assert(numnodes <= SZ);
  int k;
  cin >> k;
  ll ret = 0;
  {
    for(int i = 0; i < n; i++) {
      int j = i+1;
      ret += (vertices[i].f * (ll)vertices[j].s) - (vertices[i].s * (ll)vertices[j].f);
    }
    ret = abs(ret)/2;
  }
  while(k--) {
    int lx, ly, rx, ry;
    cin >> lx >> ly >> rx >> ry;
    pii key = {lx, rx};
    int v = segmenttoidx[key];
    while(!consumed[v]) {
      ret -= 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: 23 / 23
• Subtask 2: 19 / 19
• Subtask 3: 22 / 22
• Subtask 4: 36 / 36