oj.uz

Submission #6971

# Submission time Handle Problem Language Result Execution time Memory
6971 2014-07-12T00:29:53 Z model_code Fortune Telling 2 (JOI14_fortune_telling2) C++
100 / 100
 1136 ms 100496 KB 
#include <cstdio>
#include <algorithm>
#include <vector>

#include <iostream>

using namespace std;

const int MAXN = 200050, MAXK = 200050, MAXV = 2 * MAXN + MAXK;
int N, K, M;
int A[MAXN], B[MAXN], T[MAXK], X[MAXV];
pair<int, int> J[MAXN];
vector<int> S[MAXV * 4 + 50];

void insert(int x, int u, int a, int b, int L, int R) {
  if (a == L && b == R) {
    S[x].push_back(u);
    return;
  }
  int m = (L + R) / 2;
  if (a < m) insert(2 * x + 0, u, a, min(b, m), L, m);
  if (b > m) insert(2 * x + 1, u, max(a, m), b, m, R);
}

void check(int x, int j, int t, int L, int R) {
  for (int i = 0; i < S[x].size(); ++i) {
    if (J[S[x][i]].first < 0) {
      J[S[x][i]].first = j;
    }
  }
  S[x].clear();
  if (R - L == 1) {
    return;
  }
  int m = (L + R) / 2;
  if (t < m) check(2 * x + 0, j, t, L, m);
  else       check(2 * x + 1, j, t, m, R);
  return;
}

int F[MAXV];

void update(int x) {
  while (x <= M) {
    ++F[x];
    x += x & -x;
  }
}

int sum(int x) {
  int s = 0;
  while (x > 0) {
    s += F[x];
    x -= x & -x;
  }
  return s;
}


int main() {
  scanf("%d%d", &N, &K);

  int xs = 0;
  for (int i = 0; i < N; ++i) {
    scanf("%d%d", &A[i], &B[i]);
    X[xs++] = A[i];
    X[xs++] = B[i];
  }
  for (int j = 0; j < K; ++j) {
    scanf("%d", &T[j]);
    X[xs++] = T[j];
  }

  sort(X, X + xs);
  M = unique(X, X + xs) - X;

  for (int i = 0; i < N; ++i) {
    A[i] = lower_bound(X, X + M, A[i]) - X;
    B[i] = lower_bound(X, X + M, B[i]) - X;
    J[i] = make_pair(-1, i);
    insert(1, i, min(A[i], B[i]), max(A[i], B[i]), 0, M);
  }
  for (int j = K - 1; j >= 0; --j) {
    T[j] = lower_bound(X, X + M, T[j]) - X;
    check(1, j, T[j], 0, M);
  }

  sort(J, J + N);
  reverse(J, J + N);

  int cur = K - 1, all = 0;
  long long res = 0;
  for (int i = 0; i < N; ++i) {
    while (cur > J[i].first) {
      update(T[cur--] + 1);
      ++all;
    }

    int u = J[i].second;
    int flip = (all - sum(B[u])) % 2;
    int start = cur >= 0 ? (A[u] < B[u] ? 1 : 0) : 0;
    res += X[(start + flip) % 2 ? B[u] : A[u]];
  }

  printf("%lld\n", res);

  return 0;
}

Subtask #1
4.0 / 4.0

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

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 67864 KB Output is correct
2 Correct 72 ms 69336 KB Output is correct
3 Correct 124 ms 70804 KB Output is correct
4 Correct 152 ms 72500 KB Output is correct
5 Correct 164 ms 72516 KB Output is correct
6 Correct 172 ms 72648 KB Output is correct
7 Correct 152 ms 72084 KB Output is correct
8 Correct 152 ms 71680 KB Output is correct
9 Correct 120 ms 72048 KB Output is correct
10 Correct 92 ms 70816 KB Output is correct
11 Correct 100 ms 71028 KB Output is correct
12 Correct 104 ms 71804 KB Output is correct
13 Correct 112 ms 69104 KB Output is correct
14 Correct 116 ms 69180 KB Output is correct
15 Correct 104 ms 70440 KB Output is correct
16 Correct 96 ms 67860 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 68652 KB Output is correct
2 Correct 388 ms 75500 KB Output is correct
3 Correct 600 ms 83532 KB Output is correct
4 Correct 1104 ms 99488 KB Output is correct
5 Correct 144 ms 66540 KB Output is correct
6 Correct 1112 ms 99368 KB Output is correct
7 Correct 1136 ms 99428 KB Output is correct
8 Correct 1132 ms 99460 KB Output is correct
9 Correct 1080 ms 98660 KB Output is correct
10 Correct 1088 ms 96364 KB Output is correct
11 Correct 944 ms 100360 KB Output is correct
12 Correct 1092 ms 97432 KB Output is correct
13 Correct 1092 ms 96036 KB Output is correct
14 Correct 520 ms 100464 KB Output is correct
15 Correct 540 ms 100496 KB Output is correct
16 Correct 556 ms 100348 KB Output is correct
17 Correct 564 ms 97116 KB Output is correct
18 Correct 452 ms 82248 KB Output is correct
19 Correct 672 ms 87580 KB Output is correct
20 Correct 652 ms 89388 KB Output is correct