Submission #265427

#	Time	Username	Problem	Language	Result	Execution time	Memory
265427		evpipis	Fish (IOI08_fish)	C++11	4 / 100	3085 ms	16888 KiB

fish

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef pair<int, int> ii;

const int len = 5e5+5;
int n, k, m;
ii fish[len], big[len];
int fir[len], cnt[len], pos[len], mx[len];
//ii fish[len];
//int tree[4*len], vis[len], big[len];



int add(int a, int b){
    return (a+b)%m;
}

int mul(int a, int b){
    return (a*1LL*b)%m;
}

/*void build(int p, int l, int r){
    if (l == r)
        return void(tree[p] = 1);

    int mid = (l+r)/2;
    build(2*p, l, mid);
    build(2*p+1, mid+1, r);

    tree[p] = mul(tree[2*p], tree[2*p+1]);
}

void update(int p, int l, int r, int i){
    if (l == r)
        return void(tree[p] = add(tree[p], 1));

    int mid = (l+r)/2;
    if (i <= mid)
        update(2*p, l, mid, i);
    else
        update(2*p+1, mid+1, r, i);

    tree[p] = mul(tree[2*p], tree[2*p+1]);
}

int query(int p, int l, int r, int i, int j){
    if (r < i || j < l)
        return 1;
    if (i <= l && r <= j)
        return tree[p];

    int mid = (l+r)/2;
    return mul(query(2*p, l, mid, i, j), query(2*p+1, mid+1, r, i, j));
}

int without(int i){
    return mul(query(1, 1, k, 1, i-1), query(1, 1, k, i+1, k));
}

void print(int p = 1, int l = 1, int r = k){
    if (l == r)
        return void(printf("%d ", tree[p]));

    int mid = (l+r)/2;
    print(2*p, l, mid);
    print(2*p+1, mid+1, r);

    if (p == 1)
        printf("\n");
}*/

int main(){
    /// read input
    scanf("%d %d %d", &n, &k, &m);
    for (int i = 0; i < n; i++)
        scanf("%d %d", &fish[i].fi, &fish[i].se);

    //for (int i = 0; i < n; i++)
      //  printf("fish")

    /// now fix big[], pos[]
    for (int i = 1; i <= k; i++)
        pos[i] = -1;

    sort(fish, fish+n);
    for (int i = n-1, j = 0; i >= 0; i--)
        if (pos[fish[i].se] == -1)
            big[j] = fish[i], pos[fish[i].se] = j++;
    reverse(big, big+k);

    /// fix fir[]
    for (int i = 1; i <= k; i++)
        cnt[i] = 0, mx[i] = -1;
    for (int i = 0; i < k; i++)
        fir[i] = k;

    for (int i = 0, j = 0; i < k; i++){
        while (big[i].fi >= 2*fish[j].fi){
            cnt[fish[j].se]++;
            if (cnt[fish[j].se] == mx[fish[j].se])
                fir[pos[fish[j].se]] = i;
            j++;
        }

        mx[big[i].se] = cnt[big[i].se]+1;
    }

    /// compute the answer
    for (int i = 1; i <= k; i++)
        cnt[i] = 0;

    int ans = 0;
    for (int i = 0, j = 0; i < k; i++){
        while (big[i].fi >= 2*fish[j].fi)
            cnt[fish[j++].se]++;

        int full = 1, par = 1;
        for (int f = 0; f < k; f++){
            int c = cnt[big[f].se];

            if (f < i)
                full = mul(full, c+1), par = mul(par, c+1);
            else if (f == i)
                par = mul(par, c);
            else if (f < fir[i])
                full = mul(full, c+1);
        }

        ans = add(ans, add(full, par));
    }

    printf("%d\n", ans);

    /*build(1, 1, k);

    for (int i = 0; i < n; i++)
        printf("fish#%d: %d %d, big = %d\n", i, fish[i].fi, fish[i].se, big[i]);

    int ans = m-1;
    for (int i = 0, j = 0; i < n; i++){
        while (fish[i].fi >= 2*fish[j].fi)
            update(1, 1, k, fish[j].se), j++;

        if (big[i])
            ans = add(ans, without(fish[i].se));

        if (big[i])
            printf("I am in big, i = %d\n", i), print();
    }

    ans = add(ans, tree[1]);*/
    return 0;
}

Compilation message (stderr)

fish.cpp: In function 'int main()':
fish.cpp:79:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   79 |     scanf("%d %d %d", &n, &k, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:81:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   81 |         scanf("%d %d", &fish[i].fi, &fish[i].se);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 4 / 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