Submission #602195

#	Time	Username	Problem	Language	Result	Execution time	Memory
602195		Theo830	The Potion of Great Power (CEOI20_potion)	C++17	100 / 100	2595 ms	77888 KiB

potion

#include <bits/stdc++.h>
using namespace std;
typedef int ll;
const ll INF = 1e9+7;
const ll MOD = 998244353;
typedef pair<ll,ll> ii;
#define iii pair<ii,ll>
#define ull unsigned ll
#define f(i,a,b) for(ll i = a;i < b;i++)
#define pb push_back
#define vll vector<ll>
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
///I hope I will get uprating and don't make mistakes
///I will never stop programming
///sqrt(-1) Love C++
///Please don't hack me
///@TheofanisOrfanou Theo830
///Think different approaches (bs,dp,greedy,graphs,shortest paths,mst)
///Stay Calm
///Look for special cases
///Beware of overflow and array bounds
///Think the problem backwards
///Training
///Dremix10's template
template<typename T>
struct SPARSE{
    vector<vector<T> > sparse;
    vector<int> log;
    const int maxPow = 20;
    int N;

    void init(int n){
        sparse.assign(n,vector<T>(maxPow));
        log.assign(n+1,0);
        N = n;

        for(int i = 2;i <= n;i++)
            log[i] = log[i/2] + 1;
    }

    // supports 0-indexing
    void build(vector<T> arr){
        int i,j;
        for(i = 0;i < N ;i++)
            sparse[i][0] = arr[i];

        for(j = 1;j < maxPow;j++)
            for(i = 0;i + (1<<j) <= N;i++)
                sparse[i][j] = min(sparse[i][j-1],sparse[i+(1<<(j-1))][j-1]);
    }

    T query(int l, int r){
        int k = log[r-l+1];
        return min(sparse[l][k],sparse[r-(1<<k)+1][k]);
    }

};
vector<iii>rang[100005];
SPARSE<ll>s[100005];
ll n;
ll h[100005];
void init(int N, int D, int H[]){
    n = N;
    f(i,0,n){
        h[i] = H[i];
    }
}
void curseChanges(int U, int A[], int B[]) {
    ll u = U;
    vector<ii>exo[n];
    f(i,0,u){
        ll a = A[i],b = B[i];
        exo[a].pb(ii(b,i+1));
        exo[b].pb(ii(a,i+1));
    }
    ll last[n];
    memset(last,-1,sizeof last);
    f(i,0,n){
        set<ll>ex;
        for(auto x:exo[i]){
            if(last[x.F] == -1){
                last[x.F] = x.S;
                ex.insert(x.F);
            }
            else{
                rang[i].pb(iii(ii(x.S - 1,last[x.F]),h[x.F]));
                last[x.F] = -1;
                ex.erase(x.F);
            }
        }
        for(auto x:ex){
            rang[i].pb(iii(ii(u + 5,last[x]),h[x]));
            last[x] = -1;
        }
        sort(all(rang[i]));
        s[i].init(rang[i].size());
        vector<ll>vale;
        for(auto x:rang[i]){
            vale.pb(x.F.S);
        }
        s[i].build(vale);
    }
}
int question(int x, int y, int v) {
    ll ans = 1e9;
    vector<ii>kame;
    ll L;
    ll pos = lower_bound(all(rang[x]),iii(ii(v,0),0)) - rang[x].begin();
    if(rang[x].size() > 750){
        f(j,pos,rang[x].size()){
            if(rang[x][j].F.S <= v){
                kame.pb(ii(rang[x][j].S,0));
            }
        }
    }
    else{
        L = pos;
        while(1){
            ll l = L,r = rang[x].size() - 1;
            pos = r + 1;
            while(l <= r){
                ll mid = (l+r)/2;
                if(s[x].query(L,mid) <= v){
                    r = mid - 1;
                    pos = min(pos,mid);
                }
                else{
                    l = mid + 1;
                }
            }
            if(pos < rang[x].size()){
                kame.pb(ii(rang[x][pos].S,0));
            }
            else{
                break;
            }
            L = pos + 1;
        }
    }
    pos = lower_bound(all(rang[y]),iii(ii(v,0),0)) - rang[y].begin();
    if(rang[y].size() > 750){
        f(j,pos,rang[y].size()){
            if(rang[y][j].F.S <= v){
                kame.pb(ii(rang[y][j].S,1));
            }
        }
    }
    else{
        L = pos;
        while(1){
            ll l = L,r = rang[y].size() - 1;
            pos = r + 1;
            while(l <= r){
                ll mid = (l+r)/2;
                if(s[y].query(L,mid) <= v){
                    r = mid - 1;
                    pos = min(pos,mid);
                }
                else{
                    l = mid + 1;
                }
            }
            if(pos < rang[y].size()){
                kame.pb(ii(rang[y][pos].S,1));
            }
            else{
                break;
            }
            L = pos + 1;
        }
    }
    sort(all(kame));
    f(i,0,(ll)kame.size()-1){
        if(kame[i].S != kame[i+1].S){
            ans = min(ans,kame[i+1].F - kame[i].F);
        }
    }
    return ans;
}

Compilation message (stderr)

potion.cpp: In function 'int question(int, int, int)':
potion.cpp:9:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define f(i,a,b) for(ll i = a;i < b;i++)
......
  112 |         f(j,pos,rang[x].size()){
      |           ~~~~~~~~~~~~~~~~~~~~   
potion.cpp:112:9: note: in expansion of macro 'f'
  112 |         f(j,pos,rang[x].size()){
      |         ^
potion.cpp:133:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |             if(pos < rang[x].size()){
      |                ~~~~^~~~~~~~~~~~~~~~
potion.cpp:9:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define f(i,a,b) for(ll i = a;i < b;i++)
......
  144 |         f(j,pos,rang[y].size()){
      |           ~~~~~~~~~~~~~~~~~~~~   
potion.cpp:144:9: note: in expansion of macro 'f'
  144 |         f(j,pos,rang[y].size()){
      |         ^
potion.cpp:165:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  165 |             if(pos < rang[y].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