Submission #399629

#	Time	Username	Problem	Language	Result	Execution time	Memory
399629		IloveN	Fish (IOI08_fish)	C++14	0 / 100	1541 ms	64592 KiB

fish

#include<bits/stdc++.h>

using namespace std;
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define all(vr) vr.begin(),vr.end()
#define vi vector<int>
#define vll vector<ll>
const int N = 1e6 + 10;
int mod, n;

struct segment_tree
{
    int it[N * 4], lazy[N * 4];
    void down(int id)
    {
        int tmp = lazy[id];
        it[id * 2] = it[id * 2] * tmp % mod;
        it[id * 2 + 1] = it[id * 2 + 1] * tmp % mod;
        lazy[id * 2] = lazy[id * 2] * tmp % mod;
        lazy[id * 2 + 1] = lazy[id * 2 + 1] * tmp % mod;
        lazy[id] = 1;
    }

    void init()
    {
        memset(lazy, 1, sizeof(lazy));
    }

    void update_single(int pos, int val, int id = 1, int l = 0, int r = n)
    {
        if (l == r)
        {
            it[id] = val;
            return;
        }
        int mid = (l + r) / 2;
        down(id);
        if (pos <= mid) update_single(pos, val, id * 2, l, mid);
        else update_single(pos, val, id * 2 + 1, mid + 1, r);
        it[id] = (it[id * 2] + it[id * 2 + 1]) % mod;
    }

    void update_range(int u, int v, int coef, int id = 1, int l = 0, int r = n)
    {
        if (l > v || r < u) return;
        if (u <= l && r <= v)
        {
            it[id] = it[id] * coef % mod;
            lazy[id] = lazy[id] * coef % mod;
            return;
        }
        int mid = (l + r) / 2;
        down(id);
        update_range(u, v, coef, id * 2, l, mid);
        update_range(u, v, coef, id * 2 + 1, mid + 1, r);
        it[id] = (it[id * 2] + it[id * 2 + 1]) % mod;
    }

    int get(int u, int v, int id = 1, int l = 0, int r = n)
    {
        if (l > v || r < u) return 0;
        if (u <= l && r <= v) return it[id];
        int mid = (l + r) / 2;
        down(id);
        return get(u, v, id * 2, l, mid) + get(u, v, id * 2 + 1, mid + 1, r);
    }
} seg;

int k, lim[N], p[N];
pii a[N];
vi vt[N];

bool cmp(int c1, int c2) { return vt[c1].back() < vt[c2].back(); }

int main()
{
    //freopen("ss.inp", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k >> mod;
    for (int i = 1; i <= n; ++i) cin >> a[i].fi >> a[i].se;
    sort(a + 1, a + n + 1);
    int j = 0;
    for (int i = 1; i <= n; ++i)
    {
        while (a[j].fi * 2 <= a[i].fi) ++j;
        lim[i] = j - 1;
    }
    for (int i = 1; i <= n; ++i) vt[a[i].se].eb(i);
    for (int i = 1; i <= k; ++i) p[i] = i;
    sort(p + 1, p + k + 1, cmp);
    seg.init();
    seg.update_single(0, 1);
    int res = 0;
    for (int i = 1; i <= k; ++i)
    {
        int c = p[i];
        int mx = vt[c].back();
        int coef = 1;
        for (int x : vt[c])
            if (x <= lim[mx]) coef++;
        res = (res + seg.get(0, lim[mx]) % mod * coef) % mod;
        reverse(all(vt[c]));
        for (int x : vt[c]) seg.update_single(x, seg.get(0, x) % mod);
        reverse(all(vt[c]));
        coef = 1;
        for (int i = 0; i < (int)vt[c].size() - 1; ++i)
        {
            int l = vt[c][i] + 1, r = vt[c][i + 1] - 1;
            if (l <= r) seg.update_range(l, r, coef);
            coef++;
        }
        if ((int)vt[c].back() <n) seg.update_range(vt[c].back() + 1, n, coef);
    }
    cout << res;
    return 0;
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 4
• Subtask 3: 0 / 4
• Subtask 4: 0 / 4
• Subtask 5: 0 / 4
• Subtask 6: 0 / 5
• Subtask 7: 0 / 6
• Subtask 8: 0 / 6
• Subtask 9: 0 / 6
• Subtask 10: 0 / 6
• Subtask 11: 0 / 7
• Subtask 12: 0 / 7
• Subtask 13: 0 / 7
• Subtask 14: 0 / 5
• Subtask 15: 0 / 5
• Subtask 16: 0 / 5
• Subtask 17: 0 / 5
• Subtask 18: 0 / 5
• Subtask 19: 0 / 5