oj.uz

Submission #924706

# Submission time Handle Problem Language Result Execution time Memory
924706 2024-02-09T14:08:02 Z ace5 Passport (JOI23_passport) C++17
0 / 100
 637 ms 55732 KB 
#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);
    }
    if(id.size())
    {
        set<int> cc = (*id.begin()).second;
        for(auto v:cc)
        {
            vis[v] = 1;
            modify(v,INF,0,n-1,0);
            modify2(v,-1,0,n-1,0);
        }
    }
    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;
        }
       // cout << td << "\n";
        id.erase(id.begin());
        vector<int> t;
        for(auto v:cc)
        {
           // cout << v << ' ';
            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

passport.cpp: In function 'int main()':
passport.cpp:198: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]
  198 |         for(int i = 0;i < t.size();++i)
      |                       ~~^~~~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 637 ms 55732 KB Output is correct
5 Incorrect 468 ms 49496 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Incorrect 1 ms 348 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Incorrect 1 ms 348 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Incorrect 1 ms 348 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 637 ms 55732 KB Output is correct
5 Incorrect 468 ms 49496 KB Output isn't correct
6 Halted 0 ms 0 KB -