Submission #466639

#	Time	Username	Problem	Language	Result	Execution time	Memory
466639		ivan_tudor	The Potion of Great Power (CEOI20_potion)	C++14	100 / 100	2535 ms	30552 KiB

potion

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int BUCKET_SIZE[N];
int h[N];
int n, d;
int lg2[2*N];
void init(int N, int D, int H[]) {
  d = D;
  n = N;
  for(int i = 0; i < N; i++){
    h[i] = H[i];
  }
}
struct otherhelper{
  int x;
  int time;
};
vector <otherhelper> changes[N];
vector<vector<int>> precalc[N];
set<int> act;
void curseChanges(int U, int A[], int B[]) {
  lg2[1] = 0;
  for(int i = 2; i < N; i++)
    lg2[i] = 1 + lg2[i/2];
  for(int i = 0; i < U; i++){
    changes[A[i]].push_back({B[i], i});
    changes[B[i]].push_back({A[i], i});
  }
  for(int i = 0; i < n; i++){

    int cnt = 0;
    BUCKET_SIZE[i] =sqrt(changes[i].size());
    if(BUCKET_SIZE[i] == 0)
      BUCKET_SIZE[i] = 1;
    for(int j = 0; j < changes[i].size(); j++){
      int val = changes[i][j].x;
      if(act.count(val) == true)
        act.erase(val);
      else
        act.insert(val);
      cnt++;
      if(cnt == BUCKET_SIZE[i]){
        precalc[i].push_back(vector<int>(act.size()));
        int nr = 0;
        for(auto x: act)
          precalc[i].back()[nr++] = (x);
        cnt = 0;
      }
    }
    act.clear();
  }
}
bitset<100005> mark;
void get_list(int x, int v, vector<int> &ans){
  int pas = 0;
  for(int p2 = 1<<(lg2[changes[x].size()] + 1); p2 > 0; p2/=2){
    if(pas + p2 < changes[x].size() && changes[x][pas + p2].time < v)
      pas += p2;
  }
  if(!(pas < changes[x].size() && changes[x][pas].time < v)){
    return;
  }
  mark.reset();
  int lastcheck = pas / BUCKET_SIZE[x] - 1;
  if(lastcheck >= 0){
    for(auto a: precalc[x][lastcheck]){
      mark[a] = true;
    }
  }
  for(int i = (lastcheck + 1) * BUCKET_SIZE[x]; i <= pas; i++){
    int val = changes[x][i].x;
    mark[val] = mark[val] ^  1;
  }
  if(lastcheck >= 0){
    for(auto a: precalc[x][lastcheck]){
      if(mark[a] == true){
        ans.push_back(h[a]);
        mark[a] = false;
      }
    }
  }
  for(int i = (lastcheck + 1) * BUCKET_SIZE[x]; i <= pas; i++){
    int val = changes[x][i].x;
    if(mark[val] == true){
      ans.push_back(h[val]);
      mark[val] = false;
    }

  }
  for(auto x:act){
    ans.push_back(h[x]);
    mark[x] = false;
  }
  act.clear();
  sort(ans.begin(), ans.end());
}
vector<int> a, b;
int question(int x, int y, int v) {
  a.clear();
  get_list(x, v, a);
  b.clear();
  get_list(y, v, b);
  int ans = 1e9;
  for(int i = 0, j = 0; i < a.size() && j < b.size();){
    if(a[i] < b[j]){
      ans = min(ans, b[j] - a[i]);
      i++;
    }
    else{
      ans = min(ans, a[i] - b[j]);
      j++;
    }
  }
  return ans;
}

Compilation message (stderr)

potion.cpp: In function 'void curseChanges(int, int*, int*)':
potion.cpp:36:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<otherhelper>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for(int j = 0; j < changes[i].size(); j++){
      |                    ~~^~~~~~~~~~~~~~~~~~~
potion.cpp: In function 'void get_list(int, int, std::vector<int>&)':
potion.cpp:58:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<otherhelper>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     if(pas + p2 < changes[x].size() && changes[x][pas + p2].time < v)
      |        ~~~~~~~~~^~~~~~~~~~~~~~~~~~~
potion.cpp:61:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<otherhelper>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |   if(!(pas < changes[x].size() && changes[x][pas].time < v)){
      |        ~~~~^~~~~~~~~~~~~~~~~~~
potion.cpp: In function 'int question(int, int, int)':
potion.cpp:105:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |   for(int i = 0, j = 0; i < a.size() && j < b.size();){
      |                         ~~^~~~~~~~~~
potion.cpp:105:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |   for(int i = 0, j = 0; i < a.size() && j < b.size();){
      |                                         ~~^~~~~~~~~~

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