oj.uz

Submission #118430

# Submission time Handle Problem Language Result Execution time Memory
118430 2019-06-19T03:04:12 Z briansu Fish (IOI08_fish) C++14
100 / 100
 545 ms 41464 KB 
#include<bits/stdc++.h>
using namespace std;
typedef int 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) % M;
        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 % M;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] % M * 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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 14208 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 14080 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 14080 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14052 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14080 KB Output is correct
2 Correct 15 ms 14080 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 14080 KB Output is correct
2 Correct 154 ms 20564 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 14080 KB Output is correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14208 KB Output is correct

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 16888 KB Output is correct
2 Correct 93 ms 17504 KB Output is correct

Subtask #10
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 14208 KB Output is correct
2 Correct 17 ms 14208 KB Output is correct
3 Correct 15 ms 14208 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 18528 KB Output is correct
2 Correct 183 ms 20556 KB Output is correct
3 Correct 177 ms 20508 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 20924 KB Output is correct
2 Correct 182 ms 21136 KB Output is correct

Subtask #13
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 18408 KB Output is correct
2 Correct 191 ms 20756 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 20760 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 21680 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 20252 KB Output is correct
2 Correct 367 ms 24500 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 394 ms 25208 KB Output is correct
2 Correct 290 ms 23824 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 293 ms 26024 KB Output is correct
2 Correct 395 ms 24440 KB Output is correct
3 Correct 316 ms 28632 KB Output is correct
4 Correct 407 ms 24312 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 494 ms 27640 KB Output is correct
2 Correct 435 ms 41396 KB Output is correct
3 Correct 438 ms 41464 KB Output is correct
4 Correct 545 ms 36796 KB Output is correct