Submission #799254

#	Time	Username	Problem	Language	Result	Execution time	Memory
799254		NeroZein	The Potion of Great Power (CEOI20_potion)	C++17	17 / 100	333 ms	44624 KiB

potion

#include "bits/stdc++.h"

using namespace std;

const int C = 50;
const int N = 1e5 + 5;
const int U = 2e5 + 5;
const int INF = 1e9; 

int h[N]; 

struct cmp {
  bool operator ()(int i, int j) const {
    return h[i] < h[j];
  }
};

void print (int u, set<int, cmp> se) {
  cout << "U: " << u << '\n';
  cout << "SE: ";
  for (int i : se) cout << i << ' ';
  cout << '\n';
}

int a[U], b[U];
set<int, cmp> cur[N]; 
vector<int> edits[N];
vector<set<int, cmp>> versions[N];


void edit (int v, set<int, cmp>& seU) {
  if (seU.count(v)) {
    seU.erase(v);
  } else {
    seU.insert(v);
  }
}

void init (int N_, int D, int H[]) {
  for (int i = 0; i < N_; ++i) {
    edits[i].push_back(0); 
    versions[i].push_back({});
    h[i] = H[i];
  }
}

void curseChanges (int U_, int A[], int B[]) {
  for (int day = 1; day <= U_; ++day) {
    a[day] = A[day - 1];
    b[day] = B[day - 1];
    edit(b[day], cur[a[day]]);
    edit(a[day], cur[b[day]]); 
    edits[a[day]].push_back(day);
    edits[b[day]].push_back(day);
    if (edits[a[day]].size() % C == 0) {
      versions[a[day]].push_back(cur[a[day]]);
    }
    if (edits[b[day]].size() % C == 0) {
      versions[b[day]].push_back(cur[a[day]]); 
    }
  }
}

int get (const set<int, cmp>& seU, const set<int, cmp>& seV) {
  vector<int> vecU, vecV;
  for (int i : seU) vecU.push_back(i);
  for (int i : seV) vecV.push_back(i);
  int pU = 0, pV = 0;
  int ret = INF;
  while (pU < (int) vecU.size() && pV < (int) vecV.size()) {
    if (h[vecU[pU]] < h[vecV[pV]]) {
      ret = min(ret, h[vecV[pV]] - h[vecU[pU]]);
      pU++;
    } else {
      ret = min(ret, h[vecU[pU]] - h[vecV[pV]]);
      pV++; 
    }
  }
  return ret;
}

int question (int x, int y, int v) {
  vector<set<int, cmp>> se(2); 
  for (int rep = 0; rep < 2; ++rep) {
    int last_edit = upper_bound(edits[x].begin(), edits[x].end(), v) - edits[x].begin() - 1;
    se[rep] = versions[x][last_edit / C];
    int st = last_edit - (last_edit % C) + 1;
    for (; st <= last_edit; ++st) {
      int i = a[edits[x][st]], j = b[edits[x][st]];
      if (i != x) {
        assert(j == x);
        swap(i, j);
      }
      edit(j, se[rep]); 
    }
    swap(x, y);
  }
  return get(se[0], se[1]); 
}

• Subtask 1: 0 / 0
• Subtask 2: 17 / 17
• Subtask 3: 0 / 14
• Subtask 4: 0 / 18
• Subtask 5: 0 / 21
• Subtask 6: 0 / 30