QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#532778#9228. ICPC Inferenceucup-team1231#TL 4ms13552kbC++172.1kb2024-08-25 11:39:262024-08-25 11:39:27

Judging History

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

  • [2024-08-25 11:39:27]
  • 评测
  • 测评结果:TL
  • 用时:4ms
  • 内存:13552kb
  • [2024-08-25 11:39:26]
  • 提交

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...

output:


result: