oj.uz

Submission #399629

# Submission time Handle Problem Language Result Execution time Memory
399629 2021-05-06T10:24:04 Z IloveN Fish (IOI08_fish) C++14
0 / 100
 1541 ms 64592 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 39372 KB Output isn't correct

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 39460 KB Output isn't correct

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 39432 KB Output isn't correct

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 39500 KB Output isn't correct

Subtask #5
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 39444 KB Output is correct
2 Incorrect 22 ms 39448 KB Output isn't correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 39440 KB Output is correct
2 Incorrect 1010 ms 58136 KB Output isn't correct

Subtask #7
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 39500 KB Output isn't correct

Subtask #8
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 39668 KB Output isn't correct

Subtask #9
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 429 ms 47592 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 39676 KB Output is correct
2 Incorrect 32 ms 39668 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #11
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 702 ms 53312 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 673 ms 58352 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 420 ms 53400 KB Output is correct
2 Incorrect 1216 ms 59316 KB Output isn't correct

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1202 ms 58204 KB Output isn't correct

Subtask #15
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1344 ms 60624 KB Output isn't correct

Subtask #16
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1027 ms 57000 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #17
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1394 ms 61896 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1155 ms 60696 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1541 ms 64592 KB Output isn't correct
2 Halted 0 ms 0 KB -