Submission #589803

#	Time	Username	Problem	Language	Result	Execution time	Memory
589803		marcipan5000	Event Hopping 2 (JOI21_event2)	C++14	100 / 100	859 ms	51212 KiB

event2

#include <bits/stdc++.h>

using namespace std;

struct event{
    int s;
    int a,b;
    int inda,indb;
};

struct break_point{
    int a;
    int ind;
};

int n,k;
vector<event> t;
event null_event;
vector<int> h[200005];
vector<break_point> g;
vector<break_point> gs;
break_point u;
int m;
map<int,int,less<int>> ass;
int p=0;
int lmin=1e9,rmax=-1;

bool kis(break_point x,break_point y) {
    return((x.a<y.a)||((x.a==y.a)&&(x.ind<y.ind)));
}

struct classcomp{
    bool operator() (const event x,const event y) const {
        return((x.a<y.a)||((x.a==y.a)&&(x.s<y.s)));
    }
};

int max_place(int l,int r) {
    int cur_ind=ass[l];
    if ((h[cur_ind].size()==0)||(g[h[cur_ind][0]].a>r)) {
        return(0);
    }
    int db=1,depth=1;
    while ((h[cur_ind].size()>depth)&&(g[h[cur_ind][depth]].a<=r)) {
        db=db*2; depth++;
    }
    return(max_place(g[h[cur_ind][depth-1]].a,r)+db);
}

bool intersect(event x,event y) {
    return(!((x.b<=y.a)||(x.a>=y.b)));
}

int ans;
int ans2;
set<event,classcomp> an;
set<event,classcomp>::iterator it;
int d,e;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> k;
    null_event.s=0; null_event.a=0; null_event.b=0; null_event.inda=-1; null_event.indb=-1;
    t.assign(n+1,null_event);
    for (int i=1;i<=n;i++) {
        cin >> t[i].a >> t[i].b;
        lmin=min(lmin,t[i].a);
        rmax=max(rmax,t[i].b);
        t[i].s=i;
        if (ass.find(t[i].a)==ass.end()) {
            u.a=t[i].a; u.ind=p; g.push_back(u);
            ass[t[i].a]=p; p++;
        }
        t[i].inda=ass[t[i].a];
        if (ass.find(t[i].b)==ass.end()) {
            u.a=t[i].b; u.ind=p; g.push_back(u);
            ass[t[i].b]=p; p++;
        }
        t[i].indb=ass[t[i].b];
        if (h[t[i].inda].size()==0) {
            h[t[i].inda].push_back(t[i].indb);
        } else if (g[h[t[i].inda][0]].a>t[i].b) {
            h[t[i].inda][0]=t[i].indb;
        }
    }
    gs=g;
    m=g.size();
    sort(gs.begin(),gs.end(),kis);
    for (int i=m-2;i>=0;i--) {
        if (h[gs[i+1].ind].size()>0) {
            if (h[gs[i].ind].size()==0) {
                h[gs[i].ind].push_back(h[gs[i+1].ind][0]);
            } else if (g[h[gs[i+1].ind][0]].a<g[h[gs[i].ind][0]].a) {
                h[gs[i].ind][0]=h[gs[i+1].ind][0];
            }
        }
    }
    for (int j=1;j<=100;j++) {
        for (int i=0;i<m;i++) {
            if (h[gs[i].ind].size()<j) {
                break;
            }
            if (h[h[gs[i].ind][j-1]].size()<j) {
                break;
            }
            h[gs[i].ind].push_back(h[h[gs[i].ind][j-1]][j-1]);
        }
    }

    /*
    for (int i=0;i<m;i++) {
        cout << i << ": " << gs[i].a << " " << gs[i].ind << " jumps: ";
        for (int j:h[gs[i].ind]) {
            cout << g[j].a << " ";
        }
        cout << endl;
    }

    int d,e;
    while (true) {
        cin >> d >> e;
        cout << max_place(d,e) << endl;
    }
    */

    ans=max_place(lmin,rmax);
    if (ans<k) {
        cout << -1 << endl;
        return(0);
    }

    event z;
    z.a=-1e9;
    z.b=lmin;
    z.s=-1;
    an.insert(z);
    z.a=rmax;
    z.b=1e9+1;
    z.s=-2;
    an.insert(z);

    //cout << lmin << " " << rmax << endl;

    for (int i=1;i<=n;i++) {
        ans2=ans;
        it=an.lower_bound(t[i]);
        //cout << i << " " << (*it).s << endl;
        //cout << (it==an.end()) << endl;
        if (intersect(*it,t[i])) {
            continue;
        }
        e=(*it).a;
        it--;
        //cout << i << " " << (*it).s << endl;
        if (intersect(*it,t[i])) {
            continue;
        }
        d=(*it).b;
        ans2-=max_place(d,e);
        ans2+=1;
        ans2+=max_place(d,t[i].a);
        ans2+=max_place(t[i].b,e);
        if (ans2>=k) {
            an.insert(t[i]);
            ans=ans2;
        }
        if (an.size()==2+k) {
            break;
        }

        //cout << ans << " " << ans2 << endl;
    }
    vector<int> kiir;
    for (event i:an) {
        if (i.s>0) {
            kiir.push_back(i.s);
        }
    }
    sort(kiir.begin(),kiir.end());
    for (int i:kiir) {
        cout << i << endl;
    }
    return 0;
}

/*
5 4
1 3
2 5
8 9
6 8
10 15
*/

Compilation message (stderr)

event2.cpp: In function 'int max_place(int, int)':
event2.cpp:44:30: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   44 |     while ((h[cur_ind].size()>depth)&&(g[h[cur_ind][depth]].a<=r)) {
      |             ~~~~~~~~~~~~~~~~~^~~~~~
event2.cpp: In function 'int main()':
event2.cpp:102:36: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  102 |             if (h[gs[i].ind].size()<j) {
      |                 ~~~~~~~~~~~~~~~~~~~^~
event2.cpp:105:44: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  105 |             if (h[h[gs[i].ind][j-1]].size()<j) {
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~
event2.cpp:169:22: warning: comparison of integer expressions of different signedness: 'std::set<event, classcomp>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  169 |         if (an.size()==2+k) {
      |             ~~~~~~~~~^~~~~

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