Submission #466627

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

potion

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
const int BUCKET_SIZE = 25;
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 = 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++){
    unordered_set<int> act;
    int cnt = 0;
    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);
      cnt++;
      if(cnt == BUCKET_SIZE){
        precalc[i].push_back({act, changes[i][j].time, j});
        cnt = 0;
      }
    }
  }
}
void get_list(int x, int v, vector<int> &ans){
  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:37:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<otherhelper>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for(int j = 0; j < changes[i].size(); j++){
      |                    ~~^~~~~~~~~~~~~~~~~~~
potion.cpp: In function 'void get_list(int, int, std::vector<int>&)':
potion.cpp:55:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<sethelper>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     if(pas + p2 < precalc[x].size() && precalc[x][pas + p2].time < v)
      |        ~~~~~~~~~^~~~~~~~~~~~~~~~~~~
potion.cpp:59:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<sethelper>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |   if(pas < precalc[x].size() && precalc[x][pas].time < v){
      |      ~~~~^~~~~~~~~~~~~~~~~~~
potion.cpp:63:7: warning: statement has no effect [-Wunused-value]
   63 |   for(pos; pos < changes[x].size();pos++){
      |       ^~~
potion.cpp:63:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<otherhelper>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |   for(pos; pos < changes[x].size();pos++){
      |            ~~~~^~~~~~~~~~~~~~~~~~~
potion.cpp: In function 'int question(int, int, int)':
potion.cpp:82:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |   for(int i = 0, j = 0; i < a.size() && j < b.size();){
      |                         ~~^~~~~~~~~~
potion.cpp:82:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |   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