oj.uz

Submission #590170

# Submission time Handle Problem Language Result Execution time Memory
590170 2022-07-05T15:31:49 Z Bench0310 Fish (IOI08_fish) C++17
0 / 100
 666 ms 25896 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 8148 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 8148 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 8148 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 8140 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 8148 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 8148 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 8172 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 8280 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 181 ms 14524 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 8148 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 337 ms 18052 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 347 ms 24016 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 174 ms 18276 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 508 ms 23372 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #15
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 548 ms 25380 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #16
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 310 ms 22196 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #17
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 601 ms 24076 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 424 ms 22092 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 666 ms 25896 KB Output isn't correct
2 Halted 0 ms 0 KB -