Submission #788063

#	Time	Username	Problem	Language	Result	Execution time	Memory
788063		PoonYaPat	Event Hopping 2 (JOI21_event2)	C++14	7 / 100	162 ms	34924 KiB

event2

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;

int n,k,nxL[100005][18],nxR[100005][18];
const int mx=200010;
pii seg[100005];
set<pii> range;
map<int,int> mp;
pii fen1[200015], fen2[200015];

int find1(int x) {
    int ma=-INT_MAX, ans;
    while (x) {
        if (fen1[x].first && ma<=fen1[x].first){
            ma=fen1[x].first;
            ans=fen1[x].second;
        }
        x-=x&-x;
    }
    return ans;
}

void update1(int x, int val, int idx) {
    while (x<=mx+2) {
        if (fen1[x].first==0 || val>fen1[x].first) {
            fen1[x]=pii(val,idx);
        }
        x+=x&-x;
    }
}

int find2(int x) {
    int mi=INT_MAX, ans;
    while (x) {
        if (fen2[x].first && fen2[x].first<=mi) {
            mi=fen2[x].first;
            ans=fen2[x].second;
        }
        x-=x&-x;
    }
    return ans;
}

void update2(int x, int val, int idx) {
    while (x<=mx+2) {
        if (fen2[x].first==0 || fen2[x].first>val) fen2[x]=pii(val,idx);
        x+=x&-x;
    }
}


int main() {
    ios_base::sync_with_stdio(0); cin.tie();
    cin>>n>>k;

    seg[0]=pii(-INT_MAX,-INT_MAX);
    seg[n+1]=pii(INT_MAX,INT_MAX);
    mp[-INT_MAX]=0; mp[INT_MAX]=0;
    for (int i=0; i<18; ++i) nxL[0][i]=0, nxR[n+1][i]=n+1;

    for (int i=1; i<=n; ++i) {
        cin>>seg[i].first>>seg[i].second;
        mp[seg[i].first]=0;
        mp[seg[i].second]=0;
    }

    int cnt=0;
    for (auto s : mp) mp[s.first]=++cnt;

    //find L
    for (int i=0; i<=n; ++i) update1(mp[seg[i].second],seg[i].first,i);
    for (int i=n; i>0; --i) {
        nxL[i][0]=find1(mp[seg[i].first]);
        for (int j=1; j<18; ++j) nxL[i][j]=nxL[nxL[i][j-1]][j-1];
    }
    
    //find R
    for (int i=1; i<=n+1; ++i) update2(mx-mp[seg[i].first],seg[i].second,i);
    for (int i=n; i>0; --i) {
        nxR[i][0]=find2(mx-mp[seg[i].second]);
        for (int j=1; j<18; ++j) nxR[i][j]=nxR[nxR[i][j-1]][j-1];
    }

    vector<int> ans;
    range.insert(pii(1,1e9));

    for (int i=1; i<=n; ++i) {
        auto it=range.upper_bound(pii(seg[i].first,INT_MAX));
        if (it==range.begin()) continue;
        --it;
        if ((*it).second<seg[i].second) continue;

        int l=(*it).first, r=(*it).second, cnt=0;
        int idx=i;
        for (int j=17; j>=0; --j) {
            if (seg[nxL[idx][j]].first>=l) idx=nxL[idx][j], cnt+=(1<<j);
        }

        idx=i;
        for (int j=17; j>=0; --j) {
            if (seg[nxR[idx][j]].second<=r) idx=nxR[idx][j], cnt+=(1<<j);
        }

        if (cnt>=k-ans.size()-1) {
            ans.push_back(i);
            range.erase(it);
            if (seg[i].first!=l) range.insert(pii(l,seg[i].first));
            if (seg[i].second!=r) range.insert(pii(seg[i].second,r));
        }

        if (ans.size()==k) {
            for (auto s : ans) cout<<s<<"\n";
            return 0;
        }
    }
    cout<<-1;
}

Compilation message (stderr)

event2.cpp: In function 'int main()':
event2.cpp:105:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |         if (cnt>=k-ans.size()-1) {
      |             ~~~^~~~~~~~~~~~~~~~
event2.cpp:112:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  112 |         if (ans.size()==k) {
      |             ~~~~~~~~~~^~~
event2.cpp: In function 'int find1(int)':
event2.cpp:21:12: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   21 |     return ans;
      |            ^~~
event2.cpp: In function 'int find2(int)':
event2.cpp:42:12: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   42 |     return ans;
      |            ^~~
event2.cpp: In function 'int main()':
event2.cpp:81:18: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   81 |         nxR[i][0]=find2(mx-mp[seg[i].second]);
      |         ~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
event2.cpp:74:18: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   74 |         nxL[i][0]=find1(mp[seg[i].first]);
      |         ~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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