Submission #1147306

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147306		thunopro	The Potion of Great Power (CEOI20_potion)	C++20	38 / 100	1213 ms	327680 KiB

potion

#include<bits/stdc++.h>
using namespace std ; 
#define maxn 200009
#define ll long long 
#define pb push_back 
#define fi first 
#define se second 
#define left id<<1
#define right id<<1|1 
#define re exit(0); 
#define _lower(x) lower_bound(v.begin(),v.end(),x)-v.begin()+1 
#define TIME ( 1.0*clock() / CLOCKS_PER_SEC )
const int mod = 1e9+7 ;
const int INF = 1e9 ; 

typedef vector<int> vi ; 
typedef pair<int,int> pii ; 
typedef vector<pii> vii ; 

template < typename T > void chkmin ( T &a , T b ) { if ( a > b ) a = b ; } 
template < typename T > void chkmax ( T &a , T b ) { if ( a < b ) a = b ; } 

void add ( int &a , int b ) 
{
	a += b ; 
	if ( a >= mod ) a -= mod ; 
	if ( a < 0 ) a += mod ; 
}

void rf () 
{
	freopen ("bai1.inp","r",stdin) ;
}

mt19937 rng (time(0)) ; 

int _pow ( int a , int n ) 
{
	if ( n == 0 ) return 1 ; 
	int res = _pow (a,n/2) ; 
	if ( n % 2 ) return 1ll*res*res%mod*a%mod ; 
	else return 1ll*res*res%mod ; 
}

int N ; 
int n , d , h [maxn] ; 
unordered_map <int,int> has [maxn] ; 
int nday ; 

unordered_map <int,vector<int>> T [maxn*4] ; 
void update ( int id , int l , int r , int u , int v , int edge_u , int edge_v ) 
{
	if ( l > v || r < u ) return ; 
	if ( u <= l && r <= v ) 
	{
		T [id][edge_u] . pb (h[edge_v]) ; 
		T [id][edge_v] . pb (h[edge_u]) ;
		return ; 
	}
	int mid = (l+r)/2 ; 
	update (left,l,mid,u,v,edge_u,edge_v) ; 
	update (right,mid+1,r,u,v,edge_u,edge_v) ; 
}
void update ( int u , int v , int l , int r ) 
{
//	cout << u << " " << v << " " << l << " " << r << '\n' ; 
	update (1,1,N,l,r,u,v) ; 
}

vi res_solve ; 
void solve ( int id , int l , int r , int day , int pos ) 
{
	if ( l > day || r < day ) return ; 
	for ( auto x : T [id][pos] ) res_solve . pb (x) ; 
	if ( l == r ) return ; 
	int mid = (l+r)/2 ; 
	solve (left,l,mid,day,pos) ; 
	solve (right,mid+1,r,day,pos) ; 
}
vector<int> solve ( int pos , int day ) 
{
	res_solve . clear () ; 
	solve (1,1,N,day,pos) ; 
	return res_solve ; 
}
void init ( int N , int D , int H [] ) 
{
	n = N ; d = D ; 
	for ( int i = 1 ; i <= n ; i ++ ) h [i] = H [i-1] ; 
}

void curseChanges ( int NDAY , int A [] , int B [] ) 
{
	NDAY ++ ; 
	nday = N = NDAY ; 
	for ( int i = 2 ; i <= NDAY ; i ++ ) 
	{
		int u = A [i-2] + 1 , v = B [i-2] + 1 ; 
		if ( u > v ) swap (u,v) ; 
		if ( has [u][v] ) update (u,v,has[u][v],i-1) , has [u][v] = 0 ; 
		else has [u][v] = i ; 
	}
	for ( int i = 1 ; i <= n ; i ++ ) 
	{
		for ( auto x : has [i] ) if (x.se) update (i,x.fi,x.se,NDAY) ; 
	}
}

int question ( int X , int Y , int DAY ) 
{
	DAY ++ , X ++ , Y ++ ; 
	vector<int> vector_x = solve (X,DAY) ; 
	vector<int> vector_y = solve (Y,DAY) ; 
	
	if ( vector_x.size () == 0 || vector_y.size () == 0 ) return 1e9 ; 
	
	sort (vector_x.begin(),vector_x.end()) ; 
	sort (vector_y.begin(),vector_y.end()) ; 
	
	int res = 1e9 ; 
	for ( int i = 0 , j = 0 ; i < vector_x.size () ; i ++ )
	{
		while ( j < vector_y.size () && vector_y [j] < vector_x [i] ) j ++ ; 
		if ( j < vector_y.size () ) chkmin (res,abs(vector_x[i]-vector_y[j])) ; 
		if ( j ) chkmin (res,abs(vector_x[i]-vector_y[j-1])) ; 
	}
	return res ; 
}
//int main () 
//{
//	ios_base::sync_with_stdio(0); 
//	cin.tie(0);cout.tie(0); 
////	rf () ;
//	int N = 6 ; 
//	int D = 5 ; 
//	int H [ ]= {2, 42, 1000, 54, 68, 234}; 
//	int U = 11 ; 
//	int A []= {0, 2, 3, 3, 3, 1, 5, 0, 3, 1, 3} ; 
//	int B []= {1, 0, 4, 5, 5, 3, 3, 5, 0, 3, 5} ; 
//	init (N,D,H);
//	curseChanges (U,A,B) ;
//	cout << question (0,3,4) << "\n" ; 
//	cout << question (3,0,8) << "\n" ; 
//	cout << question (0,5,5) << "\n" ; 
//	cout << question (3,0,11) << "\n" ;  
//}

Compilation message (stderr)

potion.cpp: In function 'void rf()':
potion.cpp:32:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |         freopen ("bai1.inp","r",stdin) ;
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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