oj.uz

Submission #885540

# Submission time Handle Problem Language Result Execution time Memory
885540 2023-12-10T03:03:23 Z huutuan Passport (JOI23_passport) C++14
6 / 100
 762 ms 654776 KB 
#include<bits/stdc++.h>

using namespace std;

#define int long long
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define isz(x) ((int)(x).size())
#define sumof(x) accumulate(all(x), 0ll)

const int N=2e5+1;
int n, pos[N], dist[3][N*4];
vector<pair<int, int>> g[N*4];
queue<int> q[N*4];

void build(int k, int l, int r){
   if (l==r){
      pos[l]=k;
      return;
   }
   int mid=(l+r)>>1;
   build(k<<1, l, mid);
   build(k<<1|1, mid+1, r);
   g[k<<1].emplace_back(k, 0);
   g[k<<1|1].emplace_back(k, 0);
}

void update(int k, int l, int r, int L, int R, int u){
   if (r<L || R<l) return;
   if (L<=l && r<=R){
      g[k].emplace_back(pos[u], 1);
      return;
   }
   int mid=(l+r)>>1;
   update(k<<1, l, mid, L, R, u);
   update(k<<1|1, mid+1, r, L, R, u);
}

void bfs(int t){
   for (int i=1; i<=n*4; ++i) if (dist[t][i]<1e9) q[dist[t][i]].push(i);
   for (int i=0; i<=n*4; ++i){
      while (q[i].size()){
         int u=q[i].front(); q[i].pop();
         if (dist[t][u]!=i) continue;
         for (auto &e:g[u]){
            int v=e.first, w=e.second;
            if (dist[t][v]>dist[t][u]+w) q[dist[t][v]=dist[t][u]+w].push(v);
         }
      }
   }
}

void solve(){
   cin >> n;
   build(1, 1, n);
   for (int i=1; i<=n; ++i){
      int l, r; cin >> l >> r;
      
      update(1, 1, n, l, r, i);
   }
   memset(dist, 0x3f, sizeof dist);
   dist[0][pos[1]]=0;
   dist[1][pos[n]]=0;
   bfs(0);
   bfs(1);
   for (int i=1; i<=n*4; ++i) dist[2][i]=dist[0][i]+dist[1][i];
   bfs(2);
   int tc; cin >> tc;
   while (tc--){
      int x; cin >> x; x=pos[x];
      cout << (dist[2][x]<1e9?dist[2][x]:-1) << '\n';
   }
}

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   int ntests=1;
   // cin >> ntests;
   for (int i=1; i<=ntests; ++i) solve();
   return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 377 ms 577092 KB Output is correct
2 Correct 265 ms 577092 KB Output is correct
3 Correct 281 ms 577096 KB Output is correct
4 Correct 762 ms 654776 KB Output is correct
5 Correct 547 ms 614480 KB Output is correct
6 Correct 461 ms 604244 KB Output is correct
7 Correct 380 ms 599888 KB Output is correct
8 Correct 382 ms 612080 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 576848 KB Output is correct
2 Correct 267 ms 577108 KB Output is correct
3 Correct 262 ms 576852 KB Output is correct
4 Correct 255 ms 577076 KB Output is correct
5 Correct 257 ms 577060 KB Output is correct
6 Correct 265 ms 576848 KB Output is correct
7 Correct 253 ms 577100 KB Output is correct
8 Incorrect 254 ms 576928 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 576848 KB Output is correct
2 Correct 267 ms 577108 KB Output is correct
3 Correct 262 ms 576852 KB Output is correct
4 Correct 255 ms 577076 KB Output is correct
5 Correct 257 ms 577060 KB Output is correct
6 Correct 265 ms 576848 KB Output is correct
7 Correct 253 ms 577100 KB Output is correct
8 Incorrect 254 ms 576928 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 576848 KB Output is correct
2 Correct 267 ms 577108 KB Output is correct
3 Correct 262 ms 576852 KB Output is correct
4 Correct 255 ms 577076 KB Output is correct
5 Correct 257 ms 577060 KB Output is correct
6 Correct 265 ms 576848 KB Output is correct
7 Correct 253 ms 577100 KB Output is correct
8 Incorrect 254 ms 576928 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 377 ms 577092 KB Output is correct
2 Correct 265 ms 577092 KB Output is correct
3 Correct 281 ms 577096 KB Output is correct
4 Correct 762 ms 654776 KB Output is correct
5 Correct 547 ms 614480 KB Output is correct
6 Correct 461 ms 604244 KB Output is correct
7 Correct 380 ms 599888 KB Output is correct
8 Correct 382 ms 612080 KB Output is correct
9 Correct 263 ms 576848 KB Output is correct
10 Correct 267 ms 577108 KB Output is correct
11 Correct 262 ms 576852 KB Output is correct
12 Correct 255 ms 577076 KB Output is correct
13 Correct 257 ms 577060 KB Output is correct
14 Correct 265 ms 576848 KB Output is correct
15 Correct 253 ms 577100 KB Output is correct
16 Incorrect 254 ms 576928 KB Output isn't correct
17 Halted 0 ms 0 KB -