Submission #1019387

#	Time	Username	Problem	Language	Result	Execution time	Memory
1019387		NintsiChkhaidze	The Potion of Great Power (CEOI20_potion)	C++17	100 / 100	1975 ms	23892 KiB

potion

#include <bits/stdc++.h>
#define pii pair<int,int>
#define pb push_back
#define s second
#define f first 
using namespace std;

const int N = 1e5 + 5;
const int BL = 50;
 
vector <pii> v[N];
int h[N],n;
vector <vector <int>> vec[N];

void init(int N, int D, int H[]) {
	n = N;
	for (int i=1;i<=n;i++)
		h[i] = H[i - 1];
}

void curseChanges(int U, int A[], int B[]) {
	for (int i = 1; i <= U; i++){
	    int a = A[i - 1],b = B[i - 1];
	    a+=1; b+=1;
	    v[a].pb({i,b});
	    v[b].pb({i,a});
  	}
  	
  	set <int> st;
    for (int i = 1; i <= n; i++){
	    st.clear();
	    for (int j = 0; j < v[i].size(); j++){
	      int y = v[i][j].s;
	      if (st.count(y)){
	        st.erase(y);
	      }else {
	        st.insert(y);
	      }
	 
	      if (j % BL == 0){
	        vector <int> vv;
	        for (int t: st) vv.pb(t);
	        vec[i].pb(vv);
	      }
	    }
    }
}

void getneighbours(vector <int> &vv,int x,int D){
  int l = 0,r = v[x].size() - 1,res=-1;
  while (l <= r){
    int mid = (l + r) >> 1;
    if (v[x][mid].f <= D){
      res=mid;
      l=mid+1;
    }else{
      r=mid-1;
    }
  }
  if (res==-1) return;
 
  int id = res/BL;
  set <int> st;
  for (int j = id * BL + 1; j <= res; j++){
    int y = v[x][j].s;
    if (st.count(y)){
      st.erase(y);
    }else {
      st.insert(y);
    }
  }
 
  for (int k: vec[x][id]){
    if (st.count(k)){
      st.erase(k);
    }else{
      vv.pb(h[k]);
    }
  }
 
  for (int y: st)
    vv.pb(h[y]);
  sort(vv.begin(),vv.end());
}
int question(int x, int y, int days) {
	x += 1; y += 1;
  	int ans = 1e9,l1 = 0,l2 = 0;
  	
  	vector <int> nx,ny;
	getneighbours(nx,x,days);
    getneighbours(ny,y,days);
    
    while (l1 < nx.size() && l2 < ny.size()){
      ans = min(ans,abs(nx[l1] - ny[l2]));
      if (nx[l1] < ny[l2]) ++l1;
      else ++l2;
    }
    
  	return ans;
}

Compilation message (stderr)

potion.cpp: In function 'void curseChanges(int, int*, int*)':
potion.cpp:32:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |      for (int j = 0; j < v[i].size(); j++){
      |                      ~~^~~~~~~~~~~~~
potion.cpp: In function 'int question(int, int, int)':
potion.cpp:93:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |     while (l1 < nx.size() && l2 < ny.size()){
      |            ~~~^~~~~~~~~~~
potion.cpp:93:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |     while (l1 < nx.size() && l2 < ny.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