Submission #466615

#	Time	Username	Problem	Language	Result	Execution time	Memory
466615		ivan_tudor	The Potion of Great Power (CEOI20_potion)	C++14	0 / 100	154 ms	19144 KiB

potion

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
const int BUCKET_SIZE = 500;
int h[N];
int n, d;
int lg2[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{
  unordered_set<int> act;
  int time;
  int pos;
};
vector<sethelper> precalc[N];
void curseChanges(int U, int A[], int B[]) {
  lg2[1] = 0;
  for(int i = 1; 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++){
    unordered_set<int> act;
    for(int j = 0; j < changes[i].size(); j++){
      int val = changes[i][j].x;
      if(act.count(val))
        act.erase(val);
      else
        act.insert(val);
      if((1 + j)%BUCKET_SIZE == 0){
        precalc[i].push_back({act, changes[i][j].time, j});
      }
    }
  }
}
void get_list(int x, int v, vector<int> &ans){
  if(precalc[x].size() == 0)
    return;
  unordered_set<int> act;
  int pas = 0;
  for(int p2 = 1<<(lg2[precalc[x].size()] + 1); p2 > 0; p2/=2){
    if(pas + p2 < precalc[x].size() && precalc[x][pas + p2].time < v)
      pas += p2;
  }
  int pos = 0;
  if(pas < precalc[x].size() && precalc[x][pas].time < v){
    act = precalc[x][pas].act;
    pos = precalc[x][pas].pos + 1;
  }
  for(pos; pos < changes[x].size();pos++){
    if(changes[x][pos].time >= v)
      break;
    int val = changes[x][pos].x;
    if(act.count(val))
      act.erase(val);
    else
      act.insert(val);
  }
  for(auto x:act){
    ans.push_back(h[x]);
  }
  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: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:54:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<sethelper>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     if(pas + p2 < precalc[x].size() && precalc[x][pas + p2].time < v)
      |        ~~~~~~~~~^~~~~~~~~~~~~~~~~~~
potion.cpp:58:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<sethelper>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |   if(pas < precalc[x].size() && precalc[x][pas].time < v){
      |      ~~~~^~~~~~~~~~~~~~~~~~~
potion.cpp:62:7: warning: statement has no effect [-Wunused-value]
   62 |   for(pos; pos < changes[x].size();pos++){
      |       ^~~
potion.cpp:62:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<otherhelper>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |   for(pos; pos < changes[x].size();pos++){
      |            ~~~~^~~~~~~~~~~~~~~~~~~
potion.cpp: In function 'int question(int, int, int)':
potion.cpp:81:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |   for(int i = 0, j = 0; i < a.size() && j < b.size();){
      |                         ~~^~~~~~~~~~
potion.cpp:81:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |   for(int i = 0, j = 0; i < a.size() && j < b.size();){
      |                                         ~~^~~~~~~~~~

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