제출 #895037

#제출 시각아이디문제언어결과실행 시간메모리
8950378pete8Event Hopping 2 (JOI21_event2)C++17
0 / 100
96 ms20668 KiB
#include<iostream> #include<stack> #include<map> #include<vector> #include<string> #include<unordered_map> #include <queue> #include<cstring> #include<float.h> #include<limits.h> #include <cassert> #include<cmath> #include<set> #include<algorithm> #include <iomanip> #include<numeric> //gcd(a,b) #include<bitset> using namespace std; #define ll long long #define f first #define endl "\n" #define s second #define pii pair<int,int> #define ppii pair<int,pii> #define vi vector<int> #define pb push_back #define all(x) x.begin(),x.end() #define rall(x) x.rbegin(),x.rend() #define F(n) for(int i=0;i<n;i++) #define lb lower_bound #define ub upper_bound #define fastio ios::sync_with_stdio(false);cin.tie(NULL); #pragma GCC optimize ("03,unroll-loops") using namespace std; #define int long long #define double long double const int mod=998244353,mxn=2e5+5,lg=30,inf=1e18,minf=-1e18,Mxn=100000; int n,k,sz; struct info{int l,r,posl,posr,mx,id;}; bool cmp(info a,info b){return a.r<b.r;} bool cmp2(info a,info b){return a.id<b.id;} struct seg{ int v[2*mxn+10]; void init(){for(int i=0;i<=2*sz+5;i++)v[i]=0;} void update(int pos,int val){ pos+=sz; v[pos]=max(val,v[pos]); for(int i=pos;i>0;i>>=1)v[i>>1]=max(v[i],v[i^1]); } int qry(int l,int r){ int ans=0; for(l+=sz,r+=sz;l<=r;l>>=1,r>>=1){ if(l&1)ans=max(ans,v[l++]); if(!(r&1))ans=max(ans,v[r--]); } return ans; } }t; struct lazyseg{ int v[4*mxn+10],add[4*mxn+10]; void push(int pos,int l,int r){ if(!add[pos])return; v[pos]=1; if(l!=r)add[pos*2]=add[pos],add[pos*2+1]=add[pos]; add[pos]=0; } void update(int l,int r,int pos,int ql,int qr){ push(pos,l,r); if(l>qr||r<ql)return; if(ql<=l&&r<=qr){ add[pos]=1; push(pos,l,r); return; } int mid=l+(r-l)/2; update(l,mid,pos*2,ql,qr); update(mid+1,r,pos*2+1,ql,qr); v[pos]=v[pos*2]|v[pos*2+1]; } int qry(int l,int r,int pos,int ql,int qr){ if(ql>qr)return 0; push(pos,l,r); if(l>qr||r<ql)return 0; if(ql<=l&&r<=qr)return v[pos]; int mid=l+(r-l)/2; return (qry(l,mid,pos*2,ql,qr)|qry(mid+1,r,pos*2+1,ql,qr)); } }t2; vector<info>v; vector<int>compress; int32_t main(){ fastio cin>>n>>k; for(int i=0;i<n;i++){ int a,b;cin>>a>>b; v.pb({a,b,-1,-1,0,i+1}); compress.pb(a); compress.pb(b); } sort(all(compress)); unique(all(compress)); sz=compress.size()+5; for(auto &i:v){ i.posl=lb(all(compress),i.l)-compress.begin()+1; i.posr=lb(all(compress),i.r)-compress.begin()+1; } sort(all(v),cmp); reverse(all(v)); t.init(); for(auto &i:v){ i.mx=t.qry(i.posr,sz)+1; t.update(i.posl,i.mx); } reverse(all(v)); t.init(); for(auto &i:v){ i.mx=max(i.mx,t.qry(0,i.posl)); t.update(i.posr,i.mx); } sort(all(v),cmp2); vector<int>ans; for(auto i:v){ if(i.mx<k)continue; if(t2.qry(0,sz,1,i.posl+1,i.posr-1))continue; t2.update(0,sz,1,i.posl,i.posr); ans.pb(i.id); if(ans.size()==k)break; } if(ans.size()<k)cout<<-1<<'\n'; else for(int i=0;i<k;i++)cout<<ans[i]<<"\n"; return 0; }

컴파일 시 표준 에러 (stderr) 메시지

event2.cpp: In function 'int32_t main()':
event2.cpp:127:16: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  127 |   if(ans.size()==k)break;
      |      ~~~~~~~~~~^~~
event2.cpp:129:15: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  129 |  if(ans.size()<k)cout<<-1<<'\n';
      |     ~~~~~~~~~~^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...