Submission #390835

#	Time	Username	Problem	Language	Result	Execution time	Memory
390835		inwbear	Event Hopping 2 (JOI21_event2)	C++14	7 / 100	289 ms	23328 KiB

event2

#include<bits/stdc++.h>
//#pragma GCC optimize("O3")
//#pragma GCC target ("sse4")
using namespace std;
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define MEM(x,a) memset((x),a,sizeof((x)))
#define F first
#define S second
#define L (idx*2)
#define R (L+1)
#define imx INT_MAX
const long long MOD = (long long)(1e9+7);
const long long MMX = (long long)(1e18);
typedef long long LL;
typedef pair<int,int> pii;
int n,k,N,cn[100005],seq[800010],pr,mx,ss;
set<int>s;
vector<int>puu[100005];
map<int,int>mp;
struct node
{
    int l,r;
}ev[100005];
vector<int>sor;
priority_queue<pii>pq;

void seq_up(int st,int ed,int idx,int pos,int val)
{
    int mid=(st+ed)/2;
    if(pos<st||pos>ed)return;
    if(st==ed)
    {
        seq[idx]=max(seq[idx],val);
        return;
    }
    seq_up(st,mid,L,pos,val);
    seq_up(mid+1,ed,R,pos,val);
    seq[idx]=max(seq[L],seq[R]);
    return;
}
int seq_mx(int st,int ed,int idx,int ll,int rr)
{
    int mid=(st+ed)/2;
    if(rr<st||ll>ed)return 0;
    if(ll<=st&&rr>=ed)return seq[idx];
    return max(seq_mx(st,mid,L,ll,rr),seq_mx(mid+1,ed,R,ll,rr));
}

int main()
{
    scanf("%d %d",&n,&k);
    for(int i=1;i<=n;i++)
    {
        scanf("%d %d",&ev[i].l,&ev[i].r);
        if(mp[ev[i].l]==0)
        {
            sor.pb(ev[i].l);
            mp[ev[i].l]=1;
        }
        if(mp[ev[i].r]==0)
        {
            sor.pb(ev[i].r);
            mp[ev[i].r]=1;
        }
    }
    sort(all(sor));
    for(int i=0;i<sor.size();i++)
    {
        mp[sor[i]]=i+1;
    }
    N=sor.size();
    sor.clear();
    for(int i=1;i<=n;i++)
    {
        ev[i].l=mp[ev[i].l];
        ev[i].r=mp[ev[i].r];
        pq.push({ev[i].l,i});
    }
    while(!pq.empty())
    {
        pr=pq.top().S;
        pq.pop();
        mx=seq_mx(1,N,1,ev[pr].r,N);
        seq_up(1,N,1,ev[pr].l,mx+1);
        cn[pr]=mx+1;
    }
    ss=imx;
    for(int i=1;i<=n;i++)
    {
        if(cn[i]>=k)
        {
            ss=min(i,ss);
        }
        puu[cn[i]].pb(i);
    }
    if(ss==imx)
    {
        printf("-1");
    }
    else
    {
        sor.pb(ss);
        for(int i=n;i>=k;i--)
        {
            for(int j=0;j<puu[i].size();j++)
            {
                s.insert(puu[i][j]);
                pq.push({-ev[puu[i][j]].l,puu[i][j]});
            }
        }
        for(int i=k-1;i>0;i--)
        {
            for(int j=0;j<puu[i].size();j++)
            {
                s.insert(puu[i][j]);
                pq.push({-ev[puu[i][j]].l,puu[i][j]});
            }
            while(-pq.top().F<ev[ss].r)
            {
                s.erase(pq.top().S);
                pq.pop();
            }
            ss=*(s.begin());
            sor.pb(ss);
        }
        sort(all(sor));
        for(int i=0;i<sor.size();i++)
        {
            printf("%d\n",sor[i]);
        }
    }
}

Compilation message (stderr)

event2.cpp: In function 'int main()':
event2.cpp:68:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     for(int i=0;i<sor.size();i++)
      |                 ~^~~~~~~~~~~
event2.cpp:106:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |             for(int j=0;j<puu[i].size();j++)
      |                         ~^~~~~~~~~~~~~~
event2.cpp:114:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |             for(int j=0;j<puu[i].size();j++)
      |                         ~^~~~~~~~~~~~~~
event2.cpp:128:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |         for(int i=0;i<sor.size();i++)
      |                     ~^~~~~~~~~~~
event2.cpp:52:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   52 |     scanf("%d %d",&n,&k);
      |     ~~~~~^~~~~~~~~~~~~~~
event2.cpp:55:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   55 |         scanf("%d %d",&ev[i].l,&ev[i].r);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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