oj.uz

Submission #480138

# Submission time Handle Problem Language Result Execution time Memory
480138 2021-10-14T19:26:22 Z fatemetmhr The Potion of Great Power (CEOI20_potion) C++17
100 / 100
 2717 ms 39980 KB 
//  ~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

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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9672 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9800 KB Output is correct
2 Correct 8 ms 9840 KB Output is correct
3 Correct 9 ms 9784 KB Output is correct
4 Correct 24 ms 10780 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 413 ms 39972 KB Output is correct
2 Correct 384 ms 39976 KB Output is correct
3 Correct 180 ms 15460 KB Output is correct
4 Correct 1431 ms 25068 KB Output is correct
5 Correct 576 ms 35528 KB Output is correct
6 Correct 2717 ms 25996 KB Output is correct
7 Correct 529 ms 25764 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 365 ms 39980 KB Output is correct
2 Correct 1193 ms 17728 KB Output is correct
3 Correct 845 ms 26160 KB Output is correct
4 Correct 1304 ms 25968 KB Output is correct
5 Correct 534 ms 39436 KB Output is correct
6 Correct 1346 ms 25920 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 11464 KB Output is correct
2 Correct 81 ms 10056 KB Output is correct
3 Correct 142 ms 9972 KB Output is correct
4 Correct 760 ms 10860 KB Output is correct
5 Correct 695 ms 11152 KB Output is correct
6 Correct 93 ms 10904 KB Output is correct
7 Correct 672 ms 10184 KB Output is correct

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9672 KB Output is correct
2 Correct 8 ms 9800 KB Output is correct
3 Correct 8 ms 9840 KB Output is correct
4 Correct 9 ms 9784 KB Output is correct
5 Correct 24 ms 10780 KB Output is correct
6 Correct 413 ms 39972 KB Output is correct
7 Correct 384 ms 39976 KB Output is correct
8 Correct 180 ms 15460 KB Output is correct
9 Correct 1431 ms 25068 KB Output is correct
10 Correct 576 ms 35528 KB Output is correct
11 Correct 2717 ms 25996 KB Output is correct
12 Correct 529 ms 25764 KB Output is correct
13 Correct 365 ms 39980 KB Output is correct
14 Correct 1193 ms 17728 KB Output is correct
15 Correct 845 ms 26160 KB Output is correct
16 Correct 1304 ms 25968 KB Output is correct
17 Correct 534 ms 39436 KB Output is correct
18 Correct 1346 ms 25920 KB Output is correct
19 Correct 56 ms 11464 KB Output is correct
20 Correct 81 ms 10056 KB Output is correct
21 Correct 142 ms 9972 KB Output is correct
22 Correct 760 ms 10860 KB Output is correct
23 Correct 695 ms 11152 KB Output is correct
24 Correct 93 ms 10904 KB Output is correct
25 Correct 672 ms 10184 KB Output is correct
26 Correct 723 ms 18040 KB Output is correct
27 Correct 1259 ms 25992 KB Output is correct
28 Correct 1399 ms 34192 KB Output is correct
29 Correct 1273 ms 25156 KB Output is correct
30 Correct 2441 ms 26048 KB Output is correct
31 Correct 2206 ms 17600 KB Output is correct
32 Correct 2260 ms 25996 KB Output is correct