QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#531948 | #9228. ICPC Inference | ucup-team3586# | WA | 62ms | 82224kb | C++23 | 4.0kb | 2024-08-24 23:19:21 | 2024-08-24 23:19:22 |
Judging History
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;
}
}
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: 16ms
memory: 58732kb
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: 11ms
memory: 59548kb
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: 62ms
memory: 82224kb
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'