제출 #1089108

#제출 시각아이디문제언어결과실행 시간메모리
1089108guagua0407팀들 (IOI15_teams)C++17
컴파일 에러
0 ms0 KiB
#include "teams.h" #include <bits/stdc++.h> using namespace std; #define ll long long //#define int ll #define pii pair<int,int> #define f first #define s second #define all(x) x.begin(),x.end() #define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); const ll mxn=5e5+5; const ll inf=1e9; vector<ll> segtree(mxn*20); vector<ll> R(mxn*20),L(mxn*20); vector<ll> root(mxn); ll n; ll cnt=0; ll update(ll node,ll pos,ll l=1,ll r=n){ ll x=++cnt; assert(x<mxn*20); L[x]=L[node]; R[x]=R[node]; segtree[x]=segtree[node]; if(l==r){ segtree[x]++; return x; } ll mid=(l+r)/2; if(pos<=mid) L[x]=update(L[node],pos,l,mid); else R[x]=update(R[node],pos,mid+1,r); segtree[x]=segtree[L[x]]+segtree[R[x]]; return x; } ll query(ll node1,ll node2,ll tl,ll tr,ll l=1,ll r=n){ if(r<tl or tr<l){ return 0; } if(tl<=l and r<=tr){ return segtree[node1]-segtree[node2]; } ll mid=(l+r)/2; return query(L[node1],L[node2],tl,min(mid,tr),l,mid)+query(R[node1],R[node2],max(mid+1,tl),tr,mid+1,r); } ll kth(ll node1,ll node2,ll k,ll l=1,ll r=n){ if(l==r){ return l; } ll sum=segtree[L[node1]]-segtree[L[node2]]; ll mid=(l+r)/2; if(k<=sum) return kth(L[node1],L[node2],k,l,mid); else return kth(R[node1],R[node2],k-sum,mid+1,r); } void init(ll N, ll A[], ll B[]) { n=N; vector<vector<ll>> vec(n+1); for(ll i=0;i<n;i++){ vec[A[i]].push_back(B[i]); } for(ll i=1;i<=n;i++){ root[i]=root[i-1]; for(auto v:vec[i]){ root[i]=update(root[i],v); } } } ll can(ll M, ll K[]) { sort(K,K+M); ll m=M+1; vector<ll> vec(m); for(ll i=1;i<m;i++){ vec[i]=K[i-1]; } vector<ll> rem(m); vector<ll> used(m); vector<ll> H(m); vector<ll> st; st.push_back(0); H[0]=n+1; //cout<<'\n'; for(ll i=1;i<m;i++){ used[i]=query(root[vec[i]],root[vec[st.back()]],1,vec[i]-1); while(!st.empty() and H[st.back()]<vec[i]){ assert((ll)st.size()>1); used[i]+=query(root[vec[st.back()]],root[vec[st[st.size()-2]]],1,vec[i]-1); st.pop_back(); } ll sum=rem[st.back()]+query(root[vec[i]],root[vec[st.back()]],1,n)-used[i]; //cout<<sum<<' '<<rem[st.back()]<<' '<<query(root[vec[i]],root[vec[st.back()]],vec[i],n)<<'\n'; if(sum<vec[i]){ return 0; } H[i]=vec[i]; ll cur=vec[i]; while(!st.empty()){ ll now=query(root[vec[i]],root[vec[st.back()]],1,H[st.back()]-1)-used[i]; //cout<<now<<'\n'; if(now>=cur){ used[i]+=cur; if(now==cur) H[i]=H[st.back()]; else H[i]=kth(root[vec[i]],root[vec[st.back()]],used[i]+1); assert(H[i]<=H[st.back()]); rem[i]=rem[st.back()]+query(root[vec[i]],root[vec[st.back()]],1,n)-used[i]; break; } else{ H[i]=H[st.back()]; used[i]+=used[st.back()]; used[i]+=now; cur-=now; st.pop_back(); } } if(H[st.back()]==H[i]) st.pop_back(); st.push_back(i); } return 1; } /*ll main() { ll N; cin>>N; int *A = (int*)malloc(sizeof(int)*(unsigned int)N); int *B = (int*)malloc(sizeof(int)*(unsigned int)N); for (int i = 0; i < N; ++i) { cin>>A[i]>>B[i]; } init(N, A, B); int Q; cin>>Q; for (int i = 0; i < Q; ++i) { int M; cin>>M; int *K = (int*)malloc(sizeof(int)*(unsigned int)M); for (int j = 0; j < M; ++j) { cin>>K[j]; } cout<<can(M, K)<<'\n'; } return 0; }*/

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

/usr/bin/ld: /tmp/cc1sbDzU.o: in function `main':
grader.c:(.text.startup+0x88): undefined reference to `init(int, int*, int*)'
/usr/bin/ld: grader.c:(.text.startup+0x242): undefined reference to `can(int, int*)'
collect2: error: ld returned 1 exit status