oj.uz

Submission #39954

# Submission time Handle Problem Language Result Execution time Memory
39954 2018-01-25T02:37:10 Z funcsr Fortune Telling 2 (JOI14_fortune_telling2) C++14
0 / 100
 190 ms 43540 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 41484 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 41 ms 42220 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Incorrect 190 ms 43540 KB Output isn't correct
2 Halted 0 ms 0 KB -