Submission #806326

#	Time	Username	Problem	Language	Result	Execution time	Memory
806326		vjudge1	Event Hopping 2 (JOI21_event2)	C++14	0 / 100	2731 ms	30280 KiB

event2

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
using namespace std ;
const int N = (1 << 17) ;
bool flag1, us[N + 1] ;
int n, cnt, k, a[N + 1], b[N + 1], dp[N + 1], pw[N + 1], mx[N + 1][18] ;
pair<pair<int, int>, int> p[N + 1] ;
vector<int> ans ;
map<int, int> mp ;
set<int> s ;
bool flag = 0 ;
vector<int> now, v[N + 1] ;
void dfs(int city, int last)
{
    us[city] = 1 ;
    now.push_back(city) ;
    for(int i : v[city])
    {
        if(i == last)
            continue ;
        dfs(i, city) ;
    }
}
void build_sparce_table()
{
    for(int i = 2 ; i <= n ; i++)
        pw[i] = pw[i / 2] + 1 ;
    for(int i = 1 ; i <= n ; i++)
        mx[i][0] = a[i] ;
    for(int i = 1 ; i < 18 ; i++)
        for(int j = 1 ; j <= n - (1 << i) + 1 ; j++)
            mx[j][i] = max(mx[j][i - 1], mx[j + (1 << (i - 1))][i - 1]) ;
}
int get_max(int l, int r)
{
    int num = pw[r - l + 1] ;
    return max(mx[l][num], mx[r - (1 << num) + 1][num]) ;
}
signed main()
{
    ios_base::sync_with_stdio( 0 ) ;
    cin.tie( 0 ) ;
    cout.tie( 0 ) ;
    cin >> n >> k ;
    for(int i = 1 ; i <= n ; i++)
    {
        cin >> a[i] >> b[i] ;
        if(a[i - 1] > a[i])
            flag1 = 1 ;
        p[i] = {{b[i], a[i]}, i} ;
        s.insert(a[i]) ;
        s.insert(b[i]) ;
    }
//    cout<<flag1<<'\n' ;
    if(!flag1)
    {
        build_sparce_table() ;
        for(int i = 1 ; i <= n ; i++)
        {
            int l = i, r = n + 1 ;
            while(l + 1 < r)
            {
                int mid = (l + r) >> 1 ;
                if(get_max(i + 1, mid) >= b[i])
                    r = mid ;
                else
                    l = mid ;
            }
            if(r < n + 1)
                v[i].push_back(r) ;
        }
        for(int i = 1 ; i <= n ; i++)
        {
            if(us[i])
                continue ;
            now.clear() ;
            dfs(i, 1) ;
            if(now.size() >= k)
            {
                for(int i = 0 ; i < k ; i++)
                    cout << now[i] << '\n' ;
                return 0 ;
            }
        }
        cout << "-1\n" ;
        return 0 ;
    }
//    for(int i : s)
//    {
//        cnt++ ;
//        mp[i] = cnt ;
//    }
//    sort(p + 1, p + n + 1) ;
//    for(int i = 1 ; i <= n ; i++)
//    {
//        p[i].fi.se = mp[p[i].fi.se] ;
//        p[i].fi.fi = mp[p[i].fi.fi] ;
//    }
//    for(int i = 1 ; i <= n ; i++)
//    {
//        dp[i] = 1 ;
//        for(int j = 1 ; j < i ; j++)
//            if(p[j].fi.fi <= p[i].fi.se)
//                dp[i] = max(dp[j] + 1, dp[i]) ;
//    }
//    for(int i = 1 ; i <= n ; i++)
//    {
//        if(dp[i] < k)
//            continue ;
//        int cnt = dp[i] ;
//    }
//    cout << ans.size() << '\n' ;
//    for(int i : ans)
//        cout << i << '\n' ;
    return 0 ;
}

Compilation message (stderr)

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

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