QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#671154 | #9513. 环上排序信息最优分割 | zjy0001 | Compile Error | / | / | C++14 | 4.9kb | 2024-10-24 11:19:18 | 2024-10-24 11:19:22 |
Judging History
This is the latest submission verdict.
- [2024-10-24 11:19:22]
- Judged
- Verdict: Compile Error
- Time: 0ms
- Memory: 0kb
- [2024-10-24 11:19:18]
- Submitted
answer
#include<bits/stdc++.h>
#define LL long long
#define LLL __int128
#define uint unsigned
#define ldb long double
#define uLL unsigned long long
using namespace std;
template < int D = 3 > class fast_trie
{
template < int > friend class fast_trie;
using ull = unsigned long long; using C = fast_trie < D ? D - 1 : 0 >;
constexpr static int L = D * 6; ull o; C *c;
inline static int hb(ull x) { return __builtin_clzll(x) ^ 63; }
inline static int lb(ull x) { return __builtin_ctzll(x); }
public:
inline fast_trie() : o(0), c(D ? new C[64] : nullptr) {}
inline ~fast_trie() { delete[] c; }
inline void ins(int x)
{
int i = ( x >> L ) & 63; o |= 1ull << i;
if constexpr ( D ) c[i].ins(x);
}
inline void del(int x)
{
int i = ( x >> L ) & 63; if ( !( ( o >> i ) & 1 ) ) return;
if constexpr ( D ) { c[i].del(x); if ( !c[i].o ) o ^= 1ull << i; } else o ^= 1ull << i;
}
inline bool count(int x)const
{
int i = ( x >> L ) & 63; if ( !( ( o >> i ) & 1 ) ) return false;
if constexpr ( D ) return c[i].count(x); else return true;
}
inline int min()const
{
if constexpr ( D == 3 ) { if ( !o ) return -1; }
int i = lb(o);
if constexpr ( D ) return c[i].min() | ( i << L ); else return i;
}
inline int max()const
{
if constexpr ( D == 3 ) { if ( !o ) return -1; }
int i = hb(o);
if constexpr ( D ) return c[i].max() | ( i << L ); else return i;
}
inline int pre(int x)const
{
int i = ( x >> L ) & 63, j; ull p;
if constexpr ( !D ) return p = o & ( ( 2ull << i ) - 1 ), p ? hb(p) : -1;
if ( ( o >> i ) & 1 && ~( j = c[i].pre(x) ) ) return j | ( i << L );
if ( !( p = o & ( ( 1ull << i ) - 1 ) ) ) return -1;
return j = hb(p), c[j].max() | ( j << L );
}
inline int nxt(int x)const
{
int i = ( x >> L ) & 63, j; ull p;
if constexpr ( !D ) return p = o & -( 1ull << i ), p ? lb(p) : -1;
if ( ( o >> i ) & 1 && ~( j = c[i].nxt(x) ) ) return j | ( i << L );
if ( !( p = o & -( 2ull << i ) ) ) return -1;
return j = lb(p), c[j].min() | ( j << L );
}
};
fast_trie T;
const int N=2e5+5,V=2e6,M=N*3;
const LL INF=1e18;
int n,q,cnt;
LL ans=INF;
int val[M];
vector<LL>W;
vector<int>L,R;
vector<vector<LL>>F;
vector<multiset<int>>S;
vector<vector<int>>A,pre,B,C;
inline void ins(int k,int v){
const auto x=T.pre(v),y=T.nxt(v);
W[k]-=1ll*(val[y]-val[x])*(val[y]-val[x]);
W[k]+=1ll*(val[y]-val[v])*(val[y]-val[v]);
W[k]+=1ll*(val[v]-val[x])*(val[v]-val[x]);
T.ins(v);
}
inline void del(int k,int v){
T.del(v);
const auto x=T.pre(v),y=T.nxt(v);
W[k]+=1ll*(val[y]-val[x])*(val[y]-val[x]);
W[k]-=1ll*(val[y]-val[v])*(val[y]-val[v]);
W[k]-=1ll*(val[v]-val[x])*(val[v]-val[x]);
}
inline LL calc(int k,int x,int y){
--y;
while(L[k]>x)ins(k,B[k][--L[k]]);
while(R[k]<y)ins(k,C[k][++R[k]]);
while(L[k]<x)del(k,B[k][L[k]++]);
while(R[k]>y)del(k,C[k][R[k]--]);
return W[k];
}
inline void solve(int k,int l,int r,int ql,int qr){
const int mid=(l+r)>>1;
int pos=0;LL w=INF;
for(int i=ql;i<=qr;++i){
LL v=(k?F[k-1][i]:F[n-1][i])+calc(k,i,mid);
if(v<w)w=v,pos=i;
}
F[k][mid]=w,pre[k][mid]=pos;
if(l<mid)solve(k,l,mid-1,ql,pos);
if(mid<r)solve(k,mid+1,r,pos,qr);
}
inline void solve(vector<pair<int,int>>seg){
const int mid=(seg[0].first+seg[0].second)/2;
for(int i=seg[1].first;i<=seg[1].second;++i)
F[1][i]=calc(1,mid,i);
for(int i=2;i<n;++i)
solve(i,seg[i].first,seg[i].second,seg[i-1].first,seg[i-1].second);
int ed=0;LL w=INF;
for(int i=seg[n-1].first;i<=seg[n-1].second;++i){
LL v=F[n-1][i]+calc(0,i,mid);
if(v<w)w=v,ed=i;
}
ans=min(ans,w);
vector<pair<int,int>>segl(n),segr(n);
for(int i=n-1;i>=1;--i){
segl[i]=make_pair(seg[i].first,ed);
segr[i]=make_pair(ed,seg[i].second);
ed=pre[i][ed];
}
segl[0]=make_pair(seg[0].first,mid-1);
segr[0]=make_pair(mid+1,seg[0].second);
if(segl[0].first<=segl[0].second)solve(segl);
if(segr[0].first<=segr[0].second)solve(segr);
}
signed main(){
cin.tie(0)->sync_with_stdio(0);
cin>>n,A.resize(n);
for(int i=0;i<n;++i){
int m;cin>>m,A[i].resize(m);
if(A[i].size()<A[q].size())q=i;
for(int&j:A[i])cin>>j;
}
rotate(A.begin(),A.begin()+q,A.end());
vector<pair<int,int>>seg(n);
pre.resize(n),F.resize(n),L.resize(n),R.resize(n),S.resize(n),W.resize(n),B.resize(n),C.resize(n);
for(int i=0;i<n;++i){
L[i]=(i?A[i-1].size():A[n-1].size()),R[i]=-1,
seg[i]=make_pair(0,A[i].size()-1),
F[i].assign(A[i].size(),INF),
pre[i].resize(A[i].size()),
W[i]=1ll*V*V;
vector<pair<int,int>>E;
for(int j=0;j<A[i?i-1:n-1].size();++j)E.emplace_back(A[i?i-1:n-1][j],-j-1);
for(int j=0;j<A[i].size();++j)E.emplace_back(A[i][j],j+1);
sort(E.begin(),E.end()),B[i].resize(A[i?i-1:n-1].size()),C[i].resize(A[i].size());
val[cnt]=0,T.ins(cnt++);
for(int j=0;j<E.size();++j){
val[cnt]=E[j].first;
if(E[j].second<0)B[i][-E[j].second-1]=cnt++;
else C[i][E[j].second-1]=cnt++;
}
val[cnt]=V,T.ins(cnt++);
}
solve(seg);
cout<<ans<<'\n';
return 0;
}
/*
*/
詳細信息
answer.code: In member function ‘void fast_trie<D>::ins(int)’: answer.code:21:20: warning: ‘if constexpr’ only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions] 21 | if constexpr ( D ) c[i].ins(x); | ^~~~~~~~~ answer.code: In member function ‘void fast_trie<D>::del(int)’: answer.code:26:20: warning: ‘if constexpr’ only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions] 26 | if constexpr ( D ) { c[i].del(x); if ( !c[i].o ) o ^= 1ull << i; } else o ^= 1ull << i; | ^~~~~~~~~ answer.code: In member function ‘bool fast_trie<D>::count(int) const’: answer.code:31:20: warning: ‘if constexpr’ only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions] 31 | if constexpr ( D ) return c[i].count(x); else return true; | ^~~~~~~~~ answer.code: In member function ‘int fast_trie<D>::min() const’: answer.code:35:20: warning: ‘if constexpr’ only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions] 35 | if constexpr ( D == 3 ) { if ( !o ) return -1; } | ^~~~~~~~~ answer.code:37:20: warning: ‘if constexpr’ only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions] 37 | if constexpr ( D ) return c[i].min() | ( i << L ); else return i; | ^~~~~~~~~ answer.code: In member function ‘int fast_trie<D>::max() const’: answer.code:41:20: warning: ‘if constexpr’ only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions] 41 | if constexpr ( D == 3 ) { if ( !o ) return -1; } | ^~~~~~~~~ answer.code:43:20: warning: ‘if constexpr’ only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions] 43 | if constexpr ( D ) return c[i].max() | ( i << L ); else return i; | ^~~~~~~~~ answer.code: In member function ‘int fast_trie<D>::pre(int) const’: answer.code:48:20: warning: ‘if constexpr’ only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions] 48 | if constexpr ( !D ) return p = o & ( ( 2ull << i ) - 1 ), p ? hb(p) : -1; | ^~~~~~~~~ answer.code: In member function ‘int fast_trie<D>::nxt(int) const’: answer.code:56:20: warning: ‘if constexpr’ only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions] 56 | if constexpr ( !D ) return p = o & -( 1ull << i ), p ? lb(p) : -1; | ^~~~~~~~~ answer.code: At global scope: answer.code:62:1: error: invalid use of template-name ‘fast_trie’ without an argument list 62 | fast_trie T; | ^~~~~~~~~ answer.code:62:1: note: class template argument deduction is only available with ‘-std=c++17’ or ‘-std=gnu++17’ answer.code:8:30: note: ‘template<int D> class fast_trie’ declared here 8 | template < int D = 3 > class fast_trie | ^~~~~~~~~ answer.code: In function ‘void ins(int, int)’: answer.code:74:22: error: ‘T’ was not declared in this scope 74 | const auto x=T.pre(v),y=T.nxt(v); | ^ answer.code:75:24: error: ‘y’ was not declared in this scope 75 | W[k]-=1ll*(val[y]-val[x])*(val[y]-val[x]); | ^ answer.code: In function ‘void del(int, int)’: answer.code:81:9: error: ‘T’ was not declared in this scope 81 | T.del(v); | ^ answer.code:83:24: error: ‘y’ was not declared in this scope 83 | W[k]+=1ll*(val[y]-val[x])*(val[y]-val[x]); | ^ answer.code: In function ‘int main()’: answer.code:150:28: error: ‘T’ was not declared in this scope 150 | val[cnt]=0,T.ins(cnt++); | ^