Submission #865201

#	Time	Username	Problem	Language	Result	Execution time	Memory
865201		HuyQuang_re_Zero	Fish (IOI08_fish)	C++14	100 / 100	477 ms	65536 KiB

fish

#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 / 4
• Subtask 2: 4 / 4
• Subtask 3: 4 / 4
• Subtask 4: 4 / 4
• Subtask 5: 4 / 4
• Subtask 6: 5 / 5
• Subtask 7: 6 / 6
• Subtask 8: 6 / 6
• Subtask 9: 6 / 6
• Subtask 10: 6 / 6
• Subtask 11: 7 / 7
• Subtask 12: 7 / 7
• Subtask 13: 7 / 7
• Subtask 14: 5 / 5
• Subtask 15: 5 / 5
• Subtask 16: 5 / 5
• Subtask 17: 5 / 5
• Subtask 18: 5 / 5
• Subtask 19: 5 / 5