Submission #480138

#	Time	Username	Problem	Language	Result	Execution time	Memory
480138		fatemetmhr	The Potion of Great Power (CEOI20_potion)	C++17	100 / 100	2717 ms	39980 KiB

potion

//  ~Be name khoda~  //

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second
#define cl       clear
#define endll    '\n'

const int maxn  =  1e6   + 10;
const int maxn5 =  1e5   + 10;
const int maxnt =  1.2e6 + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   +  7;
const int ssq   =  503;
const ll  inf   =  2e18;

int n, d, u, h[maxn5], val[2 * maxn5];
vector <int> ver1, ver2, adj[maxn5], lim[maxn5];
map <int, int> have[maxn5];
pair <int, int> e[2 * maxn5];

inline bool cmp (int a, int b){
	return val[a] < val[b];
}

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

void curseChanges(int U, int A[], int B[]) {
	u = U;
	for(int i = 0; i < u; i++){
		int a = A[i];
		int b = B[i];
		e[i] = {a, b};
		if(have[b].find(a) == have[b].end()){
			adj[b].pb(i);
			have[b][a] = i;
		}
		else{
			val[have[b][a]] = i;
			have[b].erase(a);
		}
		if(have[a].find(b) == have[a].end()){
			adj[a].pb(i);
			have[a][b] = i;
		}
		else{
			val[have[a][b]] = i;
			have[a].erase(b);
		}
	}
	for(int i = 0; i < n; i++) for(auto it = have[i].begin(); it != have[i].end(); it++) val[it->se] = u + 10;
	for(int i = 0; i < n; i++){
		int ind = 0;
		while(ind < adj[i].size()){
			lim[i].pb(adj[i][min(ind + ssq - 1, int(adj[i].size()) - 1)]);
			sort(adj[i].begin() + ind, adj[i].begin() + min(ssq + ind, int(adj[i].size())), cmp);
			ind += ssq; 
		}
	}
	return;
}

int question(int x, int y, int v) {
	if(v == 0) return 1000000000;
	ver1.clear(); ver2.clear();
	v--;
	
	int ind = 0, num = 0;
	while(ind < adj[x].size()){
		if(lim[x][num] <= v){
			int j = min(ind + ssq - 1, int(adj[x].size()) - 1);
			while(j >= ind && val[adj[x][j]] > v){
				int u = e[adj[x][j]].fi;
				if(u == x) u = e[adj[x][j]].se;
				ver1.pb(h[u]);
				j--;
			}
		}
		else{
			int j = ind;
			for(; j < min(ind + ssq, int(adj[x].size())); j++){
				if(adj[x][j] <= v && val[adj[x][j]] > v){
					int u = e[adj[x][j]].fi;
					if(u == x) u = e[adj[x][j]].se;
					ver1.pb(h[u]);
				}
			}
		}
		num++;
		ind += ssq;
	}
	
	ind = 0, num = 0; x = y;
	while(ind < adj[x].size()){
		if(lim[x][num] <= v){
			int j = min(ind + ssq - 1, int(adj[x].size()) - 1);
			while(j >= ind && val[adj[x][j]] > v){
				int u = e[adj[x][j]].fi;
				if(u == x) u = e[adj[x][j]].se;
				ver2.pb(h[u]);
				j--;
			}
		}
		else{
			int j = ind;
			for(; j < min(ind + ssq, int(adj[x].size())); j++){
				if(adj[x][j] <= v && val[adj[x][j]] > v){
					int u = e[adj[x][j]].fi;
					if(u == x) u = e[adj[x][j]].se;
					ver2.pb(h[u]);
				}
			}
		}
		num++;
		ind += ssq;
	}
	
	if(ver1.empty() || ver2.empty()) return 1000000000;
	
	sort(all(ver1));
	sort(all(ver2));
	ind = 0;
	int ans = 1000000000;
	for(int i = 0; i < ver1.size(); i++){
		while(ind < ver2.size() && ver2[ind] <= ver1[i]) ind++;
		if(ind > 0) ans = min(ans, ver1[i] - ver2[ind - 1]);
		if(ind < ver2.size()) ans = min(ans, ver2[ind] - ver1[i]);
	}
	
	return ans;
}

Compilation message (stderr)

potion.cpp: In function 'void curseChanges(int, int*, int*)':
potion.cpp:67:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |   while(ind < adj[i].size()){
      |         ~~~~^~~~~~~~~~~~~~~
potion.cpp: In function 'int question(int, int, int)':
potion.cpp:82:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |  while(ind < adj[x].size()){
      |        ~~~~^~~~~~~~~~~~~~~
potion.cpp:107:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |  while(ind < adj[x].size()){
      |        ~~~~^~~~~~~~~~~~~~~
potion.cpp:137:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |  for(int i = 0; i < ver1.size(); i++){
      |                 ~~^~~~~~~~~~~~~
potion.cpp:138:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |   while(ind < ver2.size() && ver2[ind] <= ver1[i]) ind++;
      |         ~~~~^~~~~~~~~~~~~
potion.cpp:140:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  140 |   if(ind < ver2.size()) ans = min(ans, ver2[ind] - ver1[i]);
      |      ~~~~^~~~~~~~~~~~~

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