Submission #56743

#	Time	Username	Problem	Language	Result	Execution time	Memory
56743		ruhanhabib39	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	714 ms	19528 KiB

fortune_telling2

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2e5;

int N, K;
pair<int,int> A[MAXN + 10];
int bit[MAXN + 10];
int X[MAXN + 10];

void inc(int i) {
   for(i++; i <= K; i += i & (-i)) {
      bit[i] ^= 1;
   }
}

int sum(int r) {
   int res = 0;
   for(r++; r > 0; r -= r & (-r)) {
      res ^= bit[r];
   }
   return res;
}

int sum(int l, int r) {
   return sum(r) ^ sum(l);
}

int mx[4 * MAXN + 10];

void mx_upd(int cn, int b, int e, int i, int x) {

   if(i < b || i > e) return;
   if(b == e) {
      mx[cn] = x;
      return;
   }
   int m = (b + e) / 2;
   mx_upd(cn << 1, b, m, i, x);
   mx_upd(cn << 1 | 1, m+1, e, i, x);
   mx[cn] = max(mx[cn << 1], mx[cn << 1 | 1]);
}

int nxt(int cn, int b, int e, int x) {
   if(mx[cn] < x) return -1;
   if(b == e) return b;
   int m = (b + e) / 2;
   if(mx[cn<<1|1] < x) return nxt(cn << 1, b, m, x);
   return nxt(cn << 1 | 1, m+1, e, x);
}

int solve(int i) {
   int l = nxt(1, 0, K-1, min(A[i].first, A[i].second));
   
   int p = sum(l, K-1);
   if(l != -1) {
      if(A[i].first < A[i].second) swap(A[i].first, A[i].second);
   }
   int res = p ? A[i].second : A[i].first;
   return res;
}

int main() {
   scanf("%d%d", &N, &K);
   for(int i = 0; i < N; i++) {
      scanf("%d%d", &A[i].first, &A[i].second);
   }
   for(int i = 0; i < K; i++) {
      scanf("%d", &X[i]);
   }
   sort(A, A + N,
      [](pair<int,int> a, pair<int,int> b) {
         int ma = max(a.first, a.second);
         int mb = max(b.first, b.second);
         if(ma != mb) return ma < mb;
         return a < b;
      });

   reverse(A, A + N);

   memset(mx, -1, sizeof mx);

   for(int i = 0; i < K; i++) {
      if(X[i] < max(A[0].first, A[0].second)) { // S
         mx_upd(1, 0, K-1, i, X[i]);
      }
   }

   set<pair<long long,int>> st;
   for(int i = 0; i < K; i++) {
      st.emplace(X[i], i);
   }
   while(st.size() && st.rbegin()->first >= max(A[0].first, A[0].second)) {
      int j = st.rbegin()->second;
      inc(j);
      mx_upd(1, 0, K-1, j, -1);
      st.erase(*st.rbegin());
   }

   long long res = solve(0);
   for(int i = 1; i < N; i++) {
      while(st.size() && st.rbegin()->first >= max(A[i].first, A[i].second)) {
         int j = st.rbegin()->second;
         mx_upd(1, 0, K-1, j, -1);
         inc(j);
         st.erase(*st.rbegin());
      }
      res += solve(i);
   }
   printf("%lld\n", res);
}

Compilation message (stderr)

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:64:9: 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:66:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d%d", &A[i].first, &A[i].second);
       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:69:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d", &X[i]);
       ~~~~~^~~~~~~~~~~~~

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