Submission #317318

#	Time	Username	Problem	Language	Result	Execution time	Memory
317318		soroush	The Potion of Great Power (CEOI20_potion)	C++14	100 / 100	2428 ms	30200 KiB

potion

/*
#pragma GCC optimize("O2")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2,fma,tune=native")
//*/
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int  ,int > pii;
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
const ll maxn  = 1e5 + 10;
const ll mod =1e9+7;
const ld PI = acos((ld)-1);
 
#define pb push_back
//#define endl '\n'
#define dokme(x) cout << x , exit(0);
#define migmig ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ms(x , y) memset(x , y , sizeof x);
#define file_init freopen("input.txt", "r+", stdin); freopen("output.txt", "w+", stdout);
ll pw(ll a, ll b, ll md = mod){ll res = 1;while(b){if(b&1){res=(a*res)%md;}a=(a*a)%md;b>>=1;}return(res);}
 
int n , d, u , q;
int h[maxn];
 
vector < pii > query[maxn] , ans;
vector < int > adr[maxn];
vector < int > vec[2];
vector < int > adj[4*maxn];
int bz = 64;
bool mark[maxn];
set < int > st;
vector < int > fuck;
int cur = 0;
 
void build(int v){
    st.clear();
    int cnt = 0;
    for(int i = 0 ; i < int(query[v].size()) ; i ++){
        cnt++;
        mark[query[v][i].second] ^= 1;
        if(!mark[query[v][i].second])st.erase(query[v][i].second);
        else st.insert(query[v][i].second);
        if(cnt==bz){
            adr[v].pb(cur);
            adj[cur].resize(st.size());
            int i = 0;
            for(int x : st) adj[cur][i++] = x;
            cur++;
            cnt = 0;
        }
        else
            adr[v].pb(-1);
    }
    for(int i : st)mark[i] = 0;
}
 
int solve(){
    sort(vec[0].begin() , vec[0].end());
    sort(vec[1].begin() , vec[1].end());
    int mn = 1e9;
    int p1 = 0 , p2 = 0;
    while(p1 < vec[0].size() and p2 < vec[1].size()){
        mn = min(mn , abs(vec[0][p1] - vec[1][p2]));
        if(vec[0][p1] < vec[1][p2])
            p1 ++;
        else
            p2 ++;
    }
    return(mn);
}
 
void get(int v , int t , int ind = 0){
    vec[ind].clear();
    if(query[v].size() == 0) return;
    if(query[v][0].first > t) return;
    int l = 0 , r = query[v].size();
    while(r - l > 1){
        int mid = (l + r)/2;
        if(query[v][mid].first > t)
            r = mid;
        else
            l = mid;
    }
    fuck.clear();
    while(l >= 0 and adr[v][l] == -1){
        mark[query[v][l].second] ^= 1;
        fuck.pb(query[v][l].second);
        l --;
    }
    if(l >= 0 and adr[v][l] > -1){
        for(int i : adj[adr[v][l]]){
            mark[i] ^= 1;
            fuck.pb(i);
        }
    }
    for(int i : fuck)
        if(mark[i]) vec[ind].pb(h[i]) , mark[i] = 0;
}
 
void curseChanges(int U, int A[], int B[]){
  int a , b;
   u = U;
    for(int i = 1 ; i <= U ; i ++){
        a = A[i - 1];
      	b = B[i - 1];
        a ++ , b ++ ;
        query[a].pb({i , b});
        query[b].pb({i , a});
    }
  	for(int i = 1 ; i <= n ; i ++)
        build(i);
}
 
int question(int X, int Y, int V){
  int x ,y , v;
  	x = X;
  y = Y;
  v = V;
 		 x ++ , y ++ ;
        get(x , v);
        get(y , v , 1);
        return (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];

}

Compilation message (stderr)

potion.cpp: In function 'int solve()':
potion.cpp:68:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     while(p1 < vec[0].size() and p2 < vec[1].size()){
      |           ~~~^~~~~~~~~~~~~~~
potion.cpp:68:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     while(p1 < vec[0].size() and p2 < vec[1].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