QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#673073#9513. 环上排序信息最优分割WrongAnswer_900 0ms0kbC++239.4kb2024-10-24 20:30:242024-10-24 20:30:33

Judging History

This is the latest submission verdict.

  • [2024-10-24 20:30:33]
  • Judged
  • Verdict: 0
  • Time: 0ms
  • Memory: 0kb
Show
  • [2024-10-24 20:30:24]
  • Submitted

answer

#include<bits/stdc++.h>
#define ull unsigned long long
#define ui unsigned int
#define ld long double
#define ll long long
#define lll __int128
#define fi first
#define se second
#define e emplace
#define eb emplace_back
#define db double
#define ef emplace_front
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vi vector<int>
#define vll vector<ll>
#define vp vector<pii>
#define vt vector<tup>
#define all(x) x.begin(),x.end()
#define mp make_pair

#define FastI
#define FastO
#define int ll
bool ST;
static const ll MOD=998244353,Phi=998244352,inv2=499122177,Root=3,iRoot=332748118;
static const ll inf=1073741823,Inf=4294967296,INF=4557430888798830399;
static const ld eps=1e-9,pi=3.1415926535;
char in[1<<20],*p1=in,*p2=in;
char out[1<<20],*p3=out;
using namespace std;
struct tup
{
	int x,y,z;
	tup(int X=0,int Y=0,int Z=0)
	{x=X,y=Y,z=Z;}
};
#ifdef FastI
#define getchar() (p1==p2&&(p2=(p1=in)+fread(in,1,1<<20,stdin),p1==p2)?EOF:*p1++)
#endif
#ifdef FastO
#define putchar(x) (p3-out==1<<20?fwrite(out,1,1<<20,stdout),p3=out,0:0,*p3++=x)
#define puts(x) write(x,'\n')
#endif
namespace FastIO
{
	template<typename T> inline void write(T x,char ch=' ')
	{
		if(is_same<char,T>::value)putchar(x);
		else
		{
			if(x<0)x=-x,putchar('-');
			static char st[25];
			int top=0;
			do st[top++]=x%10+'0',x/=10;while(x);
			while(top)putchar(st[--top]);
		}
		ch!='~'?putchar(ch):0;
	}
	inline void write(const char*x,char ch=' ')
	{
		for(int i=0;x[i]!='\0';++i)putchar(x[i]);
		ch!='~'?putchar(ch):0;
	}
	inline void read(char&s){do s=getchar();while(s=='\n'||s==' ');}
	inline void read(char s[])
	{
		int len=0;char st;
		do st=getchar();while(st=='\n'||st==' ');
		s[++len]=st,st=getchar();
		while(st!='\n'&&st!=' '&&st!='\r')s[++len]=st,st=getchar();
		s[++len]='\0';
	}
	template<typename T> inline void read(T &s)
	{
		char ch=getchar();s=0;
		while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
		bool tf=(ch=='-'&&(ch=getchar()));
		while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+ch-'0',ch=getchar();
		s=tf?-s:s;
	}
	inline void edl(){putchar('\n');}
	template<typename T1,typename T2> inline void read(pair<T1,T2> &s){read(s.fi),read(s.se);}
	template<typename T,typename...Args> inline void write(T x,Args...args){write(x,'~'),write(args...);}
	template<typename T,typename...Args> inline void read(T&x,Args&...args){read(x),read(args...);}
	#ifdef FastO
	struct Writer{~Writer(){fwrite(out,1,p3-out,stdout);}}Writ;
	#endif
}
using namespace FastIO;
namespace MTool
{
	inline int Cadd(int a,int b){return (ll)a+b>=MOD?(ll)a+b-MOD:a+b;}
	inline int Cdel(int a,int b){return a-b<0?a-b+MOD:a-b;}
	inline int Cmul(int a,int b){return 1ll*a*b%MOD;}
	inline int sqr(int a){return 1ll*a*a%MOD;}
	inline void Madd(int&a,int b){a=((ll)a+b>=MOD?(ll)a+b-MOD:a+b);}
	inline void Mdel(int&a,int b){a=(a-b<0?a-b+MOD:a-b);}
	inline void Mmul(int&a,int b){a=1ll*a*b%MOD;}
	inline int Cmod(int x){return (x%MOD+MOD)%MOD;}
	inline void Mmod(int&x){x=(x%MOD+MOD)%MOD;}
	template<typename T> inline bool Mmax(T&a,T b){return a<b?a=b,1:0;}
	template<typename T> inline bool Mmin(T&a,T b){return a>b?a=b,1:0;}
	template<typename...Args> inline void Madd(int&a,int b,Args...args){Madd(a,b),Madd(a,args...);}
	template<typename...Args> inline void Mmul(int&a,int b,Args...args){Mmul(a,b),Mmul(a,args...);}
	template<typename...Args> inline void Mdel(int&a,int b,Args...args){Mdel(a,b),Mdel(a,args...);}
	template<typename...Args> inline int Cadd(int a,int b,Args...args){return Cadd(Cadd(a,b),args...);}
	template<typename...Args> inline int Cmul(int a,int b,Args...args){return Cmul(Cmul(a,b),args...);}
	template<typename...Args> inline int Cdel(int a,int b,Args...args){return Cdel(Cdel(a,b),args...);}
	template<typename...Args,typename T> inline bool Mmax(T&a,T b,Args...args){return Mmax(a,b)|Mmax(a,args...);}
	template<typename...Args,typename T> inline bool Mmin(T&a,T b,Args...args){return Mmin(a,b)|Mmin(a,args...);}
	inline int power(int x,int y){int s=1;for(;y;y>>=1,Mmul(x,x))if(y&1)Mmul(s,x);return s;}
}
using namespace MTool;
namespace WrongAnswer_90
{
	int n;
	vi A[200010],B[200010],from[200010];
	vll F[200010];
	#define clr(x) (vi().swap(x))
	namespace myee_trie {
	typedef unsigned long long ullt;
	const ui Dep = 5, W = 64, LogW = 6, And = W - 1, Val = 16777216;
	ullt BUFF[Val >> LogW << 1 | 1];
	ullt *BT = BUFF + sizeof(BUFF) / sizeof(ullt);
	ullt *NewMemory(ui siz) { return BT -= siz; }
	inline ui hp(ullt v) { return W - __builtin_clzll(v) - 1; }
	inline ui lp(ullt v) { return __builtin_ctzll(v); }
	struct Trie  // 压位 Trie
	{
	    ullt *Node[Dep - 1];
	    Trie() {
	        for (ui i = 0; i + 1 < Dep; i++) Node[i] = NewMemory(1llu << (LogW * i));
	    }
	    inline void insert(ui v) {
	        for (ui i = Dep - 2; ~i; i--) {
	            if (Node[i][v >> LogW] >> (v & And) & 1) return;
	            Node[i][v >> LogW] |= 1llu << (v & And), v >>= LogW;
	        }
	    }
	    inline void erase(ui v) {
	        if (!(Node[Dep - 2][v >> LogW] >> (v & And) & 1)) return;
	        for (ui i = Dep - 2; ~i; i--) {
	            Node[i][v >> LogW] &= ~(1llu << (v & And)), v >>= LogW;
	            if (Node[i][v]) return;
	        }
	    }
	    inline ui prev(ui v) {
	        for (ui i = Dep - 2; ~i; i--, v >>= LogW)
	            if (Node[i][v >> LogW] & ~((-1llu) << (v & And))) {
	                ui p = hp(Node[i][v >> LogW] & ~((-1llu) << (v & And))) | (v >> LogW << LogW);
	                while (++i <= Dep - 2) p = (p << LogW) | hp(Node[i][p]);
	                return p;
	            }
	        return 0;
	    }
	    inline ui next(ui v) {
	        for (ui i = Dep - 2; ~i; i--, v >>= LogW)
	            if (Node[i][v >> LogW] & ((-1llu) << (v & And) << 1)) {
	                ui p = lp(Node[i][v >> LogW] & ((-1llu) << (v & And) << 1)) | (v >> LogW << LogW);
	                while (++i <= Dep - 2) p = (p << LogW) | lp(Node[i][p]);
	                return p;
	            }
	        return 0;
	    }
	} T;
	};
	using myee_trie::T;
	vi num;
	ll sum[200010];
	int l[200010],r[200010];
	ll ans=INF;
	inline void ins(int id,int x)
	{
		int L=T.prev(x),R=T.next(x);
		T.insert(x);
//		cerr<<id<<" "<<sum[id]<<endl;
//		cerr<<L<<" "<<R<<" "<<num[L]<<" "<<num[R]<<" "<<num[x]<<endl;
		sum[id]-=2ll*(num[x]-num[L])*(num[R]-num[x]);
//		cerr<<id<<" "<<sum[id]<<endl;
	}
	inline void del(int id,int x)
	{
		T.erase(x);
		int L=T.prev(x),R=T.next(x);
		sum[id]+=2ll*(num[x]-num[L])*(num[R]-num[x]);
	}
	inline void move(int id,int _l,int _r)
	{
		while(l[id]>_l)ins(id,B[(id+n-2)%n+1][--l[id]]);
		while(l[id]<_l)del(id,B[(id+n-2)%n+1][l[id]++]);
		while(r[id]<_r)ins(id,A[id][++r[id]]);
		while(r[id]>_r)del(id,A[id][r[id]--]);
	}
	void Solve(int l,int r,int L,int R,int id)
	{
		if(l>r)return;
		int mid=(l+r)>>1;
		assert(L<=R);
		from[id][mid]=-1;
		for(int i=L;i<=R;++i)
		{
			move(id,i+1,mid);
			if(Mmin(F[id][mid],sum[id]+F[id-1][i]))
			from[id][mid]=i;
		}
		assert(from[id][mid]!=-1);
		Solve(l,mid-1,L,from[id][mid],id);
		Solve(mid+1,r,from[id][mid],R,id);
	}
	void solve(int l,int r,vi L,vi R)
	{
		if(l>r)return clr(L),clr(R),void();
		int mid=(l+r)>>1;
		for(int j=L[1];j<=R[1];++j)
		F[1][j]=INF;
		F[1][mid]=0;
		for(int i=2;i<=n;++i)
		{
			for(int j=L[i];j<=R[i];++j)
			F[i][j]=INF;
			Solve(L[i],R[i],L[i-1],R[i-1],i);
		}
		ll val=INF;
		vi Mid(n+1);
		for(int i=L[n];i<=R[n];++i)
		{
			move(1,i+1,mid);
			if(Mmin(val,F[n][i]+sum[1]))
			Mid[n]=i;
		}
//		for(int i=1;i<=n;++i)
//		{
//			for(int j=0;j<(int)F[i].size()-1;++j)
//			cerr<<F[i][j]<<" ";
//			cerr<<endl;
//		}
//		exit(0);
		Mmin(ans,val);
		for(int i=n;i>1;--i)
		Mid[i-1]=from[i][Mid[i]];
		
		solve(l,mid-1,L,Mid);
		solve(mid+1,r,Mid,R);
		
		clr(L),clr(R),clr(Mid);
	}
	void mian()
	{
		int x,minn=inf,mini=-1;
		read(n);
		for(int i=1;i<=n;++i)
		{
			read(x);
			B[i].resize(x+1);
			for(int j=1;j<=x;++j)read(B[i][j]);
			if(Mmin(minn,(int)B[i].size()))
			mini=i;
		}
		
		for(int i=mini;i<=n;++i)A[i-mini+1]=B[i];
		for(int i=1;i<mini;++i)A[n-mini+i+1]=B[i];
		vi L(1),R(1);
		ll nw=0;
		num.eb(0);
		for(int i=1;i<=n;++i)
		{
			B[i]=A[i];
			F[i].resize(A[i].size());
			from[i].resize(A[i].size());
			
			l[i]=A[(i+n-2)%n+1].size(),r[i]=0;
			sum[i]=4e12;
			
			for(auto p:A[i])
			num.eb(nw+p);
			if(i<n)
			for(auto p:A[i])
			num.eb(nw+p+2000000);
			nw+=2e6;
			num.eb(nw);
			L.eb(0),R.eb(A[i].size()-2);
		}
		for(auto p:A[n])num.eb(p);
		sort(all(num));
//		for(auto p:num)cerr<<p<<" ";
		num.resize(unique(all(num))-num.begin());
		for(int i=1;i<=n;++i)
		{
			for(auto &p:A[i])
			p=lower_bound(all(num),p+2000000ll*(i-1))-num.begin();
		}
		for(int i=1;i<n;++i)
		{
			for(auto &p:B[i])
			p=lower_bound(all(num),p+2000000ll*i)-num.begin();
		}
		for(auto &p:B[n])
		p=lower_bound(all(num),p)-num.begin();
		T.insert(0);
		for(int i=1;i<=n;++i)
		T.insert(lower_bound(all(num),2000000ll*i)-num.begin());
//		cerr<<num[1]<<endl;
//		ins(1,1);
//		cerr<<sum[1];exit(0);
		solve(0,A[1].size()-2,L,R);
		write(ans);
	}
	inline void Mian()
	{
		int T=1;
//		read(T);
		while(T--)mian();
	}
}
bool ED;
signed main()
{
//	ios::sync_with_stdio(0);
	freopen("1.in","r",stdin);
	freopen("1.out","w",stdout);
	double st=clock();
	WrongAnswer_90::Mian();
	double ed=clock();
 	cerr<<endl;
 	cerr<<"Time: "<<ed-st<<" ms\n";
 	cerr<<"Memory: "<<abs(&ST-&ED)/1024.0/1024.0<<" MB\n";
	return 0;
}
源文件, 语言: C++23

詳細信息

Subtask #1:

score: 0
Dangerous Syscalls

Test #1:

score: 0
Dangerous Syscalls

input:

7
2 141209 1121811
2 812367 1802201
2 977174 168547
2 1687591 770753
2 383640 1117793
2 976813 1295653
2 1204905 1272531

output:

result:

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Skipped

Dependency #3:

0%
English 繁體中文 简体中文

伺服器時間: 2025-02-09 00:00:47 | 開源專案