oj.uz

Submission #865201

# Submission time Handle Problem Language Result Execution time Memory
865201 2023-10-24T06:29:36 Z HuyQuang_re_Zero Fish (IOI08_fish) C++14
100 / 100
 477 ms 65536 KB 
#include <bits/stdc++.h>
#define ll long long
#define db long double
#define N 1000005
#define II pair <int,int>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define Log(x) (31-__builtin_clz((int)x))
#define LogLL(x) (63-__builtin_clzll((ll)x))
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
using namespace std;
II a[N],b[N];
ll n,m,i,j,u,v,res,mod;
int order[N],cnt[N];
vector <int> vec[N];
struct Interval_Tree
{
    int st[4*N];
    void build(int id,int l,int r)
    {
        st[id]=1;
        if(l==r) return ;
        int mid=(l+r)>>1;
        build(id*2,l,mid); build(id*2+1,mid+1,r);
    }
    void update(int id,int l,int r,int u)
    {
        if(u<l || u>r) return ;
        if(l==r) { st[id]=(st[id]+1)%mod; return ; }
        int mid=(l+r)>>1;
        update(id*2,l,mid,u); update(id*2+1,mid+1,r,u);
        st[id]=(ll)st[id*2]*st[id*2+1]%mod;
    }
    ll get(int id,int l,int r,int u,int v)
    {
        if(u>r || v<l) return 1;
        if(u<=l && r<=v) return st[id];
        int mid=(l+r)>>1;
        return get(id*2,l,mid,u,v)*get(id*2+1,mid+1,r,u,v)%mod;
    }
} IT;
int main()
{
  //  freopen("fish.inp","r",stdin);
    //freopen("fish.out","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>m>>mod;
    for(i=1;i<=n;i++)
    {
        cin>>a[i].fst>>a[i].snd;
        b[a[i].snd].fst=max(b[a[i].snd].fst,a[i].fst);
        cnt[a[i].snd]++;
    }
    for(i=1;i<=m;i++) b[i].snd=i;
    sort(a+1,a+n+1);
    sort(b+1,b+m+1);
    for(i=1;i<=m;i++) order[b[i].snd]=i;
    IT.build(1,1,m);
    j=0;
    for(i=1;i<=n;i++)
    {
        cnt[a[i].snd]--;
        vec[a[i].snd].push_back(a[i].fst);
        while(a[j+1].fst*2<=a[i].fst) IT.update(1,1,m,order[a[++j].snd]);
        ll pre=IT.get(1,1,m,1,order[a[i].snd]-1),last=0;

        if(cnt[a[i].snd]==0)
        {
            for(int x:vec[a[i].snd])
            {
                if(a[i].fst<2*last) break;
                int l=order[a[i].snd],r=m;
                while(l<r)
                {
                    int mid=(l+r+1)>>1;
                    if(b[mid].fst<2*x) l=mid; else r=mid-1;
                }
                res=(res+pre*IT.get(1,1,m,order[a[i].snd]+1,l))%mod;
                last=x;
            }
        }
    }
    cout<<res;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 31068 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 31068 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 31068 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 31068 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 31320 KB Output is correct
2 Correct 6 ms 31068 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 31068 KB Output is correct
2 Correct 132 ms 37716 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 31064 KB Output is correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 31068 KB Output is correct

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 34384 KB Output is correct
2 Correct 85 ms 34792 KB Output is correct

Subtask #10
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 31324 KB Output is correct
2 Correct 8 ms 31068 KB Output is correct
3 Correct 8 ms 31068 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 35124 KB Output is correct
2 Correct 198 ms 37536 KB Output is correct
3 Correct 190 ms 38088 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 38100 KB Output is correct
2 Correct 210 ms 38528 KB Output is correct

Subtask #13
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 35076 KB Output is correct
2 Correct 209 ms 40124 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 40272 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 42956 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 41940 KB Output is correct
2 Correct 218 ms 46752 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 333 ms 47624 KB Output is correct
2 Correct 230 ms 45240 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 322 ms 48632 KB Output is correct
2 Correct 308 ms 46676 KB Output is correct
3 Correct 328 ms 50376 KB Output is correct
4 Correct 329 ms 46736 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 427 ms 49388 KB Output is correct
2 Correct 403 ms 65536 KB Output is correct
3 Correct 364 ms 65536 KB Output is correct
4 Correct 477 ms 65536 KB Output is correct