oj.uz

Submission #883856

# Submission time Handle Problem Language Result Execution time Memory
883856 2023-12-06T08:08:30 Z vjudge1 Passport (JOI23_passport) C++17
6 / 100
 1750 ms 123736 KB 
/* Author : Mychecksdead  */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
const int N = 8e5+100, M = 1e5+10, K = 21;
 
struct Data{
  int L, R;
};
 
int n, q, L[N][K], R[N][K];
Data up[N][K];
 
void build(int l, int r, int k, int bit){
  if(l == r){
    L[k][bit] = up[l][bit].L;
    R[k][bit] = up[l][bit].R;
    return;
  }
  int mid = l+r>>1;
  build(l, mid, k<<1, bit);
  build(mid+1, r, k<<1|1, bit);
  L[k][bit] = min(L[k<<1][bit], L[k<<1|1][bit]);
  R[k][bit] = max(R[k<<1][bit], R[k<<1|1][bit]);
}


 
int getL(int l, int r, int ql, int qr, int k, int bit){
  if(ql > r || l > qr) return MOD;
  if(ql <= l && r <= qr) return L[k][bit];
  int mid = l+r>>1;
  return min(getL(l, mid, ql, qr, k<<1, bit), getL(mid+1, r, ql, qr, k<<1|1, bit));
}
int getR(int l, int r, int ql, int qr, int k, int bit){
  if(ql > r || l > qr) return 0;
  if(ql <= l && r <= qr) return R[k][bit];
  int mid = l+r>>1;
  return max(getR(l, mid, ql, qr, k<<1, bit), getR(mid+1, r, ql, qr, k<<1|1, bit));
}
 
void solve(){
  cin >> n;
  for(int i = 1; i <= n; ++i){
    int l, r; cin >> l >> r;
    up[i][0] = {l, r};
  }
  build(1, n, 1, 0);
  for(int j = 1; j < K; ++j){
    for(int i = 1; i <= n; ++i){
      up[i][j] = {getL(1, n, up[i][j - 1].L, up[i][j - 1].R, 1, j - 1), getR(1, n, up[i][j - 1].L, up[i][j - 1].R, 1, j - 1)};
    }
    build(1, n, 1, j);
  }
  cin >> q;
  for(int i = 1; i <= q; ++i){
    int l; cin >> l;
    Data x = up[l][0];
    bool ok = 0;
    int ans = 1;
    for(int j = K - 1; j >= 0; --j){
      Data u = {getL(1, n, x.L, x.R, 1, j), getR(1, n, x.L, x.R, 1, j)};
      if(u.L == 1 && u.R == n){
        ok = 1;
      }else{
        x = u;
        ans += (1<<j);
      }
      // cout << x.L << ' ' << x.R << '\n';
    }
    if(!ok) cout << "-1\n";
    else{
      Data u = {getL(1, n, x.L, x.R, 1, 0), getR(1, n, x.L, x.R, 1, 0)};
      assert(u.L == 1 && u.R == n);
      if(x.L == 1 && x.R == n){
        cout << ans << '\n';
        continue;
      }
      cout << ans + 1 << '\n';
    }
  }
}
 
 
int main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tt = 1, aa;
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  while(tt--){
    solve();
  }
  cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
  return 0;
}

Compilation message

passport.cpp: In function 'void build(int, int, int, int)':
passport.cpp:25:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   25 |   int mid = l+r>>1;
      |             ~^~
passport.cpp: In function 'int getL(int, int, int, int, int, int)':
passport.cpp:37:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |   int mid = l+r>>1;
      |             ~^~
passport.cpp: In function 'int getR(int, int, int, int, int, int)':
passport.cpp:43:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |   int mid = l+r>>1;
      |             ~^~
passport.cpp: In function 'int main()':
passport.cpp:92:15: warning: unused variable 'aa' [-Wunused-variable]
   92 |   int tt = 1, aa;
      |               ^~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 491 ms 123716 KB Output is correct
5 Correct 1253 ms 123736 KB Output is correct
6 Correct 1750 ms 123732 KB Output is correct
7 Correct 237 ms 123728 KB Output is correct
8 Correct 757 ms 117584 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4440 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4696 KB Output is correct
7 Incorrect 1 ms 4444 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4440 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4696 KB Output is correct
7 Incorrect 1 ms 4444 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4440 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4696 KB Output is correct
7 Incorrect 1 ms 4444 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 491 ms 123716 KB Output is correct
5 Correct 1253 ms 123736 KB Output is correct
6 Correct 1750 ms 123732 KB Output is correct
7 Correct 237 ms 123728 KB Output is correct
8 Correct 757 ms 117584 KB Output is correct
9 Correct 1 ms 4440 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 1 ms 4440 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 1 ms 4696 KB Output is correct
15 Incorrect 1 ms 4444 KB Output isn't correct
16 Halted 0 ms 0 KB -