Submission #466637

#	Time	Username	Problem	Language	Result	Execution time	Memory
466637		ivan_tudor	The Potion of Great Power (CEOI20_potion)	C++14	38 / 100	3067 ms	19148 KiB

potion

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
const int BUCKET_SIZE = 50;
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];
struct sethelper{
  vector<int> act;
  int time;
  int pos;
};
vector<vector<int>> precalc[N];
bool mark[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;
    for(int j = 0; j < changes[i].size(); j++){
      int val = changes[i][j].x;
      mark[val]^= true;
      if(mark[val] == false)
        act.erase(val);
      else
        act.insert(val);
      cnt++;
      if(cnt == BUCKET_SIZE){
        precalc[i].push_back(vector<int>());
        for(auto x: act)
          precalc[i].back().push_back(x);
        cnt = 0;
      }
    }
    for(auto x:act)
      mark[x] = false;
    act.clear();
  }
}
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;
  }
  int lastcheck = pas / BUCKET_SIZE - 1;
  if(lastcheck >= 0){
    for(auto a: precalc[x][lastcheck]){
      mark[a] ^= true;
      act.insert(a);
    }
  }
  for(int i = (lastcheck + 1) * BUCKET_SIZE; i <= pas; i++){
    int val = changes[x][i].x;
    mark[val]^= true;
    if(mark[val] == false)
      act.erase(val);
    else
      act.insert(val);
  }
  for(auto x:act){
    ans.push_back(h[x]);
    mark[x] = false;
  }
  act.clear();
  sort(ans.begin(), ans.end());
}
int question(int x, int y, int v) {
  vector<int> a, b;
  get_list(x, v, a);
  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:39:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<otherhelper>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for(int j = 0; j < changes[i].size(); j++){
      |                    ~~^~~~~~~~~~~~~~~~~~~
potion.cpp: In function 'void get_list(int, int, std::vector<int>&)':
potion.cpp:62:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<otherhelper>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     if(pas + p2 < changes[x].size() && changes[x][pas + p2].time < v)
      |        ~~~~~~~~~^~~~~~~~~~~~~~~~~~~
potion.cpp:65:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<otherhelper>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |   if(!(pas < changes[x].size() && changes[x][pas].time < v)){
      |        ~~~~^~~~~~~~~~~~~~~~~~~
potion.cpp: In function 'int question(int, int, int)':
potion.cpp:95:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |   for(int i = 0, j = 0; i < a.size() && j < b.size();){
      |                         ~~^~~~~~~~~~
potion.cpp:95:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |   for(int i = 0, j = 0; i < a.size() && j < b.size();){
      |                                         ~~^~~~~~~~~~

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