Submission #446868

#	Time	Username	Problem	Language	Result	Execution time	Memory
446868		ivan_tudor	Event Hopping 2 (JOI21_event2)	C++14	100 / 100	299 ms	26296 KiB

event2

#include<bits/stdc++.h>
using namespace std;
const int N = 100005;
struct Intervale{
  int l, r;
  bool operator < (Intervale oth) const{
    return r < oth.r;
  }
};
struct Nodes{
  int h;
  int id;
  Nodes *jump;
  Nodes *par;
};
Nodes *poz[2 * N];
void add_leaf(int dad, int son){
  poz[son] = new Nodes;
  poz[son] ->id = son;
  poz[son]->h = poz[dad]->h + 1;
  poz[son]->par = poz[dad];
  if(poz[dad]->h - poz[dad]->jump->h == poz[dad]->jump->h - poz[dad]->jump->jump->h)
    poz[son]->jump = poz[dad]->jump->jump;
  else
    poz[son]->jump = poz[dad];
}
int longest_subseq(int l, int r){
  Nodes *nod = poz[r];
  int ans = 0;
  while(nod->id >= l && nod->par != NULL){
    if(nod->jump->id >= l){
      ans += nod->h - nod->jump->h;
      nod = nod->jump;
    }
    else{
      nod = nod->par;
      ans ++;
    }
  }
  if(nod ->id < l)
    ans--;
  return ans;
}
Intervale itv[N];
Intervale citv[N];
int main()
{
  //freopen(".in","r",stdin);
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  int n, k;
  cin>>n>>k;
  map<int, int> normal;
  for(int i = 1; i<=n; i++){
    cin>>itv[i].l>>itv[i].r;
    normal[itv[i].l] = 1;
    normal[itv[i].r] = 1;
  }
  int val = 0;
  for(auto &x:normal)
    x.second = ++val;
  for(int i = 1; i <=n; i++){
    itv[i].l = normal[itv[i].l];
    itv[i].r = normal[itv[i].r];
    citv[i] = itv[i];
  }
  sort(itv + 1, itv + n + 1);
  int lpoz = -1;
  int j = 1;
  for(int i = 1; i <= val; i++){
    while(j <=n && itv[j].r == i){
      lpoz = max(lpoz, itv[j].l);
      j++;
    }
    if(lpoz != -1){
      add_leaf(lpoz, i);
    }
    else{
      poz[i] = new Nodes;
      poz[i]->h = 0;
      poz[i]->id = i;
      poz[i]->par = NULL;
      poz[i]->jump = poz[i];
    }
  }
  set<Intervale> free;
  free.insert({1, val});
  vector<int> ans;
  int cur = longest_subseq(1, val);
  for(int i = 1 ; i <= n; i++){
    itv[i] = citv[i];
    if(ans.size() == k)
      break;
    auto itr = free.lower_bound(itv[i]);
    if(itr == free.end())
      continue;
    Intervale found = (*itr);
    if(found.l <= itv[i].l && itv[i].r <= found.r){
      int newcur = cur - longest_subseq(found.l, found.r);
      Intervale st = {found.l, itv[i].l};
      if(st.l < st.r)
        newcur += longest_subseq(st.l, st.r);
      Intervale dr = {itv[i].r, found.r};
      if(dr.l < dr.r)
        newcur += longest_subseq(dr.l, dr.r);
      newcur++;
      if(newcur >= k){
        ans.push_back(i);
        free.erase(found);
        if(st.l < st.r)
          free.insert(st);
        if(dr.l < dr.r)
          free.insert(dr);
        cur = newcur;
      }
    }
  }
  if(ans.size() < k){
    cout<<-1;
    return 0 ;
  }
  for(auto x:ans)
    cout<<x<<"\n";
  return 0;
}

Compilation message (stderr)

event2.cpp: In function 'int main()':
event2.cpp:92:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   92 |     if(ans.size() == k)
      |        ~~~~~~~~~~~^~~~
event2.cpp:118:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  118 |   if(ans.size() < k){
      |      ~~~~~~~~~~~^~~

• Subtask 1: 7 / 7
• Subtask 2: 1 / 1
• Subtask 3: 31 / 31
• Subtask 4: 61 / 61