Submission #52240

#	Time	Username	Problem	Language	Result	Execution time	Memory
52240		gs14004	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	1409 ms	97644 KiB

fortune_telling2

#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 (stderr)

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 / 4
• Subtask 2: 31 / 31
• Subtask 3: 65 / 65