제출 #1246999

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1246999		repmann	운세 보기 2 (JOI14_fortune_telling2)	C++20	100 / 100	251 ms	35132 KiB

fortune_telling2

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int N, K, Q, glob;
int A[200096], B[200096], T[200096], D[600096];
ll ST[2400096];
vector <int> QR[200096];
inline void Setup()
{
  K = 1;
  while(K < glob) K <<= 1;
  for(int i = 1; i <= Q; i++) ST[T[i] + K - 1] = i;
  for(int i = K; i; i--) ST[i] = max(ST[i << 1], ST[(i << 1) + 1]);
  return;
}
inline void Update(int i)
{
  i += K - 1;
  while(i) {ST[i]++; i >>= 1;}
  return;
}
inline int GetMax(int L, int R, int LC = 1, int RC = K, int i = 1)
{
  if((L > RC) || (LC > R)) return 0;
  if((L <= LC) && (RC <= R)) return ST[i];
  int S = (LC + RC) >> 1;
  return max(GetMax(L, R, LC, S, i << 1), GetMax(L, R, S + 1, RC, (i << 1) + 1));
}
inline int GetSum(int L, int R, int LC = 1, int RC = K, int i = 1)
{
  if((L > RC) || (LC > R)) return 0;
  if((L <= LC) && (RC <= R)) return ST[i];
  int S = (LC + RC) >> 1;
  return GetSum(L, R, LC, S, i << 1) + GetSum(L, R, S + 1, RC, (i << 1) + 1);
}
int main()
{
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> N >> Q;
  for(int i = 1; i <= N; i++) cin >> A[i] >> B[i];
  for(int i = 1; i <= Q; i++) cin >> T[i];
  vector <pair <int, int>> V;
  for(int i = 1; i <= N; i++) V.push_back({A[i], i});
  for(int i = 1; i <= N; i++) V.push_back({B[i], i + N});
  for(int i = 1; i <= Q; i++) V.push_back({T[i], i + N + N});
  sort(V.begin(), V.end());
  glob = 1;
  for(int i = 0; i < V.size(); i++)
  {
    if(i) glob += V[i - 1] != V[i];
    D[glob] = V[i].first;
    if(V[i].second <= N) A[V[i].second] = glob;
    else if(V[i].second <= (N << 1)) B[V[i].second - N] = glob;
    else T[V[i].second - (N << 1)] = glob;
  }
  Setup();
  for(int i = 1, j; i <= N; i++)
  {
    j = GetMax(min(A[i], B[i]), max(A[i], B[i]));
    QR[j].push_back(i);
  }
  memset(ST, 0, sizeof(ST));
  ll sol = 0;
  for(int i = Q, j; i >= 1; i--)
  {
    for(int x : QR[i])
    {
      j = GetSum(max(A[x], B[x]), glob);
      if(j & 1) sol += D[min(A[x], B[x])];
      else sol += D[max(A[x], B[x])];
    }
    Update(T[i]);
  }
  for(int x : QR[0])
  {
    int j = GetSum(max(A[x], B[x]), glob);
    if(j & 1) sol += D[B[x]];
    else sol += D[A[x]];
  }
  cout << sol << '\n';

  return 0;
}

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