Submission #118421

#	Time	Username	Problem	Language	Result	Execution time	Memory
118421		briansu	Fish (IOI08_fish)	C++14	100 / 100	1022 ms	58736 KiB

fish

//{
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double lf;
typedef pair<ll,ll> ii;
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define FILL(i,n) memset(i,n,sizeof i)
#define X first
#define Y second
#define SZ(_a) (int)_a.size()
#define ALL(_a) _a.begin(),_a.end()
#define pb push_back
#ifdef brian
#define debug(...) do{\
    fprintf(stderr,"%s - %d (%s) = ",__PRETTY_FUNCTION__,__LINE__,#__VA_ARGS__);\
    _do(__VA_ARGS__);\
}while(0)
template<typename T>void _do(T &&_x){cerr<<_x<<endl;}
template<typename T,typename ...S> void _do(T &&_x,S &&..._t){cerr<<_x<<" ,";_do(_t...);}
template<typename _a,typename _b> ostream& operator << (ostream &_s,const pair<_a,_b> &_p){return _s<<"("<<_p.X<<","<<_p.Y<<")";}
template<typename It> ostream& _OUTC(ostream &_s,It _ita,It _itb)
{
    _s<<"{";
    for(It _it=_ita;_it!=_itb;_it++)
    {
        _s<<(_it==_ita?"":",")<<*_it;
    }
    _s<<"}";
    return _s;
}
template<typename _a> ostream &operator << (ostream &_s,vector<_a> &_c){return _OUTC(_s,ALL(_c));}
template<typename _a> ostream &operator << (ostream &_s,set<_a> &_c){return _OUTC(_s,ALL(_c));}
template<typename _a,typename _b> ostream &operator << (ostream &_s,map<_a,_b> &_c){return _OUTC(_s,ALL(_c));}
template<typename _t> void pary(_t _a,_t _b){_OUTC(cerr,_a,_b);cerr<<endl;}
#define IOS()
#else
#define debug(...)
#define pary(...)
#define endl '\n'
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#endif // brian
//}


const ll MAXn=5e5+5,MAXlg=__lg(MAXn)+2;
const ll INF=ll(1e15);

ll M;

namespace seg{
    int N;
    ll d[2 * MAXn];
    void init(int n, ll *di)
    {
        N = n + 1;
        d[N] = 0;
        for(int i = 1;i <= n;i ++)d[N + i] = di[i] + 1;
        for(int i = N - 1;i > 0;i--)d[i] = d[i<<1] * d[i<<1|1] % M;
    }
    void ins(ll x, ll k)
    {
        for(d[x += N] = k;x > 1;x >>= 1)d[x>>1] = d[x] * d[x^1] % M;
    }
    ll qr(int l, int r)
    {
        ll ret = 1;
        for(l += N, r += N;l < r;l>>=1, r>>=1)
        {
            if(l&1)ret = ret * d[l++] % M;
            if(r&1)ret = ret * d[--r] % M;
        }
        return ret;
    }
};


ii d[MAXn];
ll u[MAXn], ct[MAXn], mxsz[MAXn];

vector<ll> v[MAXn];

int main()
{
    IOS();
    ll n, m;
    cin>>n>>m;
    cin>>M;
    REP1(i,n)cin>>d[i].X>>d[i].Y;
    sort(d + 1, d + 1 + n, greater<ii>());
    pary(d + 1, d + 1 + n);

    // relabel
    {
        ll nit = m;
        REP1(i, n)
        {
            if(u[d[i].Y])d[i].Y = u[d[i].Y];
            else d[i].Y = u[d[i].Y] = nit--, mxsz[d[i].Y] = d[i].X;
        }
    }

    for(int i = n;i > 0;i --)v[d[i].Y].pb(i), ct[d[i].Y] ++;
    pary(d + 1, d + 1 + n);

    seg::init(m, ct);

    FILL(u, 0);

    ll tt = 0, it = 1;

    REP1(i, n)if(!u[d[i].Y]){
        u[d[i].Y] = 1;
        while(it <= n && d[it].X * 2 > d[i].X)
        {
            ct[d[it].Y]--;
            seg::ins(d[it].Y, ct[d[it].Y] + 1);
            it ++;
        }
        if(ct[d[i].Y] > 0)tt = (tt + ct[d[i].Y] * seg::qr(1, d[i].Y)) % M;
        debug(d[i].Y, tt);
        ll t = lower_bound(mxsz + 1, mxsz + 1 + m, d[v[d[i].Y][ct[d[i].Y]]].X * 2) - mxsz;
        tt = (tt + seg::qr(d[i].Y + 1, t) * seg::qr(1, d[i].Y)) % M;
        debug(d[i].Y, tt, t);
    }
    cout<<tt<<endl;
}

• 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