Submission #888888

#	Time	Username	Problem	Language	Result	Execution time	Memory
888888		Nurislam	Passport (JOI23_passport)	C++14	22 / 100	2076 ms	205152 KiB

passport

/*

author : abushbandit
contest : ---

*/

#include "bits/stdc++.h"

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;

using namespace std;

#define int long long
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define ff first
#define ss second
#define pb push_back
#define rep(i,s,f) for(int i = s;i < f;i++)

#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

#pragma GCC optimize("Ofast,no-stack-protector,fast-math",3)

template <class type1>
  using ordered_multiset = tree <type1, null_type, less_equal <type1>, rb_tree_tag, tree_order_statistics_node_update>;

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<pair<int,int>> vii;
typedef pair<int,int> pii;

const ll INF = 1e18;
const ll MOD7 = 1e9 + 7;
const ll MOD9 = 998244353;
const ld PI = acos(-1.0);
const int N = 1e5 + 6;

template <class F, class _S>
bool chmin(F &u, const _S &v){
    bool flag = false;
    if ( u > v ){
        u = v; flag |= true;
    }
    return flag;
}

template <class F, class _S>
bool chmax(F &u, const _S &v){
    bool flag = false;
    if ( u < v ){
        u = v; flag |= true;
    }
    return flag;
    
}

int binpow (int a, int n) {
  int res = 1;
  while (n) {
    if (n & 1)
      res *= a;
    a *= a;
    n >>= 1;
  }
  return res;
}

void start_file(string file){
  freopen((file + ".in").c_str(),"r",stdin);
  freopen((file + ".out").c_str(),"w",stdout);
}

void solve(int tc){
  
  int n;
  cin >> n;
  vector<pair<int,int>> a(n + 1);
  for(int i = 1;i <= n;i++){
    int l,r;
    cin >> l >> r;
    a[i] = {l,r};
  }
  
   
    int q;
  cin >> q;
  for(int i = 0;i < q;i++){
        int x;
        cin >> x;
        if(x == 1){
          
          int i = 1,lst = a[1].ss,cnt = 0;
          bool check = 0;
          while(true){
            cnt++;
            int mx = 0;
            while(i <= n && i <= lst){
              mx = max(mx,a[i].ss);
              i++;
        }
        if(i > n){
          break;
        } else if(lst < mx){
          lst = mx;
        } else{
          check = 1;
          break;
        }
      }
          
          if(check){
            cout << -1 << "\n";
      } else{
        cout << cnt << "\n";
      }
          
          break;
          
    } else{
      vector<vector<int>> dis(n + 1, vector<int> (n + 1,INF));
          vector<vector<int>> vis(n + 1, vector<int> (n + 1,0));
   
          set<vector<int>> st;
          dis[a[x].ff][a[x].ss] = 1;
           st.insert({1,a[x].ff,a[x].ss});
          while(!st.empty()){
              int l = (*st.begin())[1], r = (*st.begin())[2];
              st.erase(st.begin());
              if(vis[l][r])continue;
              vis[l][r] = 1;
              for(int i = l;i <= r;i++){
                  for(int j = r;j <= max(r,a[i].ss);j++){
                      for(int k = l;k >= min(l,a[i].ff);k--){
                          if(dis[l][r] + 1 < dis[k][j]){
                              st.insert({dis[l][r] + 1,k,j});
                              dis[k][j] = dis[l][r] + 1;
                          }
                      }
                  }
              }
          }
          if(dis[1][n] == INF){
            cout << "-1\n";
      } else{
        cout << dis[1][n] << "\n";
      }
    }
          
    }
  
}

signed main(){

//  start_file("");

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

  int test_cases = 1;
//  cin >> test_cases ;
  for(int tc = 1;tc <= test_cases;++ tc){
    solve(tc);
  }  

}

/*



*/

Compilation message (stderr)

passport.cpp: In function 'void start_file(std::string)':
passport.cpp:75:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |   freopen((file + ".in").c_str(),"r",stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
passport.cpp:76:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |   freopen((file + ".out").c_str(),"w",stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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