제출 #841707

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
841707		obokaman	Event Hopping (BOI22_events)	C++17	0 / 100	75 ms	13224 KiB

events

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef pair<int,int> PII;

vector<int> psort;
vector<PII> v;
vector<int> p;
int N, Q;

// [x,y): position in psort
// [a,b): positions in p
void merge(int to, int from1, int to1, int from2, int to2) {
  while (1) {
    if (from1 != to1 && from2 != to2) {
      if (psort[from1] <= psort[from2]) {
        psort[to++] = psort[from1++];
      } else {
        psort[to++] = psort[from2++];
      }
    } else if (from1 != to1) {
      psort[to++] = psort[from1++];
    } else if (from2 != to2) {
      psort[to++] = psort[from2++];
    } else {
      break;
    }
  }
}

void setup(int x, int y, int a, int b) {
  // solve [a, b)
  //  cout << "Setup: [" << x << "," << y << "): merge [" << a << "," << b << ")" << endl; 
  if (a+1==b) {
    //    cout << "psort[" << x << "]=v[p[" << a << "]].second=" << v[p[a]].second << endl;
    psort[x] = v[p[a]].second;
  } else {
    setup(x + N, x + N + (y - x) / 2, a, (a+b)/2);
    setup(x + N + (y - x) / 2, y + N, (a+b)/2, b);
    merge(x, x + N, x + N + (y - x) / 2, x + N + (y - x) / 2, y + N);
  }
}


int main() {
  cin >> N >> Q;
  int p2 = 1, pow = 0;
  while (p2 < N) {p2*=2; ++pow;}
  v.resize(p2);
  for (int i=0;i<N;++i) {
    cin >> v[i].first >> v[i].second;
  }
  N = p2;
  p.resize(N);
  for (int i=0;i<N;++i) p[i]=i;
  sort(p.begin(), p.end(), [&](int a, int b) {
    if (v[a].first != v[b].first) {
      return v[a].first < v[b].first;
    } else if (v[a].second != v[b].second) {
      return v[a].second < v[b].second;
    } else {
      return a < b;
    }
  });
  psort.resize(N*(pow+1));
  setup(0, N, 0, N);
  // for (int i=0;i<N*(pow+1);++i) {
  //   cout << psort[i] << " ";
  // }
  // cout << endl;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30