Submission #118429

#	Time	Username	Problem	Language	Result	Execution time	Memory
118429		briansu	Fish (IOI08_fish)	C++14	100 / 100	777 ms	55292 KiB

fish

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
#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 pb push_back
const ll MAXn=5e5+5;
ll M;
namespace seg{
    int N;
    ll d[2 * MAXn];
    void init(int n, ll *di){
        N = n + 1;
        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_base::sync_with_stdio(0);cin.tie(0);
    ll n, m;
    cin>>n>>m>>M;
    REP1(i,n)cin>>d[i].X>>d[i].Y;
    sort(d + 1, d + 1 + n, greater<ii>());
    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] ++;
    seg::init(m, ct);
    ll tt = 0, it = 1;
    FILL(u, 0);
    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;
        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;
    }
    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