Submission #1278159

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278159		reginox	Tourism (JOI23_tourism)	C++20	100 / 100	504 ms	31320 KiB

tourism

#include<bits/stdc++.h>
using namespace std;
int n,m,q;
vector<int> con[100005];
int v[100005];
int rez[100005];
int anc[100005][17];
int tin[100005],tout[100005],timer;
vector<pair<int,int>> qrys[100005];

int aib[100015];
int qry_aib(int poz)
{
    poz+=2;
    int aux=0;
    for(int i=poz;i<=m+5;i+=(i&(-i)))
        aux += aib[i];
    return aux;
}
void upd_aib(int poz, int newv)
{
    poz+=2;
    for(int i=poz;i>0;i-=(i&(-i)))
        aib[i] += newv;
}

int val[100005];
set<pair<pair<int,int>,int>> s;
void baga(int le, int ri, int t)
{
    auto it = prev(s.lower_bound({{le+1,-1},-1}));

    pair<pair<int,int>,int> tole,tori;
    tole = *it;
    tole.first.second = le-1;
    while(it!=s.end() && (*it).first.first <= ri)
    {
        tori = *it;
        upd_aib((*it).second,-((*it).first.second - (*it).first.first + 1));
        it = s.erase(it);
    }
    tori.first.first = ri+1;
    s.insert({{le,ri},t});
    upd_aib(t,ri-le+1);
    if(tole.first.first <= tole.first.second)
    {
        s.insert(tole);
        upd_aib(tole.second, tole.first.second-tole.first.first+1);
    }
    if(tori.first.first <= tori.first.second)
    {
        s.insert(tori);
        upd_aib(tori.second, tori.first.second-tori.first.first+1);
    }
    /*for(int i=le;i<=ri;i++)
    {
        upd_aib(val[i],-1);
        val[i]=t;
    }
    upd_aib(t,ri-le+1);*/
}

int depth[100005], siz[100005], head[100005], parent[100005], pos[100005], curpos;
void dfs(int nod)
{
    siz[nod]=1;
    tin[nod]=++timer;
    for(auto adj:con[nod])
    {
        if(adj!=parent[nod])
        {
            parent[adj]=nod;
            depth[adj]=depth[nod]+1;
            dfs(adj);
            siz[nod]+=siz[adj];
        }
    }
    tout[nod]=++timer;
}
void decompose(int nod, int chead)
{
    pos[nod]=++curpos;
    head[nod]=chead;
    int heavy=-1,maxc=-1;
    for(auto adj:con[nod])
        if(adj!=parent[nod] && siz[adj]>maxc)
            maxc=siz[adj], heavy=adj;
    if(heavy!=-1)
        decompose(heavy,chead);
    for(auto adj:con[nod])
        if(adj!=parent[nod] && adj!=heavy)
            decompose(adj,adj);
}
void upd_hld(int b, int t)
{
    for(;head[1]!=head[b];b=parent[head[b]])
    {
        baga(pos[head[b]], pos[b], t);
    }
    baga(pos[1],pos[b],t);
}

pair<int,int> aint[270000];
pair<int,int> combine(pair<int,int> x, pair<int,int> y)
{
    pair<int,int> aux;
    if(x.first!=-1 && (y.first==-1 || tin[x.first] < tin[y.first])) aux.first = x.first;
    else aux.first = y.first;
    if(x.second!=-1 && (y.second==-1 || tin[x.second] > tin[y.second])) aux.second = x.second;
    else aux.second = y.second;
    return aux;
}
void build(int nod, int st, int dr)
{
    if(st==dr)
    {
        aint[nod] = {v[st],v[st]};
        return;
    }
    int mij=(st+dr)/2;
    build(nod*2,st,mij);
    build(nod*2+1,mij+1,dr);
    aint[nod] = combine(aint[nod*2], aint[nod*2+1]);
}
pair<int,int> qry(int nod, int st, int dr, int le, int ri)
{
    if(le>ri)
        return {-1,-1};
    if(le==st && dr==ri)
        return aint[nod];
    int mij=(st+dr)/2;
    return combine(qry(nod*2,st,mij,le,min(mij,ri)),
                   qry(nod*2+1,mij+1,dr,max(mij+1,le),ri));

}
bool isanc(int x, int y)
{
    return (tin[x]<=tin[y] && tout[x]>=tout[y]);
}
int lca(int x, int y)
{
    if(isanc(x,y))
        return x;
    if(isanc(y,x))
        return y;
    for(int p=16;p>=0;p--)
        if(!isanc(anc[x][p],y))
            x = anc[x][p];
    return anc[x][0];
}
int qry_lca(int le, int ri)
{
    pair<int,int> x = qry(1,1,m,le,ri);
    return lca(x.first, x.second);
}
signed main()
{
    cin>>n>>m>>q;
    int a,b;
    for(int i=1;i<n;i++)
    {
        cin>>a>>b;
        con[a].push_back(b);
        con[b].push_back(a);
    }
    dfs(1);
    decompose(1,1);

    for(int i=1;i<=n;i++)
        anc[i][0] = parent[i];
    anc[1][0]=1;
    for(int p=1;p<17;p++)
        for(int i=1;i<=n;i++)
            anc[i][p] = anc[anc[i][p-1]][p-1];

    for(int i=1;i<=m;i++)
        cin>>v[i];
    build(1,1,m);
    for(int i=1;i<=q;i++)
    {
        cin>>a>>b;
        qrys[b].push_back({a,i});
    }
    s.insert({{0,n+1},0});
    upd_aib(0,n);
    for(int i=1;i<=m;i++)
    {
        upd_hld(v[i],i);
        for(auto [le,id]:qrys[i])
        {
            int lc = qry_lca(le,i);
            rez[id] = qry_aib(le) - depth[lc];
        }
    }
    for(int i=1;i<=q;i++)
        cout<<rez[i]<<"\n";
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 7 / 7
• Subtask 4: 18 / 18
• Subtask 5: 24 / 24
• Subtask 6: 41 / 41