oj.uz

Submission #39955

# Submission time Handle Problem Language Result Execution time Memory
39955 2018-01-25T02:45:58 Z funcsr Fortune Telling 2 (JOI14_fortune_telling2) C++14
100 / 100
 963 ms 66260 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<<20)
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], xs.pb(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) s += xs[flip[i]?B[i]:A[i]];
  cout << s << "\n";
  return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 49676 KB Output is correct
2 Correct 12 ms 49808 KB Output is correct
3 Correct 9 ms 49808 KB Output is correct
4 Correct 11 ms 49808 KB Output is correct
5 Correct 9 ms 49808 KB Output is correct
6 Correct 0 ms 49808 KB Output is correct
7 Correct 5 ms 49808 KB Output is correct
8 Correct 5 ms 49808 KB Output is correct
9 Correct 8 ms 49808 KB Output is correct
10 Correct 7 ms 49808 KB Output is correct
11 Correct 10 ms 49808 KB Output is correct
12 Correct 7 ms 49808 KB Output is correct
13 Correct 3 ms 49808 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 50412 KB Output is correct
2 Correct 82 ms 51200 KB Output is correct
3 Correct 117 ms 52116 KB Output is correct
4 Correct 181 ms 52644 KB Output is correct
5 Correct 155 ms 52644 KB Output is correct
6 Correct 158 ms 52644 KB Output is correct
7 Correct 201 ms 52644 KB Output is correct
8 Correct 179 ms 52644 KB Output is correct
9 Correct 102 ms 52380 KB Output is correct
10 Correct 97 ms 52380 KB Output is correct
11 Correct 114 ms 52248 KB Output is correct
12 Correct 116 ms 52512 KB Output is correct
13 Correct 126 ms 52512 KB Output is correct
14 Correct 173 ms 52644 KB Output is correct
15 Correct 150 ms 52644 KB Output is correct
16 Correct 141 ms 52644 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 328 ms 57248 KB Output is correct
2 Correct 398 ms 59592 KB Output is correct
3 Correct 532 ms 61176 KB Output is correct
4 Correct 853 ms 66260 KB Output is correct
5 Correct 255 ms 56984 KB Output is correct
6 Correct 963 ms 66260 KB Output is correct
7 Correct 893 ms 66260 KB Output is correct
8 Correct 848 ms 66260 KB Output is correct
9 Correct 861 ms 66260 KB Output is correct
10 Correct 909 ms 66260 KB Output is correct
11 Correct 860 ms 66260 KB Output is correct
12 Correct 906 ms 66260 KB Output is correct
13 Correct 850 ms 66260 KB Output is correct
14 Correct 588 ms 66260 KB Output is correct
15 Correct 566 ms 66260 KB Output is correct
16 Correct 582 ms 66260 KB Output is correct
17 Correct 566 ms 64544 KB Output is correct
18 Correct 543 ms 64016 KB Output is correct
19 Correct 744 ms 66260 KB Output is correct
20 Correct 711 ms 66260 KB Output is correct