QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#531980#9228. ICPC Inferenceucup-team3586#WA 57ms80428kbC++234.0kb2024-08-24 23:29:012024-08-24 23:29:02

Judging History

你现在查看的是最新测评结果

  • [2024-08-24 23:29:02]
  • 评测
  • 测评结果:WA
  • 用时:57ms
  • 内存:80428kb
  • [2024-08-24 23:29:01]
  • 提交

answer

//Author: Kevin
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define ll long long
#define ull unsigned ll
#define pb emplace_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
#define longer __int128_t
void die(string S){puts(S.c_str());exit(0);}
const int Count=13,Penalty=20;
const int Thres=400005;
const int B=450;
int n,d,L;
vector<int> vec[200200];
ll l[200200],r[200200];
inline ll gen(int pc,ll tot){return (pc>1)?0:tot;}
int sp[200200];
int val[Thres+25];
vector<int> gen(int ind)
{
	if(sz(vec[ind])>B)
	{
		memset(val,-1,sizeof(val));
		for(int i=0;i<sz(vec[ind]);i++)
			val[vec[ind][i]]=i;
		for(int i=0;i<Thres+5;i++)
			if(val[i]>0)
				val[i+Penalty]=max(val[i+Penalty],val[i]-1);
		vector<int> ret;
		for(int i=0;i<=Thres;i++) if(val[i]!=-1)
			ret.pb(i);
		for(int i=Thres+1;i<Thres+25;i++) if(val[i]!=-1)
		{
			ret.pb(i);
			break;
		}
		return ret;
	}
	else
	{
		vector<int> ret;
		for(int i=0;i<sz(vec[ind]);i++)
			for(int j=0;j<=i;j++)
				ret.pb(j*Penalty+vec[ind][i]);
		srt(ret);
		uni(ret);
		while(sz(ret)>1&&ret[sz(ret)-2]>Thres) ret.pop_back();
		return ret;
	}
}
int s1[400400],s2[400400];
int cnt[400400][30];
int segt[400400*20];
int ls[400400*20],rs[400400*20],tot;
int update(int x,int l,int r,int p,int v)
{
	int ret=++tot;
	segt[ret]=segt[x]+v;
	ls[ret]=ls[x];
	rs[ret]=rs[x];
	if(l==r) return ret;
	int mid=(l+r)/2;
	if(p<=mid)
		ls[ret]=update(ls[x],l,mid,p,v);
	else
		rs[ret]=update(rs[x],mid+1,r,p,v);
	return ret;
}
int query(int x,int l,int r,int ql,int qr)
{
	if(!x) return 0;
	if(l==ql&&r==qr) return segt[x];
	int mid=(l+r)/2;
	if(qr<=mid)
		return query(ls[x],l,mid,ql,qr);
	if(ql>mid)
		return query(rs[x],mid+1,r,ql,qr);
	return query(ls[x],l,mid,ql,mid)+query(rs[x],mid+1,r,mid+1,qr);
}
int rt[400400];
vector<int> vq[400400];
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>d>>L;
	for(int i=1;i<=n;i++)
	{
		int x,y;
		cin>>x>>y;
		vec[x].pb(y);
	}
	int tot=0;
	for(int i=1;i<=d;i++) if(sz(vec[i]))
	{
		tot++;
		int pc=0;
		ll tot=0;
		for(auto x:vec[i])
			if(pc<Count)
			{
				pc++;
				tot+=x;
			}
		l[i]=gen(pc,tot);
		ll tot2=vec[i].back()+(sz(vec[i])-1)*Penalty;
		r[i]=gen(1,tot2);
		if(r[i]>Thres)
			sp[i]=1;
		s1[l[i]]++;
		if(!sp[i])
			s2[r[i]]++;
		if(r[i]-l[i]<30)
			cnt[l[i]][r[i]-l[i]]++;
		vq[l[i]].pb(min(400400ll,r[i]));
	}
	for(int i=0;i<400400;i++)
		for(int j=1;j<30;j++)
			cnt[i][j]+=cnt[i][j-1];
	for(int i=1;i<400400;i++)
	{
		s1[i]+=s1[i-1];
		s2[i]+=s2[i-1];
	}
	for(int i=0;i<400400;i++)
	{
		if(i) rt[i]=rt[i-1];
		for(auto x:vq[i])
			rt[i]=update(rt[i],0,400400,x,1);
	}
	ll ans=0;
	vector<int> vsp;
	for(int i=1;i<=d;i++)
		if(sp[i])
			vsp.pb(i);
	for(int i=1;i<=d;i++)
	{
		vector<int> times=gen(i);
		if(!sz(times)) continue;
		int lst=-1;
		int idx=i;
		for(int i=0;i<sz(times);i++)
		{
			int cur=times[i];
			int L=s1[cur]-(lst>=0?s1[lst]:0);
			int R=s2[400400-1]-(cur>0?s2[cur-1]:0);
			if(l[idx]>lst&&l[idx]<=cur) L--;
			if(r[idx]>=cur&&!sp[idx]) R--;
			lst=cur;
			ans+=1ll*L*R;
		}
		int val=times.back();
		int R=0,L=s1[val];
		if(l[idx]<=val) L--;
		for(auto idx2:vsp)
			if(idx2!=i&&r[idx2]>=val)
				R++;
		ans+=1ll*L*R;
		ans-=(tot)-(s1[400400-1]-s1[val])-(times[0]>0?s2[times[0]-1]:0)-1;
		for(int i=1;i<sz(times);i++)
			if(times[i]-times[i-1]>=30)
				ans+=query(rt[times[i]-1],0,400400,times[i-1]+1,times[i]-1)-query(rt[times[i-1]],0,400400,times[i-1]+1,times[i]-1);
			else
				for(int j=1;j<times[i]-times[i-1];j++)
					ans+=cnt[times[i-1]+j][times[i]-times[i-1]-j-1];
	}
	cout<<ans<<endl;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 8ms
memory: 59524kb

input:

4 3 300
1 10
2 25
2 30
3 50

output:

3

result:

ok 1 number(s): "3"

Test #2:

score: 0
Accepted
time: 12ms
memory: 58808kb

input:

4 6 200000
6 1
6 1
1 2
2 2

output:

4

result:

ok 1 number(s): "4"

Test #3:

score: -100
Wrong Answer
time: 57ms
memory: 80428kb

input:

191580 64997 56
24878 1
35060 1
24245 1
64330 1
9650 1
15423 1
34953 1
21456 1
36718 1
21395 1
17613 1
16995 1
45257 1
31277 1
20026 1
1870 1
25581 1
9997 1
54701 1
30752 1
32269 1
705 1
64186 1
58881 1
24614 1
55311 1
18259 1
58886 1
23296 1
17628 1
3411 1
37469 1
47951 1
12188 1
60720 1
54168 1
45...

output:

274227167195996

result:

wrong answer 1st numbers differ - expected: '274533940012863', found: '274227167195996'