QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#532778 | #9228. ICPC Inference | ucup-team1231# | TL | 4ms | 13552kb | C++17 | 2.1kb | 2024-08-25 11:39:26 | 2024-08-25 11:39:27 |
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;
if(G.size()<2) ms[x]=-1;
else {
ms[x]=G.back()+G[sz(G)-2]+20*(sz(G)-2);
}
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;
}
}
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);
}
for(int i:GT) {
if(1) {
large(i);
continue;
}
auto&G=g[i];
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));
for(int t:S) {
}
}
cout<<ans<<"\n";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 11844kb
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: 4ms
memory: 13552kb
input:
4 6 200000 6 1 6 1 1 2 2 2
output:
4
result:
ok 1 number(s): "4"
Test #3:
score: -100
Time Limit Exceeded
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...