Submission #417196

#	Time	Username	Problem	Language	Result	Execution time	Memory
417196		tqbfjotld	Event Hopping 2 (JOI21_event2)	C++14	100 / 100	166 ms	14668 KiB

event2

#include <bits/stdc++.h>
using namespace std;

int decomp[100005][20];
vector<pair<int,int> > stuff;
vector<pair<pair<int,int>,int> > sorted;
int pos[100005];

int point(int cur, int amt){
    for (int x = 0; x<20; x++){
        if (amt&(1<<x)){
            cur = decomp[cur][x];
        }
    }
    return cur;
}

int main(){
    int n,k;
    scanf("%d%d",&n,&k);
    for (int x = 0; x<n; x++){
        int a,b;
        scanf("%d%d",&a,&b);
        stuff.push_back({a,b});
        sorted.push_back({{a,b},x});
    }
    sorted.push_back({{1000000000,1000000001},n});
    sort(sorted.begin(),sorted.end());
    decomp[n][0] = n+1;
    decomp[n+1][0] = n+1;
    for (int x = n-1; x>=0; x--){
        decomp[x][0] = lower_bound(sorted.begin(),sorted.end(),make_pair(make_pair(sorted[x].first.second,-1),-1))-sorted.begin();
        decomp[x][0] = min(decomp[x][0],decomp[x+1][0]);
    }
    for (int x = 1; x<20; x++){
        for (int y = 0; y<=n+1; y++){
            decomp[y][x] = decomp[decomp[y][x-1]][x-1];
        }
    }
    if (point(0,k)>n){
        printf("-1");
        return 0;
    }
    for (int x = 0; x<n; x++){
        pos[sorted[x].second]=x;
    }
    vector<int> ans;
    set<pair<int,int> > rem;
    int curans = 0;
    int cur = 0;
    for (int y = 19; y>=0; y--){
        if (decomp[cur][y]<=n){
            cur = decomp[cur][y];
            curans += (1<<y);
        }
    }
    rem.insert({0,n});
    for (int x = 0; x<n; x++){
        if (ans.size()==k) break;
       // for (auto x : rem) printf("(%d,%d) ",x);
       // printf("\n");
        auto it = rem.lower_bound({pos[x]+1,-1});
        if (it==rem.begin()) continue;
        it--;
      //  printf("cur interval = %d, %d\n",(*it));
      //  printf("also %d %d\n",sorted[(*it).first].first.first,sorted[(*it).second].first.first);
        if (sorted[(*it).first].first.first>stuff[x].first || sorted[(*it).second].first.first<stuff[x].second) continue;
      //  printf("hi\n");
        int st = (*it).first;
        int en = (*it).second;
        int ans1 = 0;
        int cur = st;
        for (int y = 19; y>=0; y--){
            if (decomp[cur][y]<=pos[x]){
                cur = decomp[cur][y];
                ans1 += (1<<y);
            }
        }
        int ans2 = 0;
        int tt = lower_bound(sorted.begin(),sorted.end(),make_pair(make_pair(stuff[x].second,-1),-1))-sorted.begin();
        cur = tt;
        for (int y = 19; y>=0; y--){
            if (decomp[cur][y]<=en){
                cur = decomp[cur][y];
                ans2 += (1<<y);
            }
        }
        int ans3 = 0;
        cur = st;
        for (int y = 19; y>=0; y--){
            if (decomp[cur][y]<=en){
                cur = decomp[cur][y];
                ans3 += (1<<y);
            }
        }
      //  printf("ans1: %d, ans2: %d\n",ans1,ans2);
        if (curans-ans3+ans1+ans2+1+ans.size()>=k){
            rem.erase(it);
            if (pos[x]>st)rem.insert({st,pos[x]});
            if (en>tt)rem.insert({tt,en});
            ans.push_back(x);
            curans += ans1+ans2-ans3;
        }
    }
    for (int x  : ans){
        printf("%d\n",x+1);
    }
}

Compilation message (stderr)

event2.cpp: In function 'int main()':
event2.cpp:59:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   59 |         if (ans.size()==k) break;
      |             ~~~~~~~~~~^~~
event2.cpp:97:47: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   97 |         if (curans-ans3+ans1+ans2+1+ans.size()>=k){
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
event2.cpp:20:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |     scanf("%d%d",&n,&k);
      |     ~~~~~^~~~~~~~~~~~~~
event2.cpp:23:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |         scanf("%d%d",&a,&b);
      |         ~~~~~^~~~~~~~~~~~~~

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