oj.uz

Submission #118429

# Submission time Handle Problem Language Result Execution time Memory
118429 2019-06-19T03:00:23 Z briansu Fish (IOI08_fish) C++14
100 / 100
 777 ms 55292 KB 
#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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 16000 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 16128 KB Output is correct

Subtask #3
4.0 / 4.0

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

Subtask #4
4.0 / 4.0

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

Subtask #5
4.0 / 4.0

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

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 16128 KB Output is correct
2 Correct 170 ms 28480 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 16000 KB Output is correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 16128 KB Output is correct

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 21720 KB Output is correct
2 Correct 104 ms 22812 KB Output is correct

Subtask #10
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 16256 KB Output is correct
2 Correct 19 ms 16304 KB Output is correct
3 Correct 19 ms 16256 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 24744 KB Output is correct
2 Correct 225 ms 28712 KB Output is correct
3 Correct 209 ms 28940 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 29480 KB Output is correct
2 Correct 229 ms 30300 KB Output is correct

Subtask #13
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 24696 KB Output is correct
2 Correct 234 ms 29408 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 28852 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 293 ms 30808 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 255 ms 27900 KB Output is correct
2 Correct 494 ms 34552 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 570 ms 35320 KB Output is correct
2 Correct 395 ms 31224 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 410 ms 35832 KB Output is correct
2 Correct 576 ms 34524 KB Output is correct
3 Correct 430 ms 38752 KB Output is correct
4 Correct 555 ms 34652 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 741 ms 38504 KB Output is correct
2 Correct 659 ms 55160 KB Output is correct
3 Correct 651 ms 55292 KB Output is correct
4 Correct 777 ms 49116 KB Output is correct