oj.uz

Submission #855135

# Submission time Handle Problem Language Result Execution time Memory
855135 2023-09-30T09:50:20 Z Litusiano Event Hopping (BOI22_events) C++17
20 / 100
 253 ms 42948 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 min(table[l][k], table[r-(1<<k)+1][k]);
}
 


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

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({e,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].s,i};
    For(k,25,1){
        for(int i = 0; i+ (1<<k) -1< n; i++){
            int x = i+(1<<(k-1));
            table[i][k] = min(table[i][k-1],table[x][k-1]);
 
        }
 
    }
  For(i,n,0){
    Segment S; S.s = v[i].s; S.e = 1e9; S.idx = 1e9;
    int l = 0; int r = n;
    while(r > l+1){
      int m = (l+r)/2;
      if(v[m].e >= v[i].s) l = m;
      else r = m;
    }
    int idx = l;
    //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;
    }*/
    //cerr<<"IDX "<<idx<<" "<<i<<endl;
    if(i >= idx) {
      jump[i][0] = n; continue;
    }
    ii p = query(i,idx);
    //cerr<<"IDX "<<v[i].s<<" "<<v[i].e<<" "<<idx<<" "<<i<<" "<<p.f<<" "<<p.s<<endl;
    if(p.s == i){
      if(i != 0) p = query(i+1,idx);
    }
    if(p.s != i) 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--; swap(s,e);
    if(s == e){
      cout<<0<<endl; continue;
    }
    s = idxs[s]; e = idxs[e];
    //cerr<<s<<" "<<e<<endl;
    if(s > e){
      cout<<"impossible"<<endl; continue;
    }
    int ans = 0;
    for(int i = 24; i>=0; i--){
      if(jump[s][i] < e){
        s = jump[s][i];
        ans+=(1ll<<i);
      }
    }
    //cerr<<"ANS "<<s<<" "<<jump[s][0]<<" "<<e<<" "<<v[e].s<<" "<<v[s].e<<" "<<v[e].e<<endl;
    if(s == e){
      cout<<ans<<endl; continue;
    }
    ans++; s = jump[s][0];
    if(!(v[e].s <= v[s].e && v[s].e <= v[e].e)) cout<<"impossible"<<endl;
    else cout<<ans<<endl;
  }

}

Compilation message

events.cpp: In function 'int main()':
events.cpp:64:13: warning: variable 'S' set but not used [-Wunused-but-set-variable]
   64 |     Segment S; S.s = v[i].s; S.e = 1e9; S.idx = 1e9;
      |             ^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 23132 KB Output is correct
2 Correct 204 ms 42316 KB Output is correct
3 Correct 201 ms 42336 KB Output is correct
4 Correct 209 ms 42504 KB Output is correct
5 Incorrect 220 ms 42680 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23176 KB Output is correct
2 Correct 13 ms 23128 KB Output is correct
3 Correct 14 ms 23168 KB Output is correct
4 Correct 14 ms 23128 KB Output is correct
5 Correct 14 ms 23132 KB Output is correct
6 Incorrect 14 ms 23132 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23176 KB Output is correct
2 Correct 13 ms 23128 KB Output is correct
3 Correct 14 ms 23168 KB Output is correct
4 Correct 14 ms 23128 KB Output is correct
5 Correct 14 ms 23132 KB Output is correct
6 Incorrect 14 ms 23132 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23176 KB Output is correct
2 Correct 13 ms 23128 KB Output is correct
3 Correct 14 ms 23168 KB Output is correct
4 Correct 14 ms 23128 KB Output is correct
5 Correct 14 ms 23132 KB Output is correct
6 Incorrect 14 ms 23132 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 42524 KB Output is correct
2 Correct 201 ms 42524 KB Output is correct
3 Correct 228 ms 42264 KB Output is correct
4 Correct 220 ms 42828 KB Output is correct
5 Correct 234 ms 42696 KB Output is correct
6 Correct 253 ms 42948 KB Output is correct
7 Correct 240 ms 42696 KB Output is correct
8 Correct 214 ms 42596 KB Output is correct
9 Correct 68 ms 40708 KB Output is correct
10 Correct 198 ms 42180 KB Output is correct
11 Correct 196 ms 41924 KB Output is correct
12 Correct 202 ms 42528 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 23132 KB Output is correct
2 Correct 204 ms 42316 KB Output is correct
3 Correct 201 ms 42336 KB Output is correct
4 Correct 209 ms 42504 KB Output is correct
5 Incorrect 220 ms 42680 KB Output isn't correct
6 Halted 0 ms 0 KB -