Submission #75833

#	Time	Username	Problem	Language	Result	Execution time	Memory
75833		MiricaMatei	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	100 / 100	1192 ms	142020 KiB

fortune_telling2

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 200000;
const int MAX_M = 200000;

int a[MAX_N + 5], b[MAX_N + 5];
int q[MAX_N + 5];
int srt[MAX_N + 5], srtq[MAX_M + 5];
int nor[2 * MAX_N + MAX_M + 5];
int aib[2 * MAX_N + MAX_M + 5];
int last[MAX_N + 5];

map<int, int>mp;

bool cmp1(int x, int y) {
  return min(a[x], b[x]) > min(a[y], b[y]);
}

bool cmp2(int x, int y) {
  return q[x] > q[y];
}

bool cmp3(int x, int y) {
  return last[x] > last[y];
}

void update(int poz, int val, int n) {
  assert(poz != 0);
  for (; poz <= n; poz += (poz & -poz))
    aib[poz] = max(aib[poz], val);
}

int query(int poz) {
  int ans = 0;
  for (; poz; poz -= (poz & -poz))
    ans = max(ans, aib[poz]);
  return ans;
}

void update1(int poz, int val, int n) {
  assert(poz != 0);
  for (; poz <= n; poz += (poz & -poz))
    aib[poz]++;
}

int query1(int poz) {
  int ans = 0;
  for (; poz; poz -= (poz & -poz))
    ans += aib[poz];
  return ans;
}

int main() {

  int n, m, k = 0;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; ++i) {
    scanf("%d%d", &a[i], &b[i]);
    nor[++k] = a[i];
    nor[++k] = b[i];
    srt[i] = i;
  }
  for (int i = 1; i <= m; ++i) {
    scanf("%d", &q[i]);
    nor[++k] = q[i];
    srtq[i] = i;
  }

  sort(nor + 1, nor + k + 1);
  int x = 0;
  for (int i = 1; i <= k;) {
    x++;
    int aux = nor[i];
    while (i <= k && nor[i] == aux)
      ++i;
    mp[aux] = x;
  }

  sort(srt + 1, srt + n + 1, cmp1);
  sort(srtq + 1, srtq + m + 1, cmp2);

  for (int i = 1, j = 1; i <= n && j <= m;) {
    while (j <= m && q[srtq[j]] >= min(a[srt[i]], b[srt[i]])) {
      update(mp[q[srtq[j]]], srtq[j], k);
      j++;
    }
    while (i <= n && min(a[srt[i]], b[srt[i]]) > q[srtq[j]]) {
      last[srt[i]] = query(mp[max(a[srt[i]], b[srt[i]])] - 1);
      i++;
    }
  }

  //for (int i = 1; i <= n; ++i)
    //printf("%d %d\n", i, last[i]);
  //return 0;

  sort(srt + 1, srt + n + 1, cmp3);
  memset(aib, 0, sizeof(aib));

  long long ans = 0;
  int i = 1;
  while (i <= n && last[srt[i]] == m)
    ans += max(a[srt[i]], b[srt[i]]), i++;
  for (int j = m; i <= n && j >= 1; --j) {
    update1(mp[q[j]], 1, k);
    while (i <= n && last[srt[i]] + 1 == j) {
      int aux = query1(k) - query1(mp[max(a[srt[i]], b[srt[i]])] - 1);
      if (last[srt[i]] == 0) {
        if (aux % 2 == 1)
          ans += b[srt[i]];
        else
          ans += a[srt[i]];
      } else {
        if (aux % 2 == 1) {
          ans += min(a[srt[i]], b[srt[i]]);
        }
        else {
          ans += max(a[srt[i]], b[srt[i]]);
        }
      }
      i++;
    }
  }

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

  return 0;
}

Compilation message (stderr)

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:58:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &n, &m);
   ~~~~~^~~~~~~~~~~~~~~~
fortune_telling2.cpp:60: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:66:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &q[i]);
     ~~~~~^~~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 31 / 31
• Subtask 3: 65 / 65