oj.uz

Submission #894565

# Submission time Handle Problem Language Result Execution time Memory
894565 2023-12-28T12:57:44 Z ReLice Event Hopping 2 (JOI21_event2) C++14
0 / 100
 195 ms 72472 KB 
#include <bits/stdc++.h>
#define ll long long
#define str string
#define ins insert
#define ld long double
#define pb push_back
#define pf push_front
#define pof pop_front()
#define pob pop_back()
#define lb lower_bound
#define ub upper_bound
#define endl "\n"
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define sz size()
#define vll vector<ll>
#define bc back()
#define arr array
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template <class _T>
bool chmin(_T &x, const _T &y){
    if (x>y)x=y;
    return x>y;
}
template <class _T>
bool chmax(_T &x, const _T &y){
    if (x<y)x=y;
    return x<y;
}
#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>
void fre(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
void start(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}
const ll inf=1e18+7;
const ll mod=1e9+7;
const ll N=3e5+5;
const ld eps=1e-9;
ll p[N][21];
ll dp(ll l,ll r){
    ll sum=0;
    for(ll i=20;i>=0;i--){
        if(p[l][i]<=r){
            sum+=(1ll<<i);
            l=p[l][i];
        }
    }
    return sum;
}
void solve(){
	ll i,j;
	ll n,k;
	ll a,b;
	cin>>n>>k;
	ll l[n],r[n];
	set<ll> st;
	for(i=0;i<n;i++){
        cin>>l[i]>>r[i];
        st.ins(l[i]);
        st.ins(r[i]);
	}

	//compress
	map<ll,ll> comp;
	ll c=0;
	for(auto i : st){
        comp[i]=++c;
	}
	for(i=0;i<n;i++){
        l[i]=comp[l[i]];
        r[i]=comp[r[i]];
	}

	//building graph
	ll m=c;
	ll suf[m+5];
	for(i=0;i<m+2;i++) suf[i]=m+1;
	vector<vll> v(m+5);
	for(i=0;i<n;i++){
        v[l[i]].pb(r[i]);
	}
	for(i=m;i>0;i--){
        suf[i]=suf[i+1];
        for(auto j : v[i])chmin(suf[i],j);
	}
	for(i=1;i<=m;i++){
        p[i][0]=suf[i];
	}
    for(j=1;j<=20;j++){
        for(i=m;i>0;i--){
                p[i][j]=p[p[i][j-1]][j-1];
        }
	}

	//answer
	set<pair<ll,ll>> rng;
	rng.ins({1,m});
	ll al=dp(1,m);
	if(dp(1,m)<k){
        cout<<-1<<endl;
        return;
	}
	for(i=0;i<n;i++){
        auto it=rng.ub({l[i],inf});
        it--;
        ll L=it->fr,R=it->sc;
        if(R<r[i])continue;
        if(al-dp(L,R)+dp(L,l[i])+dp(r[i],R)+1>=k){
            al=al-dp(L,R)+dp(L,l[i])+dp(r[i],R)+1;
            k--;
            cout<<i+1<<endl;
            if(k==0)return;
            rng.erase(it);
            rng.ins({L,l[i]});
            rng.ins({r[i],R});
        }
	}
}
signed main(){
	start();
    ll t=1;
	//cin>>t;
    while(t--) solve();
    return 0;
}
/*
4 2
1 4
3 5
4 9
7 10

*/

Compilation message

event2.cpp: In function 'void solve()':
event2.cpp:60:5: warning: unused variable 'a' [-Wunused-variable]
   60 |  ll a,b;
      |     ^
event2.cpp:60:7: warning: unused variable 'b' [-Wunused-variable]
   60 |  ll a,b;
      |       ^
event2.cpp: In function 'void fre(std::string)':
event2.cpp:36:27: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 | void fre(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
      |                    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
event2.cpp:36:64: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 | void fre(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
      |                                                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 195 ms 72472 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 195 ms 72472 KB Output isn't correct
5 Halted 0 ms 0 KB -