제출 #39954

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
39954		funcsr	운세 보기 2 (JOI14_fortune_telling2)	C++14	0 / 100	190 ms	43540 KiB

fortune_telling2

#include <iostream>
#include <queue>
#include <cassert>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(x) x.begin(), x.end()
#define uniq(x) x.erase(unique(all(x)), x.end())
#define index(x, y) (int)(lower_bound(all(x), y) - x.begin())
#define pb push_back
#define _1 first
#define _2 second
#define INF 1145141919
#define MAX_N (1<<19)
struct RMQ {
  int seg[MAX_N*2-1] = {};
  void update(int k, int v) {
    k += MAX_N-1;
    if (v <= seg[k]) return;
    seg[k] = v;
    while (k) {
      k = (k-1) / 2;
      seg[k] = max(seg[k*2+1], seg[k*2+2]);
    }
  }
  int query(int a, int b, int k=0, int l=0, int r=MAX_N) {
    if (b <= l || r <= a) return 0;
    if (a <= l && r <= b) return seg[k];
    return max(query(a, b, k*2+1, l, (l+r)/2), query(a, b, k*2+2, (l+r)/2, r));
  }
};
struct SegTree {
  int seg[MAX_N*2-1] = {};
  void flip(int k) {
    k += MAX_N-1;
    seg[k] ^= 1;
    while (k) {
      k = (k-1) / 2;
      seg[k] ^= 1;
    }
  }
  int query(int a, int b, int k=0, int l=0, int r=MAX_N) {
    if (b <= l || r <= a) return 0;
    if (a <= l && r <= b) return seg[k];
    return query(a, b, k*2+1, l, (l+r)/2) ^ query(a, b, k*2+2, (l+r)/2, r);
  }
};

int N, K;
int A[200000], B[200000];
int flip[200000];
int T[200000];
vector<int> G[600000], G2[600000];
RMQ rmq;
SegTree seg;

int main() {
  cin >> N >> K;
  vector<int> xs;
  rep(i, N) {
    cin >> A[i] >> B[i];
    xs.pb(A[i]), xs.pb(B[i]);
    if (A[i] > B[i]) {
      swap(A[i], B[i]);
      flip[i] ^= 1;
    }
  }
  rep(i, K) cin >> T[i];
  sort(all(xs)); uniq(xs);
  rep(i, N) A[i] = index(xs, A[i]), B[i] = index(xs, B[i]), G[B[i]].pb(i);
  rep(i, K) T[i] = index(xs, T[i]), G2[T[i]].pb(i);
  rep(i, K) rmq.update(T[i], i+1);
  for (int p=(int)xs.size()-1; p>=0; p--) {
    for (int x : G2[p]) seg.flip(x);
    for (int x : G[p]) {
      int t = rmq.query(A[x], B[x])-1;
      if (t != -1) flip[x] = 1;
      flip[x] ^= seg.query(t+1, MAX_N);
    }
  }
  long long s = 0;
  rep(i, N) {
    if (flip[i]) s += xs[B[i]];
    else s += xs[A[i]];
  }
  cout << s << "\n";
  return 0;
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 31
• Subtask 3: 0 / 65