Submission #56702

#	Time	Username	Problem	Language	Result	Execution time	Memory
56702		ruhanhabib39	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	0 / 100	5 ms	504 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];
set<int> spos;

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 solve(int i) {
   int l = *spos.rbegin();
   int p = sum(l, K-1);
   if(l != -1) {
      if(A[i].first < A[i].second) swap(A[i].first, A[i].second);
   }
   if(p) return A[i].second;
   else return A[i].first;
}

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);

   spos.insert(-1);
   for(int i = 0; i < K; i++) {
      if(X[i] < min(A[0].first, A[0].second)) continue;
      if(X[i] < max(A[0].first, A[0].second)) { // S
         spos.insert(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)) {
      inc(st.rbegin()->second);
      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;
         spos.erase(j);
         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:41: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:43: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:46:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d", &X[i]);
       ~~~~~^~~~~~~~~~~~~

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