Submission #746981

#	Time	Username	Problem	Language	Result	Execution time	Memory
746981		grogu	The Potion of Great Power (CEOI20_potion)	C++14	56 / 100	3064 ms	77528 KiB

potion

#include <bits/stdc++.h>
#define ll int
#define pb push_back
#define fi first
#define sc second
#define pll pair<ll,ll>
#define endl '\n'
#define all(a) a.begin(),a.end()
#define llinf 1000000000
#define si(a) (ll)(a.size())
#define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define cer(a) {cerr<<#a<<": ";for(ll x_ : a) cerr<<x_<< " ";cerr<<endl;}

using namespace std;
#define maxn 200005
ll n,d,m;
vector<pll> t[2*maxn];
map<pll,ll> mp;
ll ls[2*maxn],rs[2*maxn],tsz,root = 0;
ll a[maxn];
void init(int N, int D, int H[]) {
	n = N;
	d = D;
	for(ll i = 1;i<=n;i++){
		a[i] = H[i-1];
	}
}
void init(ll &v,ll tl,ll tr){
    if(!v) v = ++tsz;
    if(tl==tr) return;
    ll mid = (tl+tr)/2;
    init(ls[v],tl,mid);
    init(rs[v],mid+1,tr);
}
void upd(ll v,ll tl,ll tr,ll l,ll r,pll p){
    if(tl>tr||tl>r||l>r||l>tr) return;
    if(tl>=l&&tr<=r){t[v].pb(p);return;}
    ll mid = (tl+tr)/2;
    upd(ls[v],tl,mid,l,r,p);
    upd(rs[v],mid+1,tr,l,r,p);
}
pll f(pll p){return {min(p.fi,p.sc),max(p.fi,p.sc)};}
map<pll,bool> tu;
void curseChanges(int U, int A[], int B[]) {
    m = U;
    init(root,0,m);
    for(ll i = 0;i<m;i++){
        ll x = A[i],y = B[i];
        x++; y++;
        pll p = f({x,y});
        if(!tu[p]){
            mp[p] = i+1;
            tu[p] = 1;
        }else{
            upd(root,0,m,mp[p],i,{x,y});
            upd(root,0,m,mp[p],i,{y,x});
            tu[p] = 0;
        }
    }
    for(auto it : mp){
        if(tu[it.fi]){
            pll p = it.fi;
            ll x = p.fi,y = p.sc;
            upd(root,0,m,it.sc,m,{x,y});
            upd(root,0,m,it.sc,m,{y,x});
        }
    }
    for(ll i = 1;i<=tsz;i++) sort(all(t[i]));
}
bool cmp(ll x,ll y){return a[x]<a[y];}
vector<ll> vx,vy;
ll get(vector<pll> &v,ll x){
    ll l = 0,r = v.size()-1,rez = -1,mid;
    while(l<=r){
        mid = (l+r)/2;
        if(v[mid].fi>=x) rez = mid,r = mid-1;
        else l = mid+1;
    }
    return rez;
}
void get(ll v,ll tl,ll tr,ll id,ll x,ll y){
    ll i = get(t[v],x);
    if(i!=-1){
        for(ll j = i;j<t[v].size();j++){
            if(t[v][j].fi!=x) break;
            vx.pb(t[v][j].sc);
        }
    }
    i = get(t[v],y);
    if(i!=-1){
        for(ll j = i;j<t[v].size();j++){
            if(t[v][j].fi!=y) break;
            vy.pb(t[v][j].sc);
        }
    }
    if(tl==tr) return;
    ll mid = (tl+tr)/2;
    if(id<=mid) get(ls[v],tl,mid,id,x,y);
    else get(rs[v],mid+1,tr,id,x,y);
}
ll reshi(vector<ll> c,vector<ll> b){
    ll j = 0;
    ll ans = llinf;
    for(ll i = 0;i<si(c);i++){
        while(j<=si(b)-1&&a[b[j]]<a[c[i]]) j++;
        if(j==si(b)) break;
        ans = min(ans,a[b[j]]-a[c[i]]);
    }
    return ans;
}
int question(int x, int y, int j) {
    x++; y++;
    vx.clear();
    vy.clear();
    get(root,0,m,j,x,y);
    sort(all(vx),cmp);
    sort(all(vy),cmp);
    return min(reshi(vx,vy),reshi(vy,vx));
}
/**
6 5 11 4
2 42 1000 54 68 234
0 1
2 0
3 4
3 5
3 5
1 3
5 3
0 5
3 0
1 3
3 5
0 3 4 26
3 0 8 0
0 5 5 1000000000
3 0 11 14
*/

Compilation message (stderr)

potion.cpp: In function 'void get(int, int, int, int, int, int)':
potion.cpp:84:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |         for(ll j = i;j<t[v].size();j++){
      |                      ~^~~~~~~~~~~~
potion.cpp:91:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |         for(ll j = i;j<t[v].size();j++){
      |                      ~^~~~~~~~~~~~

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