Submission #1263215

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263215		miniob	Passport (JOI23_passport)	C++20	100 / 100	685 ms	89924 KiB

passport

#include <bits/stdc++.h>
using namespace std;

vector<pair<int, int>> prze;
vector<pair<int, int>> graph[2*524300];
int odl[2*524300];
int sumk[2*524300];
int n;

void dodajp(int l, int r, int curl, int curr, int cur, int jaki)
{
    if(l > curr || r < curl)
    {
        return;
    }
    else if(l <= curl && curr <= r)
    {
        graph[cur].push_back({262143 + jaki, 1});
    }
    else
    {
        dodajp(l, r, curl, (curl + curr) / 2, 2 * cur, jaki);
        dodajp(l, r, (curl + curr) / 2 + 1, curr, 2 * cur + 1, jaki);
    }
}

void djikstra(int skad)
{
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    odl[skad] = 0;
    pq.push({0, skad});
    for(int i = 1; i <= n; i++)
    {
        if(prze[i].first + 262143 <= skad && skad <= prze[i].second + 262143)
        {
            if(odl[262143 + i] > 0)
            {
                odl[262143 + i] = 0;
                pq.push({0, 262143 + i});
            }
        }
    }
    while(!pq.empty())
    {
        auto x = pq.top();
        pq.pop();
        if(odl[x.second] >= x.first) 
        {
            for(auto t : graph[x.second])
            {
                if(odl[t.first] > x.first + t.second)
                {
                    odl[t.first] = x.first + t.second;
                    pq.push({odl[t.first], t.first});
                }
            }
        }
    }
}

int main()
{
    cin >> n;
    for(int i = 2; i <= 524250; i++)
    {
        graph[i].push_back({i / 2, 0});
    }
    prze.push_back({0, 0});
    for(int i = 1; i <= n; i++)
    {
        int l, r;
        cin >> l >> r;
        prze.push_back({l, r});
        dodajp(l, r, 1, 262144, 1, i);
    }
    for(int i = 0; i < 524290; i++)
    {
        odl[i] = 10000000;
    }
    djikstra(262144);
    for(int i = 0; i < 524290; i++)
    {
        sumk[i] += odl[i];
        odl[i] = 10000000;
    }
    djikstra(262143 + n);
    for(int i = 0; i < 524290; i++)
    {
        sumk[i] += odl[i];
        odl[i] = 10000000;
    }
    for(int i = 262144; i < 262144 + n; i++)
    {
        graph[0].push_back({i, min(sumk[i], 10000000)});
    }
    djikstra(0);
    int q;
    cin >> q;
    while(q--)
    {
        int x;
        cin >> x;
        if(odl[262143 + x] >= 10000000)
        {
            cout << -1 << endl;
        }
        else
        {
            cout << odl[262143 + x] + 1 << endl;
        }
    }
    return 0;
}

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