Submission #119430

#	Time	Username	Problem	Language	Result	Execution time	Memory
119430		IOrtroiii	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	35 / 100	92 ms	22940 KiB

fortune_telling2

#include <bits/stdc++.h>

using namespace std;

const int N = 200200;

int n, q;
int x[N], y[N], z[N];
bool sw[N];
bool ft[N];
vector<pair<int, int>> vals;
int rmq[18][N];
vector<pair<int, int>> qs[N];

void mdf(int v) {
   for (; v > 0; v -= v & -v) {
      ft[v] ^= true;
   }
}

bool get(int v) {
   bool ans = false;
   for (; v <= q; v += v & -v) {
      ans ^= ft[v];
   }
   return ans;
}

int get(int l, int r) {
   int LG = __lg(r - l + 1);
   return max(rmq[LG][l], rmq[LG][r - (1 << LG) + 1]);
}

int main() {
   scanf("%d %d", &n, &q);
   for (int i = 1; i <= n; ++i) {
      scanf("%d %d", x + i, y + i);
   }
   for (int i = 1; i <= q; ++i) {
      scanf("%d", z + i);
      vals.emplace_back(z[i], i);
   }
   sort(vals.begin(), vals.end());
   for (int i = 0; i < q; ++i) {
      rmq[0][i + 1] = vals[i].second;
   }
   for (int i = 1; i < 17; ++i) {
      for (int j = 1; j + (1 << i) - 1 <= q; ++j) {
         rmq[i][j] = max(rmq[i - 1][j], rmq[i - 1][j + (1 << i - 1)]);
      }
   }
   for (int i = 1; i <= n; ++i) {
      int l = min(x[i], y[i]), r = max(x[i], y[i]);
      l = lower_bound(vals.begin(), vals.end(), make_pair(l, 0)) - vals.begin() + 1;
      r = lower_bound(vals.begin(), vals.end(), make_pair(r, 0)) - vals.begin();
      int last = 0;
      if (l <= r) {
         last = get(l, r);
         if (x[i] < y[i]) {
            swap(x[i], y[i]);
         }
      }
      qs[r].emplace_back(i, last + 1);
   }
   for (int i = q - 1; i >= 0; --i) {
      mdf(vals[i].second);
      for (auto v : qs[i]) {
         sw[v.first] = get(v.second);
      }
   }
   long long ans = 0;
   for (int i = 1; i <= n; ++i) {
      if (sw[i]) {
         ans += y[i];
      } else {
         ans += x[i];
      }
   }
   printf("%lld\n", ans);
}

Compilation message (stderr)

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:49:64: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
          rmq[i][j] = max(rmq[i - 1][j], rmq[i - 1][j + (1 << i - 1)]);
                                                              ~~^~~
fortune_telling2.cpp:35:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d", &n, &q);
    ~~~~~^~~~~~~~~~~~~~~~~
fortune_telling2.cpp:37:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d %d", x + i, y + i);
       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:40:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d", z + i);
       ~~~~~^~~~~~~~~~~~~

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