Submission #887560

#	Time	Username	Problem	Language	Result	Execution time	Memory
887560		andrei_iorgulescu	Passport (JOI23_passport)	C++14	100 / 100	731 ms	121720 KiB

passport

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int inf = 1e18;

struct muchie
{
    int x,y,z;///teoretic de la x pe [y z]
    int c;///costul
};

int n,q;
muchie e[200005];
vector<muchie> v[200005];
int rmq1[200005][20],rmqn[200005][20];
int lg[200005];

int query1(int l,int r)
{
    int lgg = lg[r - l + 1];
    return min(rmq1[l][lgg],rmq1[r - (1 << lgg) + 1][lgg]);
}

int queryn(int l,int r)
{
    int lgg = lg[r - l + 1];
    return min(rmqn[l][lgg],rmqn[r - (1 << lgg) + 1][lgg]);
}

bool cmp(muchie A,muchie B)
{
    return A.y < B.y;
}

pair<int,int> aint[800005];

void build(int nod,int l,int r)
{
    if (l == r)
    {
        aint[nod] = {e[l].z,l};
    }
    else
    {
        int mij = (l + r) / 2;
        build(2 * nod,l,mij);
        build(2 * nod + 1,mij + 1,r);
        aint[nod] = max(aint[2 * nod],aint[2 * nod + 1]);
    }
}

void update(int nod,int l,int r,int pos)
{
    if (l == r)
    {
        aint[nod] = {-1,-1};
    }
    else
    {
        int mij = (l + r) / 2;
        if (pos <= mij)
            update(2 * nod,l,mij,pos);
        else
            update(2 * nod + 1,mij + 1,r,pos);
        aint[nod] = max(aint[2 * nod],aint[2 * nod + 1]);
    }
}

pair<int,int> query(int nod,int l,int r,int st,int dr)
{
    if (dr < l or r < st)
        return {-1,-1};
    if (st <= l and r <= dr)
        return aint[nod];
    int mij = (l + r) / 2;
    return max(query(2 * nod,l,mij,st,dr),query(2 * nod + 1,mij + 1,r,st,dr));
}

void dijkstra_nebun(vector<int> &fin, vector<int> dinit)
{
    for (int i = 1; i <= n; i++)
        fin[i] = 4 * inf;
    ///ok so basically, vreau sa iau muchiile care il contin pe nod in [y z] si sa bag muchia inversa pana in x etc
    ///ca sa fac asta (desi aproape ma pot jura ca se poate mai simplu) sortez muchiile dupa y, tin un aint si iau aia cu max_z
    sort(e + 1,e + q + 1,cmp);
    build(1,1,q);
    priority_queue<pair<int,int>>pq;
    for (int i = 1; i <= n; i++)
        pq.push({-dinit[i],i});
    while (!pq.empty())
    {
        int nod = pq.top().second;
        int cst = -pq.top().first;
        pq.pop();
        if (cst >= fin[nod])
            continue;
        fin[nod] = cst;
        int st = 0,pas = 1 << 17;
        while (pas != 0)
        {
            if (st + pas <= q and e[st + pas].y <= nod)
                st += pas;
            pas /= 2;
        }
        while (true)
        {
            if (st == 0)
                break;
            pair<int,int> qr = query(1,1,q,1,st);
            if (qr.first < nod)
                break;
            pq.push({-(fin[nod] + e[qr.second].c),e[qr.second].x});
            update(1,1,q,qr.second);
        }
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n;
    q = n;
    for (int i = 1; i <= n; i++)
    {
        /*
        int x1,x2,x3,x4;
        cin >> x1 >> x2 >> x3 >> x4;
        muchie aux;
        aux.c = x2;
        aux.x = x1;
        aux.y = x3;
        aux.z = x4;
        e[i] = aux;
        v[x1].push_back(aux);*/
        int l,r;
        cin >> l >> r;
        muchie aux;
        aux.c = 1;
        aux.x = i;
        aux.y = l;
        aux.z = r;
        e[i] = aux;
        v[i].push_back(aux);
    }
    vector<int>d1(n + 1),dn(n + 1),cost(n + 1),ans(n + 1);
    vector<int>initial(n + 1);
    initial[1] = 0;
    for (int i = 2; i <= n; i++)
        initial[i] = inf;
    dijkstra_nebun(d1,initial);
    initial[1] = inf;
    initial[n] = 0;
    dijkstra_nebun(dn,initial);
    for (int i = 2; i <= n; i++)
        lg[i] = 1 + lg[i / 2];
    for (int i = 1; i <= n; i++)
        rmq1[i][0] = d1[i],rmqn[i][0] = dn[i];
    for (int j = 1; j <= lg[n]; j++)
    {
        for (int i = 1; i <= n - (1 << j) + 1; i++)
        {
            rmq1[i][j] = min(rmq1[i][j - 1],rmq1[i + (1 << (j - 1))][j - 1]);
            rmqn[i][j] = min(rmqn[i][j - 1],rmqn[i + (1 << (j - 1))][j - 1]);
        }
    }
    for (int i = 1; i <= n; i++)
    {
        cost[i] = d1[i] + dn[i];
        for (auto it : v[i])
        {
            cost[i] = min(cost[i],it.c + query1(it.y,it.z) + queryn(it.y,it.z));
        }
    }
    for (int i = 1; i <= n; i++)
        initial[i] = cost[i];
    dijkstra_nebun(ans,initial);
    int q;
    cin >> q;
    for (int i = 1; i <= q; i++)
    {
        int x;
        cin >> x;
        if (ans[x] >= inf)
            cout << -1 << '\n';
        else
            cout << ans[x] << '\n';
    }
    return 0;
}

/**
ce insane
deci vreau sa calculez cost[i] = costul din i daca el e punctul de articulatie (xt)
cost[i] = min(d1[i] + dn[i],c[k] + min(d1[j]) + min(dn[j]) cu k o muchie din i, j intre l[k] si r[k])
adica daca imi calculez cost[i] pentru fiecare nod, apoi am doar un rmq sau cv
apoi, pentru fiecare x, vreau minimul din dist(x,i) + cost[i], adica un dijkstra in care nodul i in care offset dist[i]
doamne ajuta cu impl
**/

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