oj.uz

Submission #853462

# Submission time Handle Problem Language Result Execution time Memory
853462 2023-09-24T11:50:48 Z vjudge1 Event Hopping (BOI22_events) C++17
20 / 100
 311 ms 96020 KB 
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;

#define int long long
#define f first
#define s second
#define ii pair<int,int>
#define vi vector<int>
#define vvi vector<vi>
#define vvii vector<vector<ii>>
#define pb push_back
#define vpi vector<ii> 
#define forcin for(int i = 0; i<n; ++i) cin>>v[i];
#define ld long double
#define all(a) (a).begin(),(a).end()
#define For(i, n, x) for (int i = x; i < n; i++)
#define rsz(a,x) assign(a,x)
const int MAXN = 1e5+5;
vvii table(MAXN,vpi(25,{0,0}));
struct Segment{
  int s,e,idx;
};

 
ii query(int l,int r){
 
  int len = r-l+1;
  int k = 31- __builtin_clz(len);
  return max(table[l][k], table[r-(1<<k)+1][k]);
}
 

bool cmp(Segment a, Segment b){
  if(a.s == b.s) return a.e <= b.e;
  return a.s < b.s;
}

bool cmp1(Segment a, Segment b){
  if(a.s == b.s) return a.e > b.e;
  return a.s < b.s;
}

signed main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n,q; cin>>n>>q;
  vector<Segment> v(n);
  vpi start;
  For(i,n,0){
    int s,e; cin>>s>>e;
    v[i].s = s; v[i].e = e; v[i].idx = i;
    start.pb({s,i});
  }
  sort(all(v),cmp);
  vi idxs(n+1);
  vvi jump(n+1,vi(25,n));  
  For(i,n,0) table[i][0] = {v[i].e,i};
    For(k,25,1){
        for(int i = 0; i+ (1<<k) -1< n; i++){
            int x = i+(1<<(k-1));
            if(table[i][k-1].f == table[x][k-1].f) table[i][k] = min(table[i][k-1],table[x][k-1]);
            else table[i][k] = max(table[i][k-1],table[x][k-1]);
 
        }
 
    }
  For(i,n,0){
    
    Segment S; S.s = v[i].e; S.e = 1e9; S.idx = 1e9;
    int idx = (upper_bound(all(v),S,cmp) - v.begin());
    idx--;
    //cerr<<i<<" "<<idx<<" "<<S.s<<" "<<S.e<<" "<<S.idx<<" "<<v[idx].s<<" "<<v[idx].e<<" "<<v[idx].idx<<endl;
    /*if(idx == i){
      jump[v[i].idx][0] = 0; continue;
    }*/
    ii p = query(0,idx);
    if(p.s == i) jump[i][0] = n; 
    else jump[i][0] = p.s;
  }
  //Build Binary Lifting
  For(k,25,1){
    For(i,n,0){
      jump[i][k] = jump[jump[i][k-1]][k-1];
      if(jump[i][k] == i || jump[i][k] == jump[i][k-1]) jump[i][k] = n;
    }
  }
  For(i,n,0) idxs[v[i].idx] = i;
  /*For(i,n,0){
    cerr<<i<<" "<<v[i].s<<" "<<v[i].e<<" "<<v[i].idx<<endl;
    cerr<<jump[i][0]<<" "<<jump[i][1]<<" "<<jump[i][2]<<endl<<endl;
  }*/
  while(q--){
    int s,e; cin>>s>>e; s--,e--;s = idxs[s]; e = idxs[e];
    if(s == e){
      cout<<0<<endl; continue;
    }
    //cerr<<s<<" "<<e<<" ";
    int ans = 0;
    for(int i = 24; i>=0; i--){
      if(jump[s][i] != n && jump[s][i] < e){
        s = jump[s][i];
        ans+=(1ll<<i);
      }
    }
   //cerr<<"ANS "<<s<<" "<<jump[s][0]<<" "<<e<<endl;
    if(max(e,s) ==n || !(v[e].s <= v[s].e && v[s].e <= v[e].e)) cout<<"impossible"<<endl;
    else cout<<ans+1<<endl;
  }

}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 43296 KB Output is correct
2 Correct 233 ms 71268 KB Output is correct
3 Correct 252 ms 71360 KB Output is correct
4 Correct 248 ms 71708 KB Output is correct
5 Correct 245 ms 71464 KB Output is correct
6 Correct 232 ms 71364 KB Output is correct
7 Correct 246 ms 71752 KB Output is correct
8 Correct 225 ms 71860 KB Output is correct
9 Correct 220 ms 71928 KB Output is correct
10 Correct 283 ms 71788 KB Output is correct
11 Correct 282 ms 71868 KB Output is correct
12 Runtime error 79 ms 96020 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 43396 KB Output is correct
2 Correct 23 ms 43356 KB Output is correct
3 Correct 23 ms 43800 KB Output is correct
4 Correct 22 ms 43612 KB Output is correct
5 Incorrect 23 ms 43612 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 43396 KB Output is correct
2 Correct 23 ms 43356 KB Output is correct
3 Correct 23 ms 43800 KB Output is correct
4 Correct 22 ms 43612 KB Output is correct
5 Incorrect 23 ms 43612 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 43396 KB Output is correct
2 Correct 23 ms 43356 KB Output is correct
3 Correct 23 ms 43800 KB Output is correct
4 Correct 22 ms 43612 KB Output is correct
5 Incorrect 23 ms 43612 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 71752 KB Output is correct
2 Correct 238 ms 71516 KB Output is correct
3 Correct 246 ms 71364 KB Output is correct
4 Correct 221 ms 71872 KB Output is correct
5 Correct 269 ms 71792 KB Output is correct
6 Correct 311 ms 71616 KB Output is correct
7 Correct 279 ms 71612 KB Output is correct
8 Correct 259 ms 71672 KB Output is correct
9 Correct 94 ms 71116 KB Output is correct
10 Correct 222 ms 71204 KB Output is correct
11 Correct 222 ms 71040 KB Output is correct
12 Correct 237 ms 71236 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 43296 KB Output is correct
2 Correct 233 ms 71268 KB Output is correct
3 Correct 252 ms 71360 KB Output is correct
4 Correct 248 ms 71708 KB Output is correct
5 Correct 245 ms 71464 KB Output is correct
6 Correct 232 ms 71364 KB Output is correct
7 Correct 246 ms 71752 KB Output is correct
8 Correct 225 ms 71860 KB Output is correct
9 Correct 220 ms 71928 KB Output is correct
10 Correct 283 ms 71788 KB Output is correct
11 Correct 282 ms 71868 KB Output is correct
12 Runtime error 79 ms 96020 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -