Submission #590170

#	Time	Username	Problem	Language	Result	Execution time	Memory
590170		Bench0310	Fish (IOI08_fish)	C++17	0 / 100	666 ms	25896 KiB

fish

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int mod;
int add(int a,int b){return a+b-(a+b>=mod?mod:0);}
int sub(int a,int b){return a-b+(a-b<0?mod:0);}
int mul(int a,int b){return (a*b)%mod;}

const int N=500005;
int tree[4*N];
array<int,2> fish[N];
array<int,2> gems[N];
int two[N];

void update(int idx,int l,int r,int pos,int x)
{
    if(l==r) tree[idx]=add(tree[idx],x);
    else
    {
        int m=(l+r)/2;
        if(pos<=m) update(2*idx,l,m,pos,x);
        else update(2*idx+1,m+1,r,pos,x);
        tree[idx]=mul(tree[2*idx],tree[2*idx+1]);
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,m;
    cin >> n >> m >> mod;
    for(int i=0;i<4*N;i++) tree[i]=1;
    for(int i=0;i<n;i++) cin >> fish[i][0] >> fish[i][1];
    sort(fish,fish+n);
    for(int i=0;i<n;i++) gems[i]={fish[i][1],i};
    sort(gems,gems+n);
    int p=-1;
    int res=0;
    two[0]=1;
    for(int i=1;i<=n;i++) two[i]=mul(two[i-1],2);
    for(int i=0;i<n;i++)
    {
        auto [len,g]=fish[i];
        while(2*fish[p+1][0]<=fish[i][0]) update(1,1,m,fish[++p][1],1);
        int nxt=gems[lower_bound(gems,gems+n,array<int,2>{g,p+1})-gems][1];
        int inc=lower_bound(fish,fish+n,array<int,2>{2*fish[nxt][0],0})-fish; //[inc,n-1] includes g
        int c=(lower_bound(gems,gems+n,array<int,2>{g,inc})-upper_bound(gems,gems+n,array<int,2>{g,p+1}))/sizeof(int);
        int A=c+n-inc;
        int B=n-i-1-A;
        //cout << "i=" << i << ", A=" << A << " B=" << B << endl;
        //cout << "p=" << p << ", nxt=" << nxt << ", inc=" << inc << endl;
        //cout << "tree[1]=" << tree[1] << endl;
        //only A
        if(A==0)
        {
            update(1,1,m,g,1);
            res=add(res,tree[1]);
            //cout << "adding g, tree[1]=" << tree[1] << endl;
            update(1,1,m,g,mod-1);
        }
        //only B
        if(B>0) res=sub(res,tree[1]);
        //both
        if(A>0&&B>0)
        {
            for(int ca=0;ca<2;ca++)
            {
                for(int cb=0;cb<2;cb++)
                {
                    int r=(ca^cb^1);
                    int oa=two[A-1];
                    if(ca==0) oa=sub(oa,1);
                    int ob=two[B-1];
                    if(cb==0) ob=sub(ob,1);
                    if(r==1) res=add(res,mul(tree[1],mul(oa,ob)));
                    else res=sub(res,mul(tree[1],mul(oa,ob)));
                }
            }
        }
    }
    cout << sub(res,1) << "\n";
    return 0;
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 4
• Subtask 3: 0 / 4
• Subtask 4: 0 / 4
• Subtask 5: 0 / 4
• Subtask 6: 0 / 5
• Subtask 7: 0 / 6
• Subtask 8: 0 / 6
• Subtask 9: 0 / 6
• Subtask 10: 0 / 6
• Subtask 11: 0 / 7
• Subtask 12: 0 / 7
• Subtask 13: 0 / 7
• Subtask 14: 0 / 5
• Subtask 15: 0 / 5
• Subtask 16: 0 / 5
• Subtask 17: 0 / 5
• Subtask 18: 0 / 5
• Subtask 19: 0 / 5