Submission #736891

#	Time	Username	Problem	Language	Result	Execution time	Memory
736891		Cookie	Passport (JOI23_passport)	C++14	48 / 100	991 ms	394596 KiB

passport

#include<bits/stdc++.h>
#include<fstream>
using namespace std;
ifstream fin("WINTER.inp");
ofstream fout("WINTER.out");
 
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
const ld PI = 3.14159265359;
const int x[4] = {1, -1, 0, 0};
const int y[4] = {0, 0, 1, -1};
const ll mod = 1e9 + 7;
const int mxn = 2e5, mxm = 1e5, sq = 400;
const int base = (1 << 18);
const ll inf = 1e9;
const ld pre = 1e-6;
struct th{
    int u, v, w;
};
int n, q;
int l[mxn + 1], r[mxn + 1], d[2505][2505];
vt<th>adj[2505][2505];
void add_edge(int a, int b, int c, int d, int w){
    adj[c][d].pb({a, b, w});
}
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    forr(i, 1, n + 1){
        cin >> l[i] >> r[i];
        forr(j, i, n + 1){
            d[i][j] = 1e9;
        }
    }
    for(int i = 1; i <= n; i++){
        int mnl = 1e9, mxr = -1;
        for(int j = i; j <= n; j++){
            mnl = min(mnl, l[j]); mxr = max(mxr, r[j]);
            if(i == j){
                add_edge(i, j, l[i], r[i], 1);
            }if(i < j){
                add_edge(i, j, i + 1, j, 0); add_edge(i, j, i, j - 1, 0);
            }
            add_edge(i, j, mnl, j, 1); add_edge(i, j, i, mxr, 1);
        }
    }
    d[1][n] = 0;
    deque<pair<int, int>>dq; dq.pb({1, n});
    while(!dq.empty()){
        auto [i, j] = dq.front(); dq.pop_front();
        for(auto [x, y, w]: adj[i][j]){
            if(d[x][y] > d[i][j] + w){
                d[x][y] = d[i][j] + w;
                if(w){
                    dq.pb({x, y});
                }else{
                    dq.push_front({x, y});
                }
            }
        }
    }
    cin >> q;
    forr(i, 0, q){
        int x; cin >> x;
        if(d[x][x] == 1e9)cout << -1 << "\n";
        else cout << d[x][x] << "\n";
    }
    return(0);
}

Compilation message (stderr)

passport.cpp: In function 'int main()':
passport.cpp:60:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   60 |         auto [i, j] = dq.front(); dq.pop_front();
      |              ^
passport.cpp:61:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   61 |         for(auto [x, y, w]: adj[i][j]){
      |                  ^

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