委員長の魔女 (AOJ 2317)

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2317

問題

略

解法

紐をまとめて切るだけ。

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <assert.h>
#include <vector>
#include <queue>

using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
static const double EPS = 1e-9;
static const double PI = acos(-1.0);

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, s, n) for (int i = (s); i < (int)(n); i++)
#define FOREQ(i, s, n) for (int i = (s); i <= (int)(n); i++)
#define FORIT(it, c) for (__typeof((c).begin())it = (c).begin(); it != (c).end(); it++)
#define MEMSET(v, h) memset((v), h, sizeof(v))

struct Interval {
  ll start;
  ll end;
  int head;
  int endHead;
  int cut;
  Interval() {;}
  Interval(ll start, ll end, int head) : start(start), end(end), head(head) {;}
  bool operator<(const Interval &rhs) const {
    return start < rhs.start;
  }
};

struct EndEvent {
  ll end;
  int head;
  EndEvent() {;}
  EndEvent(ll end, int head) : end(end), head(head) {;}
  bool operator<(const EndEvent &rhs) const {
    return end > rhs.end;
  }
};

ll n, q;
Interval snake[100010];
ll query[100010];
ll snakeCount[2];

int main() {
  while (scanf("%lld %lld", &n, &q) > 0) {
    REP(i, n) {
      ll s, e, h;
      ll v = scanf("%lld %lld", &s, &e);
      assert(v == 2);
      if (s < e) { h = 0; }
      else { h = 1; swap(s, e); }
      snake[i] = Interval(s, e, h);
    }
    sort(snake, snake + n);
    snake[n] = Interval(1LL << 60, 1LL << 60, 0);
    REP(i, q) {
      ll v = scanf("%lld", &query[i]);
      assert(v == 1);
    }
    sort(query, query + q);
    query[q++] = 1LL << 60;
    REP(i, n) {
      ll *left = upper_bound(query, query + q, snake[i].start);
      ll *right = lower_bound(query, query + q, snake[i].end);
      snake[i].cut = right - left;
      if (snake[i].cut % 2 == 0) {
        snake[i].head = 0;
        snake[i].endHead = 0;
      } else {
        snake[i].endHead = snake[i].head ^ 1;
      }
    }
    priority_queue<EndEvent> endQue;
    ll ans = 0;
    ll prev = -10000000000000LL;
    int cutIndex = 0;
    int snakeIndex = 0;
    while (!endQue.empty() || cutIndex < q) {
      if (endQue.empty() || query[cutIndex] < endQue.top().end) {
        ll x = query[cutIndex];
        ans += snakeCount[0] * (x - prev);
        swap(snakeCount[0], snakeCount[1]);

        while (snake[snakeIndex].start < x) {
          ll start = snake[snakeIndex].start;
          ll end = snake[snakeIndex].end;
          int head = snake[snakeIndex].head;
          int endHead = snake[snakeIndex].endHead;
          int cut = snake[snakeIndex].cut;
          if (cut == 0) {
            ans += end - start;
          } else {
            if (head == 0) {
              ans += x - start;
            }
            snakeCount[head ^ 1]++;
            endQue.push(EndEvent(end, endHead));
          }
          snakeIndex++;
        }
        prev = x;
        cutIndex++;
      } else {
        ll end = endQue.top().end;
        int head = endQue.top().head;
        endQue.pop();
        snakeCount[head]--;
        assert(snakeCount[head] >= 0);
        if (head == 0) {
          ans += end - prev;
        }
      }
    }
    printf("%lld\n", ans);
  }
}