oj.uz

Submission #52240

# Submission time Handle Problem Language Result Execution time Memory
52240 2018-06-25T05:50:45 Z gs14004 Fortune Telling 2 (JOI14_fortune_telling2) C++17
100 / 100
 1409 ms 97644 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;
}

Compilation message

fortune_telling2.cpp: In function 'void check(int, int, int, int, int)':
fortune_telling2.cpp:26:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < S[x].size(); ++i) {
                   ~~^~~~~~~~~~~~~
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:61:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &N, &K);
   ~~~~~^~~~~~~~~~~~~~~~
fortune_telling2.cpp:65:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &A[i], &B[i]);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:70:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &T[j]);
     ~~~~~^~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 56824 KB Output is correct
2 Correct 50 ms 56924 KB Output is correct
3 Correct 50 ms 57032 KB Output is correct
4 Correct 51 ms 57108 KB Output is correct
5 Correct 51 ms 57108 KB Output is correct
6 Correct 52 ms 57108 KB Output is correct
7 Correct 52 ms 57108 KB Output is correct
8 Correct 55 ms 57108 KB Output is correct
9 Correct 50 ms 57108 KB Output is correct
10 Correct 53 ms 57108 KB Output is correct
11 Correct 50 ms 57108 KB Output is correct
12 Correct 51 ms 57108 KB Output is correct
13 Correct 50 ms 57108 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 56824 KB Output is correct
2 Correct 50 ms 56924 KB Output is correct
3 Correct 50 ms 57032 KB Output is correct
4 Correct 51 ms 57108 KB Output is correct
5 Correct 51 ms 57108 KB Output is correct
6 Correct 52 ms 57108 KB Output is correct
7 Correct 52 ms 57108 KB Output is correct
8 Correct 55 ms 57108 KB Output is correct
9 Correct 50 ms 57108 KB Output is correct
10 Correct 53 ms 57108 KB Output is correct
11 Correct 50 ms 57108 KB Output is correct
12 Correct 51 ms 57108 KB Output is correct
13 Correct 50 ms 57108 KB Output is correct
14 Correct 80 ms 58812 KB Output is correct
15 Correct 117 ms 60760 KB Output is correct
16 Correct 161 ms 62780 KB Output is correct
17 Correct 203 ms 64740 KB Output is correct
18 Correct 200 ms 64748 KB Output is correct
19 Correct 202 ms 64748 KB Output is correct
20 Correct 201 ms 64748 KB Output is correct
21 Correct 190 ms 64748 KB Output is correct
22 Correct 134 ms 64748 KB Output is correct
23 Correct 132 ms 64748 KB Output is correct
24 Correct 124 ms 64748 KB Output is correct
25 Correct 129 ms 64748 KB Output is correct
26 Correct 135 ms 64748 KB Output is correct
27 Correct 150 ms 64748 KB Output is correct
28 Correct 146 ms 64748 KB Output is correct
29 Correct 137 ms 64748 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 56824 KB Output is correct
2 Correct 50 ms 56924 KB Output is correct
3 Correct 50 ms 57032 KB Output is correct
4 Correct 51 ms 57108 KB Output is correct
5 Correct 51 ms 57108 KB Output is correct
6 Correct 52 ms 57108 KB Output is correct
7 Correct 52 ms 57108 KB Output is correct
8 Correct 55 ms 57108 KB Output is correct
9 Correct 50 ms 57108 KB Output is correct
10 Correct 53 ms 57108 KB Output is correct
11 Correct 50 ms 57108 KB Output is correct
12 Correct 51 ms 57108 KB Output is correct
13 Correct 50 ms 57108 KB Output is correct
14 Correct 80 ms 58812 KB Output is correct
15 Correct 117 ms 60760 KB Output is correct
16 Correct 161 ms 62780 KB Output is correct
17 Correct 203 ms 64740 KB Output is correct
18 Correct 200 ms 64748 KB Output is correct
19 Correct 202 ms 64748 KB Output is correct
20 Correct 201 ms 64748 KB Output is correct
21 Correct 190 ms 64748 KB Output is correct
22 Correct 134 ms 64748 KB Output is correct
23 Correct 132 ms 64748 KB Output is correct
24 Correct 124 ms 64748 KB Output is correct
25 Correct 129 ms 64748 KB Output is correct
26 Correct 135 ms 64748 KB Output is correct
27 Correct 150 ms 64748 KB Output is correct
28 Correct 146 ms 64748 KB Output is correct
29 Correct 137 ms 64748 KB Output is correct
30 Correct 229 ms 64748 KB Output is correct
31 Correct 428 ms 69820 KB Output is correct
32 Correct 707 ms 79132 KB Output is correct
33 Correct 1277 ms 97512 KB Output is correct
34 Correct 190 ms 97512 KB Output is correct
35 Correct 1231 ms 97512 KB Output is correct
36 Correct 1409 ms 97616 KB Output is correct
37 Correct 1302 ms 97644 KB Output is correct
38 Correct 1233 ms 97644 KB Output is correct
39 Correct 1366 ms 97644 KB Output is correct
40 Correct 1107 ms 97644 KB Output is correct
41 Correct 1265 ms 97644 KB Output is correct
42 Correct 1292 ms 97644 KB Output is correct
43 Correct 528 ms 97644 KB Output is correct
44 Correct 521 ms 97644 KB Output is correct
45 Correct 529 ms 97644 KB Output is correct
46 Correct 580 ms 97644 KB Output is correct
47 Correct 444 ms 97644 KB Output is correct
48 Correct 713 ms 97644 KB Output is correct
49 Correct 706 ms 97644 KB Output is correct