Submission #924715

#	Time	Username	Problem	Language	Result	Execution time	Memory
924715		ace5	Passport (JOI23_passport)	C++17	100 / 100	680 ms	62036 KiB

passport

#include <bits/stdc++.h>

using namespace std;

#define int int64_t

const int INF = 1e18;

vector<pair<int,int>> seg;
vector<int> ans;
vector<int> dpl,dpr;
vector<int> ind;
vector<pair<int,int>> segTree;
vector<int> vis;
vector<int> d;
vector<pair<int,int>> segTree2;
map<int,set<int>> id;

void modify(int i,int x,int l,int r,int indV)
{
    if(l > i || r < i)
        return ;
    else if(l == r)
    {
        segTree[indV] = {x,i};
        return ;
    }
    int m = (l+r)/2;
    modify(i,x,l,m,indV*2+1);
    modify(i,x,m+1,r,indV*2+2);
    segTree[indV] = min(segTree[indV*2+1],segTree[indV*2+2]);
    return ;
}
pair<int,int> get(int lx,int rx,int l,int r,int indV)
{
    if(l > rx || r < lx)
        return {INF,-1};
    else if(l >= lx && r <= rx)
    {
        return segTree[indV];
    }
    int m = (l+r)/2;
    pair<int,int> sl = get(lx,rx,l,m,indV*2+1);
    pair<int,int> sr = get(lx,rx,m+1,r,indV*2+2);
    return min(sl,sr);
}

void modify2(int i,int x,int l,int r,int indV)
{
    if(l > i || r < i)
        return ;
    else if(l == r)
    {
        segTree2[indV] = {x,i};
        return ;
    }
    int m = (l+r)/2;
    modify2(i,x,l,m,indV*2+1);
    modify2(i,x,m+1,r,indV*2+2);
    segTree2[indV] = max(segTree2[indV*2+1],segTree2[indV*2+2]);
    return ;
}
pair<int,int> get2(int lx,int rx,int l,int r,int indV)
{
   // cout << l << ' ' << r << ' ' << segTree2[indV].first << ' ' << segTree2[indV].second << "\n";
    if(l > rx || r < lx)
        return {-1,-1};
    else if(l >= lx && r <= rx)
    {
        return segTree2[indV];
    }
    int m = (l+r)/2;
    pair<int,int> sl = get2(lx,rx,l,m,indV*2+1);
    pair<int,int> sr = get2(lx,rx,m+1,r,indV*2+2);
    return max(sl,sr);
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    seg.resize(n);
    ind.resize(n);
    for(int i = 0;i < n;++i)
    {
        ind[i] = i;
        cin >> seg[i].first >> seg[i].second;
        seg[i].first--;
        seg[i].second--;
    }
    ans.resize(n);
    for(int i = 0;i < n;++i)
        ans[i] = -2;
    dpl.resize(n);
    dpr.resize(n);
    sort(ind.begin(),ind.end(),[&](int a,int b){return seg[a].first < seg[b].first;});
    segTree.resize(4*n);
    for(int i = 0;i < 4*n;++i)
    {
        segTree[i] = {INF,-1};
    }
    for(int i = 0;i < n;++i)
    {
        if(seg[ind[i]].first == 0)
        {
            dpl[ind[i]] = 0;
        }
        else
        {
            dpl[ind[i]] = get(seg[ind[i]].first,seg[ind[i]].second,0,n-1,0).first+1;
        }
        modify(ind[i],dpl[ind[i]],0,n-1,0);
    }
    sort(ind.begin(),ind.end(),[&](int a,int b){return seg[a].second > seg[b].second;});
    segTree.clear();
    segTree.resize(4*n);
    for(int i = 0;i < 4*n;++i)
    {
        segTree[i] = {INF,-1};
    }
    for(int i = 0;i < n;++i)
    {
        if(seg[ind[i]].second == n-1)
        {
            dpr[ind[i]] = 0;
        }
        else
        {
            dpr[ind[i]] = get(seg[ind[i]].first,seg[ind[i]].second,0,n-1,0).first+1;
        }
        modify(ind[i],dpr[ind[i]],0,n-1,0);
    }
    vis.resize(n);
    for(int i = 0;i < n;++i)
    {
        vis[i] = 0;
    }
    d.resize(n);
    //for(int i = 0;i < n;++i)
   // {
   //     cout << dpl[i] << ' ' << dpr[i] << "\n";
   // }
    for(int i = 0;i < n;++i)
        d[i] = dpl[i] + dpr[i];
    segTree.clear();
    segTree.resize(4*n);
    for(int i = 0;i < n;++i)
    {
        modify(i,seg[i].first,0,n-1,0);
    }
    segTree2.resize(4*n);
    for(int i = 0;i < n;++i)
    {
        modify2(i,seg[i].second,0,n-1,0);
    }
    for(int i = 0;i < n;++i)
    {
        id[d[i]].insert(i);
    }
    while(id.size())
    {
        set<int> cc = (*id.begin()).second;
        if(cc.size() == 0)
        {
            id.erase(id.begin());
            continue;

        }

        int td = d[*cc.begin()];
        if(td >= INF)
        {
            break;
        }
        id.erase(id.begin());
        vector<int> t;
        for(auto v:cc)
        {
           // cout << v << ' ';
            if(!vis[v])
            {
                vis[v] = 1;
                modify(v,INF,0,n-1,0);
                modify2(v,-1,0,n-1,0);
            }
            ans[v] = d[v];
            t.push_back(v);
        }
        //cout << "\n";
        int old = 0;
        for(int i = 0;i < t.size();++i)
        {
            while(true)
            {
                pair<int,int> y = get2(old,t[i]-1,0,n-1,0);
                //cout << old << ' ' << t[i] << ' ' << y.first << ' ' << y.second << endl;
                if(y.first < t[i])
                    break;
                vis[y.second] = 1;
                id[d[y.second]].erase(y.second);
                d[y.second] = td+1;
                id[d[y.second]].insert(y.second);
                modify(y.second,INF,0,n-1,0);
                modify2(y.second,-1,0,n-1,0);
            }
            old = t[i]+1;
        }
        old = n-1;
        for(int i = int(t.size())-1;i >= 0;--i)
        {
            while(true)
            {
                //cout << "!";
                pair<int,int> y = get(t[i]+1,old,0,n-1,0);
                if(y.first > t[i])
                    break;
                vis[y.second] = 1;
                id[d[y.second]].erase(y.second);
                d[y.second] = td+1;
                id[d[y.second]].insert(y.second);
                modify(y.second,INF,0,n-1,0);
                modify2(y.second,-1,0,n-1,0);
            }
            old = t[i]-1;
        }

    }
    int q;
    cin >> q;
    while(q--)
    {
        int x;
        cin >> x;
        x--;
        cout << ans[x]+1 << "\n";
    }
    return 0;
}

Compilation message (stderr)

passport.cpp: In function 'int main()':
passport.cpp:193:25: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  193 |         for(int i = 0;i < t.size();++i)
      |                       ~~^~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 8 / 8
• Subtask 5: 46 / 46