제출 #441876

#제출 시각아이디문제언어결과실행 시간메모리
441876kig9981Event Hopping 2 (JOI21_event2)C++17
0 / 100
317 ms73500 KiB
#include <bits/stdc++.h> #ifdef NON_SUBMIT #define TEST(n) (n) #define tout cerr #else #define TEST(n) ((void)0) #define tout cin #endif using namespace std; struct Seg { int l, r, v; Seg() : l(0), r(0), v(0) {} } tree[5555555]; const int SZ=1<<18; vector<int> x(1); vector<pair<int,int>> S; int node_cnt, tor[2*SZ], lazy[2*SZ], L[2*SZ], R[2*SZ]; void set_tree(int b, int n, int p, int s=0, int e=SZ-1) { int m=(s+e)>>1; if(s==e) { tree[p].v=1; return; } if(n<=m) { if(tree[p].l==tree[b].l) tree[tree[p].l=node_cnt++]=tree[tree[b].l]; set_tree(tree[b].l,n,tree[p].l,s,m); } else { if(tree[p].r==tree[b].r) tree[tree[p].r=node_cnt++]=tree[tree[b].r]; set_tree(tree[b].r,n,tree[p].r,m+1,e); } tree[p].v=tree[tree[p].l].v+tree[tree[p].r].v; } int get_r(int p, int s=0, int e=SZ-1) { int m=(s+e)>>1; if(tree[p].v==0) return -1; if(s==e) return m; if(tree[tree[p].r].v) return get_r(tree[p].r,m+1,e); return get_r(tree[p].l,s,m); } int get_sum(int n1, int n2, int p, int s=0, int e=SZ-1) { int m=(s+e)>>1; if(n2<n1 || n2<s || e<n1 || p==0) return 0; if(n1<=s && e<=n2) return tree[p].v; return get_sum(n1,n2,tree[p].l,s,m)+get_sum(n1,n2,tree[p].r,m+1,e); } void lazy_propagation(int bit, int s, int e) { if(lazy[bit]) { tor[bit]=1; if(s<e) lazy[2*bit]=lazy[2*bit+1]=1; lazy[bit]=0; } } void or_tree(int n1, int n2, int bit=1, int s=0, int e=SZ-1) { int m=(s+e)>>1; lazy_propagation(bit,s,e); if(n2<n1 || n2<s || e<n1) return; if(n1<=s && e<=n2) { lazy[bit]=1; lazy_propagation(bit,s,e); return; } or_tree(n1,n2,2*bit,s,m); or_tree(n1,n2,2*bit+1,m+1,e); tor[bit]=tor[2*bit]|tor[2*bit+1]; } int get_or(int n1, int n2, int bit=1, int s=0, int e=SZ-1) { int m=(s+e)>>1; lazy_propagation(bit,s,e); if(n2<n1 || n2<s || e<n1) return 0; if(n1<=s && e<=n2) return tor[bit]; return get_or(n1,n2,2*bit,s,m)|get_or(n1,n2,2*bit+1,m+1,e); } int get_lp(int n1, int n2, int bit=1, int s=0, int e=SZ-1) { int m=(s+e)>>1, t; lazy_propagation(bit,s,e); if(n2<n1 || n2<s || e<n1 || !tor[bit]) return SZ; if(s==e) return m; if((t=get_lp(n1,n2,2*bit,s,m))<SZ) return t; return get_lp(n1,n2,2*bit+1,m+1,e); } int get_rp(int n1, int n2, int bit=1, int s=0, int e=SZ-1) { int m=(s+e)>>1, t; lazy_propagation(bit,s,e); if(n2<n1 || n2<s || e<n1 || !tor[bit]) return -1; if(s==e) return m; if((t=get_rp(n1,n2,2*bit+1,m+1,e))>-1) return t; return get_rp(n1,n2,2*bit,s,m); } int get_lv(int n) { int ret=L[n+=SZ]; while(n>>=1) ret+=L[n]; return ret; } int get_rv(int n) { int ret=R[n+=SZ]; while(n>>=1) ret+=R[n]; return ret; } void add_lv(int s, int e, int v) { for(s+=SZ,e+=SZ;s<=e;s>>=1,e>>=1) { if(s&1) L[s++]+=v; if(~e&1) L[e--]+=v; } } void add_rv(int s, int e, int v) { for(s+=SZ,e+=SZ;s<=e;s>>=1,e>>=1) { if(s&1) R[s++]+=v; if(~e&1) R[e--]+=v; } } void set_lv(int n, int v) { v-=get_lv(n); L[n+SZ]+=v; } void set_rv(int n, int v) { v-=get_rv(n); R[n+SZ]+=v; } int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); TEST(freopen("input.txt","r",stdin)); TEST(freopen("output.txt","w",stdout)); TEST(freopen("debug.txt","w",stderr)); int N, K, cnt=0; cin>>N>>K; S.resize(N); for(auto &[l,r]: S) { cin>>l>>r; x.push_back(l); x.push_back(r); } sort(x.begin(),x.end()); x.resize(node_cnt=unique(x.begin(),x.end())-x.begin()); memset(R,0x7f,sizeof(R)); for(int i=0;i<N;i++) { auto &[l,r]=S[i]; l=lower_bound(x.begin(),x.end(),l)-x.begin(); r=lower_bound(x.begin(),x.end(),r)-x.begin(); R[r]=min(R[r],l); } for(int i=1;i<x.size();i++) { tree[i]=tree[i-1]; if(R[i]<i && get_r(i-1)<R[i]) { tree[i]=tree[R[i]]; set_tree(R[i],R[i],i); } } if(tree[x.size()-1].v<K) { cout<<"-1\n"; return 0; } memset(R,0,sizeof(R)); or_tree(0,0); or_tree(x.size()-1,x.size()-1); for(int i=0;i<N;i++) { auto[l,r]=S[i]; if(get_or(l,r-1)) continue; int s=get_rp(0,l)+1, e=get_lp(r,SZ-1), sv=get_lv(s), ev=get_rv(e), lv=get_sum(s,l,l), rv=get_sum(r,e,e), tv=get_sum(s,e,e); if(sv+lv+1+rv+ev<K || ++cnt>K) continue; or_tree(l,r-1); add_rv(0,s,tv-(lv+rv+1)); set_rv(l,ev+rv+1); add_lv(e,SZ-1,tv-(lv+rv+1)); set_lv(r,sv+lv+1); cout<<i+1<<'\n'; } return 0; }

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

event2.cpp: In function 'int main()':
event2.cpp:176:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  176 |  for(int i=1;i<x.size();i++) {
      |              ~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...