oj.uz

Submission #294557

# Submission time Handle Problem Language Result Execution time Memory
294557 2020-09-09T04:38:28 Z nandonathaniel The Potion of Great Power (CEOI20_potion) C++14
100 / 100
 2551 ms 34776 KB 
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int MAXN=100005;
 
int h[MAXN],C[MAXN],n,D;
vector<pii> adj[MAXN];
vector<vector<int> > preCompute[MAXN];
 
void init(int N, int d, int H[]) {
	n=N;D=d;
	for(int i=0;i<n;i++)h[i]=H[i];
}
 
void curseChanges(int U, int A[], int B[]) {
	for(int i=0;i<U;i++){
		adj[A[i]].push_back({B[i],i+1});
		adj[B[i]].push_back({A[i],i+1});
	}
	for(int i=0;i<n;i++){
		C[i]=(int)sqrt((int)adj[i].size());
		if(C[i]==0)C[i]=1;
		set<int> S;
		preCompute[i].push_back(vector<int>());
		for(int j=0;j<adj[i].size();j++){
			if(S.count(adj[i][j].first)){
				S.erase(adj[i][j].first);
			}
			else S.insert(adj[i][j].first);
			if((j+1)%C[i]==0){
				preCompute[i].push_back(vector<int>());
				for(int isi : S)preCompute[i].back().push_back(isi);
			}
		}
	}
}
 
bitset<100005> stat;
 
int question(int a, int b, int d) {
	int ans=1e9;
	if(d==0){
		return ans;
	}
	int ki=0,ka=adj[a].size()-1,res=-1;
	while(ki<=ka){
		int mid=(ki+ka)/2;
		if(adj[a][mid].second<=d){
			res=mid;
			ki=mid+1;
		}
		else ka=mid-1;
	}
	stat.reset();
	vector<int> A;
	if(res!=-1){
		for(auto isi : preCompute[a][res/C[a]])stat[isi]=true;
		for(int i=(res/C[a])*C[a];i<=res;i++){
			stat[adj[a][i].first]=stat[adj[a][i].first]^1;
		}
		for(auto isi : preCompute[a][res/C[a]]){
			if(stat[isi])A.push_back(h[isi]);
		}
		for(int i=(res/C[a])*C[a];i<=res;i++){
			if(stat[adj[a][i].first])A.push_back(h[adj[a][i].first]);
		}
	}
	ki=0;ka=adj[b].size()-1;res=-1;
	while(ki<=ka){
		int mid=(ki+ka)/2;
		if(adj[b][mid].second<=d){
			res=mid;
			ki=mid+1;
		}
		else ka=mid-1;
	}
	stat.reset();
	vector<int> B;
	if(res!=-1){
		for(auto isi : preCompute[b][res/C[b]])stat[isi]=true;
		for(int i=(res/C[b])*C[b];i<=res;i++){
			stat[adj[b][i].first]=stat[adj[b][i].first]^1;
		}
		for(auto isi : preCompute[b][res/C[b]]){
			if(stat[isi])B.push_back(h[isi]);
		}
		for(int i=(res/C[b])*C[b];i<=res;i++){
			if(stat[adj[b][i].first])B.push_back(h[adj[b][i].first]);
		}
	}
	sort(A.begin(),A.end());
	sort(B.begin(),B.end());
	int x=0,y=0;
	while(x<(int)A.size() && y<(int)B.size()){
		ans=min(ans,abs(A[x]-B[y]));
		if(A[x]<B[y])x++;
		else y++;
	}
	return ans;
}

Compilation message

potion.cpp: In function 'void curseChanges(int, int*, int*)':
potion.cpp:25:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |   for(int j=0;j<adj[i].size();j++){
      |               ~^~~~~~~~~~~~~~

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4992 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5248 KB Output is correct
2 Correct 6 ms 5248 KB Output is correct
3 Correct 6 ms 5248 KB Output is correct
4 Correct 28 ms 9592 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 387 ms 32120 KB Output is correct
2 Correct 373 ms 31992 KB Output is correct
3 Correct 346 ms 14968 KB Output is correct
4 Correct 1395 ms 26744 KB Output is correct
5 Correct 517 ms 23136 KB Output is correct
6 Correct 2551 ms 33040 KB Output is correct
7 Correct 585 ms 28792 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 368 ms 31992 KB Output is correct
2 Correct 1068 ms 25408 KB Output is correct
3 Correct 761 ms 30840 KB Output is correct
4 Correct 1146 ms 33144 KB Output is correct
5 Correct 421 ms 32888 KB Output is correct
6 Correct 1230 ms 33144 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 6912 KB Output is correct
2 Correct 135 ms 6016 KB Output is correct
3 Correct 214 ms 6016 KB Output is correct
4 Correct 802 ms 6776 KB Output is correct
5 Correct 813 ms 7040 KB Output is correct
6 Correct 159 ms 5888 KB Output is correct
7 Correct 685 ms 6180 KB Output is correct

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4992 KB Output is correct
2 Correct 6 ms 5248 KB Output is correct
3 Correct 6 ms 5248 KB Output is correct
4 Correct 6 ms 5248 KB Output is correct
5 Correct 28 ms 9592 KB Output is correct
6 Correct 387 ms 32120 KB Output is correct
7 Correct 373 ms 31992 KB Output is correct
8 Correct 346 ms 14968 KB Output is correct
9 Correct 1395 ms 26744 KB Output is correct
10 Correct 517 ms 23136 KB Output is correct
11 Correct 2551 ms 33040 KB Output is correct
12 Correct 585 ms 28792 KB Output is correct
13 Correct 368 ms 31992 KB Output is correct
14 Correct 1068 ms 25408 KB Output is correct
15 Correct 761 ms 30840 KB Output is correct
16 Correct 1146 ms 33144 KB Output is correct
17 Correct 421 ms 32888 KB Output is correct
18 Correct 1230 ms 33144 KB Output is correct
19 Correct 110 ms 6912 KB Output is correct
20 Correct 135 ms 6016 KB Output is correct
21 Correct 214 ms 6016 KB Output is correct
22 Correct 802 ms 6776 KB Output is correct
23 Correct 813 ms 7040 KB Output is correct
24 Correct 159 ms 5888 KB Output is correct
25 Correct 685 ms 6180 KB Output is correct
26 Correct 800 ms 24952 KB Output is correct
27 Correct 1250 ms 31092 KB Output is correct
28 Correct 1391 ms 34776 KB Output is correct
29 Correct 1221 ms 26640 KB Output is correct
30 Correct 2472 ms 33048 KB Output is correct
31 Correct 2205 ms 24696 KB Output is correct
32 Correct 2228 ms 33352 KB Output is correct