Submission #1109269

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109269		Neco_arc	Passport (JOI23_passport)	C++17	100 / 100	596 ms	27136 KiB

passport

#include <bits/stdc++.h>

#define ll long long
#define name "Tickets"
#define _left id * 2, l, mid
#define _right id * 2 + 1, mid + 1, r
#define fi(i, a, b)  for(int i = a; i <= b; ++i)
#define fid(i, a, b) for(int i = a; i >= b; --i)
#define maxn (int) (2e5 + 7)

using namespace std;

int n, k;
struct dl { int c, w, l, r; } a[maxn];
ll dist[3][2 * maxn];

struct IT {
    int st[4 * maxn];

    void build(int id = 1, int l = 1, int r = k) {
        if(l == r) return st[id] = a[l].r, void();
        int mid = (l + r) >> 1;
        build(_left), build(_right);

        st[id] = max(st[id * 2], st[id * 2 + 1]);
    }

    void get(int x, vector<int> &P, int id = 1, int l = 1, int r = k) {
        if(a[l].l > x || st[id] < x) return;
        if(l == r) {
            P.push_back(l), st[id] = -1;
            return ;
        }

        int mid = (l + r) >> 1;
        get(x, P, _left), get(x, P, _right);

        st[id] = max(st[id * 2], st[id * 2 + 1]);
    }

} St;

void DJK(ll *dist) {
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>> > q;
    fi(i, 1, k) { /// corner case
        dist[a[i].c] = min(dist[a[i].c], dist[n + i] + a[i].w);
    }

    St.build();
    fi(i, 1, n) if(dist[i] < 1e18) q.push({dist[i], i});

    while(!q.empty()) {
        int u; ll g; tie(g, u) = q.top(); q.pop();
        if(dist[u] < g) continue;

        vector<int> P; St.get(u, P);

        for(int x : P) {
            dist[x + n] = dist[u];
            if(dist[a[x].c] > dist[x + n] + a[x].w) {
                dist[a[x].c] = dist[x + n] + a[x].w;
                q.push({ dist[a[x].c], a[x].c });
            }
        }
    }

}

void solve() {

    cin >> n ; k = n;

    fi(i, 1, k) {
        a[i].c = i, a[i].w = 1;
        cin >> a[i].l >> a[i].r;
    }

    sort(a + 1, a + 1 + k, [](dl x, dl y) {
        return x.l < y.l;
    });


    memset(dist, 60, sizeof dist);
    dist[0][1] = dist[1][n] = 0;

    DJK(dist[0]), DJK(dist[1]);

    fi(i, 1, n + k) dist[2][i] = dist[0][i] + dist[1][i];
    DJK(dist[2]);

    int q; cin >> q;
    fi(_, 1, q) {
        int i; cin >> i;
        cout << (dist[2][i] < 1e18 ? dist[2][i] : -1) << '\n';
    }

}

int main() {

    ios_base::sync_with_stdio();
    cin.tie(), cout.tie();

    if(fopen(name".inp", "r")) {
        freopen(name".inp", "r", stdin);
        freopen(name".out", "w", stdout);
    }

    solve();

}

Compilation message (stderr)

passport.cpp: In function 'int main()':
passport.cpp:105:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |         freopen(name".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
passport.cpp:106:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |         freopen(name".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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