QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#532788 | #9220. Bus Analysis | ucup-team1231# | WA | 3ms | 40664kb | C++17 | 3.6kb | 2024-08-25 11:51:56 | 2024-08-25 11:51:56 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define SZ 200077
typedef pair<int,int> pii;
#define fi first
#define se second
#define pb push_back
typedef long long ll;
#define lg lg__
pii lg[SZ];
int n,d,L,sm[SZ];
const int S=400;
vector<int> g[SZ],GT;
#define all(s) s.begin(),s.end()
int qs[SZ],pf[SZ],ms[SZ];
#define sz(s) (int)(s).size()
ll ans=0;
void large(int x) {
auto&G=g[x];
for(int i=0;i<=L;++i) qs[i]=0;
for(int j=0;j<G.size();++j) {
++qs[G[j]];
--qs[min(G[j]+(j+1)*20,L+1)];
}
for(int i=1;i<=L;++i) if(i>=20) qs[i]+=qs[i-20];
static int anx[SZ],cge[SZ];
anx[L+1]=L+1; cge[L+1]=0;
for(int i=L;i>=0;--i) cge[i]=0;
for(int i=L;i>=0;--i)
if(qs[i]) anx[i]=i;
else anx[i]=anx[i+1];
for(int i:GT) if(i!=x) ++cge[sm[i]];
for(int i=L;i>=0;--i) cge[i]+=cge[i+1];
for(int i:GT) if(i!=x) {
int nx;
if(lg[i].se==1) {
nx=anx[lg[i].fi];
}
else {
if(ms[x]>=lg[i].fi) nx=0;
else nx=anx[0];
}
ans+=cge[nx];
ans-=sm[i]>=nx;
}
}
const int B=500;
int bsum[SZ],bpref[SZ];
void edt(int x,int y) {
int b=x/B;
for(int j=b;j<=L/B;++j) bsum[j]+=y;
for(int j=x;j/B==b;++j) bpref[j]+=y;
}
int qry(int x) {
if(x<0) return 0;
int ans=bpref[x];
if(x/B) ans+=bsum[x/B-1];
return ans;
}
int main() {
scanf("%d%d%d",&n,&d,&L); L+=61;
for(int i=1;i<=n;++i) {
int x,y;
scanf("%d%d",&x,&y);
g[x].push_back(y);
}
for(int i=1;i<=d;++i) if(g[i].size()) GT.push_back(i);
for(int i:GT) {
sort(all(g[i]));
if(g[i].size()>=3) lg[i]=pii(0,2);
else if(g[i].size()>=2) lg[i]=pii(g[i][0]+g[i][1],2);
else lg[i]=pii(g[i][0],1);
sm[i]=min(g[i].back()+(sz(g[i])-1)*20,L);
}
static int cntworse[SZ],cntbetter[SZ*3];
static vector<pii> event[SZ*3],ei[SZ*3];
for(int i:GT) {
int ss = lg[i].fi+(lg[i].se==1)*(L*2);
ei[ss].pb(pii(i,i));
cntworse[sm[i]]++,cntbetter[ss]++;
}
// suffix sum on cntworse and prefix on cntbetter
for(int i=1;i<=L;++i) cntworse[i]+=cntworse[i-1];
for(int i=L*3;i>=0;--i) cntbetter[i]+=cntbetter[i+1];
for(int i:GT) {
auto&G=g[i];
if(G.size()<2) ms[i]=-1;
else {
ms[i]=G.back()+G[sz(G)-2]+20*(sz(G)-2);
ms[i]=min(ms[i],L+L);
}
if(0) {
large(i);
continue;
}
vector<int> S;
for(int u=0;u<sz(G);++u) {
for(int z=0;z<=u&&G[u]+20*z<=L;++z) {
S.push_back(G[u]+20*z);
}
}
sort(all(S));reverse(all(S));
ll last_cnt_worse=0;
int prev=L+1;
for(int t:S) {
ll cnt_better = cntbetter[t+L*2]-1;
ll cnt_worse = cntworse[t]-1;
ans += cnt_better * (cnt_worse - last_cnt_worse);
last_cnt_worse = cnt_worse;
event[t+L*2].push_back(pii(t, prev-1));
prev = t;
}
if(ms[i]!=-1)
{
ll cnt_better = cntbetter[ms[i]]-1;
ll cnt_worse = n-1;
ans += cnt_better * (cnt_worse - last_cnt_worse);
event[ms[i]].push_back(pii(0, prev-1));
}
}
for(int i=L*3;i>=0;--i) {
for(auto p:ei[i]) {
int x=p.fi,y=p.se;
edt(y,1);
}
for(auto p:event[i]) {
int x=p.fi,y=p.se;
ans+=qry(y)-qry(x-1);
}
}
cout<<ans<<"\n";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 3ms
memory: 40664kb
input:
3 1 8 20
output:
0
result:
wrong answer 1st numbers differ - expected: '14', found: '0'