Submission #1161159

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161159		ace5	Tourism (JOI23_tourism)	C++20	100 / 100	977 ms	28340 KiB

tourism

#include <bits/stdc++.h>

using namespace std;

const int maxn = 100005;
const int maxlog = 17;

int fenv[maxn];

void modify(int i,int x)
{
    //cout << i << ' ' << x << endl;
    for(int j = i;j < maxn;j += ((j)&(-j)))
    {
        fenv[j] += x;
    }
}
int get(int l,int r)
{
    int ans = 0;
    for(int j = r;j > 0;j -= ((j)&(-j)))
    {
        ans += fenv[j];
    }
    for(int j = l-1;j > 0;j -= ((j)&(-j)))
    {
        ans -= fenv[j];
    }
    return ans;
}

vector<int> g[maxn];
int la[maxlog][maxn];
int tin[maxn],tout[maxn];
int dep[maxn];
int lv[maxn];
int head[maxn];
int par[maxn];
int sz[maxn];
int times = 0;

set<pair<pair<int,int>,int>> seg;


void dfs(int v,int p,int d)
{
    par[v] = p;
    for(int j = 0;j < maxlog;++j)
    {
        la[j][v] = (j == 0 ? p : la[j-1][la[j-1][v]]);
    }
    dep[v] = d;
    sz[v] = 1;
    for(int i = 0;i < g[v].size();++i)
    {
        if(g[v][i] != p)
        {
            dfs(g[v][i],v,d+1);
            sz[v] += sz[g[v][i]];
            if(g[v][0] == p || sz[g[v][0]] < sz[g[v][i]])
                swap(g[v][0],g[v][i]);
        }
    }
}
void hld(int v,int p,int th)
{
    head[v] = th;
    tin[v] = times++;
    for(auto u:g[v])
    {
        if(u != p)
        {
            hld(u,v,(u == g[v][0] ? th : u));
        }
    }
    tout[v] = times;
    return ;
}
bool isP(int u,int v)
{
    return tin[u] <= tin[v] && tout[u] >= tout[v];
}
int lca(int u,int v)
{
    for(int j = maxlog-1;j >= 0;--j)
    {
        if(!isP(la[j][u],v))
            u = la[j][u];
    }
    if(!isP(u,v))
        u = la[0][u];
    return u;
}
int dist(int u,int v)
{
    return dep[u] + dep[v] - 2 * dep[lca(u,v)];
}
void add(pair<pair<int,int>,int> a)
{
    seg.insert(a);
    if(a.second)
        modify(a.second,a.first.second-a.first.first+1);
}
void del(pair<pair<int,int>,int> a)
{
    seg.erase(a);
    if(a.second)
        modify(a.second,-a.first.second+a.first.first-1);
}

void modifys(int l,int r,int x)
{
   // cout << seg.size() << endl;
    //cout << l << ' ' << r << ' ' << x << endl;
    while(true)
    {
        auto it = seg.lower_bound(make_pair(make_pair(l,-1),-1));
        if(it == seg.end() || (*it).first.second > r)
            break;
        del(*it);
    }
    //cout << "?" << endl;
    auto it = seg.lower_bound(make_pair(make_pair(l,-1),-1));
    if(it != seg.end() && (*it).first.first <= r)
    {
        add({{r+1,(*it).first.second},(*it).second});
        del(*it);
    }
    it = seg.lower_bound(make_pair(make_pair(l,-1),-1));
    if(it != seg.begin())
    {
       // cout << "?" << endl;
        it--;
        if((*it).first.second >= l)
        {
            //cout << "j" << endl;
            if((*it).first.second > r)
            {
                //cout << "y" << endl;
                add({{r+1,(*it).first.second},(*it).second});
                add({{(*it).first.first,l-1},(*it).second});
                //cout << "o" << endl;
            }
            else
            {
                add({{(*it).first.first,l-1},(*it).second});
            }
            //cout << "u" << endl;
            del((*it));
        }
    }
    //cout << "t" << endl;
    add({{l,r},x});
}

void modifyp(int u,int v,int x)
{
  //  cout << u << ' ' << v << ' ' << x << endl;
    while(!isP(head[u],v))
    {
        //cout << u << ' ';
        modifys(tin[head[u]],tin[u],x);
        u = par[head[u]];
    }
    while(!isP(head[v],u))
    {
       // cout << v << ' ';
        modifys(tin[head[v]],tin[v],x);
        v = par[head[v]];
    }
    if(!isP(u,v))
        swap(u,v);
    modifys(tin[u],tin[v],x);
    return ;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n,m,q;
    cin >> n >> m >> q;
    for(int i = 0;i < n-1;++i)
    {
        int u,v;
        cin >> u >> v;
        u--;
        v--;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(0,0,0);
    hld(0,0,0);
    for(int j = 0;j < m;++j)
    {
        cin >> lv[j];
        lv[j]--;
    }
    int res[q];
    vector<vector<pair<int,int>>> que(m);
    for(int j = 0;j < q;++j)
    {
        int l,r;
        cin >> l >> r;
        l--;
        r--;
        que[r].push_back({l,j});
    }
   // cout << endl;
    seg.insert({{0,n-1},0});
    for(int j = 0;j < m;++j)
    {
        //cout << j << endl;
        if(j != 0)
            modifyp(lv[j-1],lv[j],j);
        modifyp(lv[j],lv[j],j+1);
       // cout << j << endl;
        for(int y = 0;y < que[j].size();++y)
        {
            //cout << "que " << que[j][y].first << ' ' << j << endl;
            //for(auto [g,h] : seg)
            //{
            //    cout << "seg " << g.first << ' ' << g.second << ' ' << h << endl;
            //}
            res[que[j][y].second] = get(que[j][y].first+1,m);
        }
    }
    for(int j = 0;j < q;++j)
        cout << res[j] << "\n";
}

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