oj.uz

답안 #799279

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
799279 2023-07-31T11:39:02 Z NeroZein The Potion of Great Power (CEOI20_potion) C++17
38 / 100
 745 ms 262144 KB 
#include "bits/stdc++.h"

using namespace std;

const int C = 1;
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];
  }
};

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[b[day]]); 
    }
  }
}

int getDis (vector<int> h1, vector<int> h2) {//n + m
  if (h1.empty() || h2.empty()) {
    return INF; 
  }
  assert(is_sorted(h1.begin(), h1.end()));
  assert(is_sorted(h2.begin(), h2.end()));
  int ret = INF; 
  int i = 0, j = 0;
  int n = h1.size(), m = h2.size();
  while (i < n || j < m) {
    if (i < n && (j == m || h1[i] < h2[j])) {
      if (j < m) {
        ret = min(ret, h2[j] - h1[i]);        
      }
      i++;
    } else {
      if (i < n) {
        ret = min(ret, h1[i] - h2[j]);         
      }
      j++; 
    }
  }
  return ret;
} 

int question (int x, int y, int v) {
  if (x == y) return 0; 
  vector<int> vv[2] = {};
  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]); 
    }
    for (auto i : se[rep]) vv[rep].push_back(h[i]);
    swap(x, y);
  }
  return getDis(vv[0], vv[1]); 
}

Subtask #1
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 9680 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 10192 KB Output is correct
2 Correct 5 ms 10192 KB Output is correct
3 Correct 6 ms 10192 KB Output is correct
4 Correct 24 ms 20248 KB Output is correct

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 615 ms 128496 KB Output is correct
2 Correct 631 ms 128664 KB Output is correct
3 Correct 679 ms 222376 KB Output is correct
4 Runtime error 405 ms 262144 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 388 ms 76456 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #5
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 57 ms 15184 KB Output is correct
2 Correct 92 ms 20532 KB Output is correct
3 Correct 147 ms 21140 KB Output is correct
4 Correct 721 ms 76104 KB Output is correct
5 Correct 745 ms 59992 KB Output is correct
6 Correct 128 ms 22480 KB Output is correct
7 Correct 576 ms 66264 KB Output is correct

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 9680 KB Output is correct
2 Correct 6 ms 10192 KB Output is correct
3 Correct 5 ms 10192 KB Output is correct
4 Correct 6 ms 10192 KB Output is correct
5 Correct 24 ms 20248 KB Output is correct
6 Correct 615 ms 128496 KB Output is correct
7 Correct 631 ms 128664 KB Output is correct
8 Correct 679 ms 222376 KB Output is correct
9 Runtime error 405 ms 262144 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -