oj.uz

Submission #265478

# Submission time Handle Problem Language Result Execution time Memory
265478 2020-08-14T21:52:05 Z evpipis Fish (IOI08_fish) C++11
100 / 100
 788 ms 20216 KB 
#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], tree[4*len];

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

int sub(int a, int b){
    return (m+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 solve(){
    /// now fix big[], pos[]
    for (int i = 1; i <= k; i++)
        pos[i] = -1;

    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++;

    for (int i = 1; i <= k; i++)
        pos[i] = k-pos[i]-1;
    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
    build(1, 0, k-1);

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

        int full = mul(query(1, 0, k-1, 0, i-1), query(1, 0, k-1, i+1, fir[i]-1));
        int par = mul(query(1, 0, k-1, 0, i-1), sub(query(1, 0, k-1, i, i), 1));

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

    return ans;
}

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

    printf("%d\n", solve());
    return 0;
}

Compilation message

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

Subtask #1
4.0 / 4.0

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

Subtask #2
4.0 / 4.0

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

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 201 ms 4328 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 1912 KB Output is correct
2 Correct 112 ms 2296 KB Output is correct

Subtask #10
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 2808 KB Output is correct
2 Correct 265 ms 4472 KB Output is correct
3 Correct 239 ms 4472 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 4344 KB Output is correct
2 Correct 266 ms 4344 KB Output is correct

Subtask #13
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 2856 KB Output is correct
2 Correct 254 ms 4728 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 242 ms 4232 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 282 ms 4984 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 248 ms 5112 KB Output is correct
2 Correct 292 ms 7672 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 413 ms 9464 KB Output is correct
2 Correct 338 ms 8312 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 405 ms 9592 KB Output is correct
2 Correct 381 ms 7672 KB Output is correct
3 Correct 478 ms 10976 KB Output is correct
4 Correct 400 ms 7800 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 540 ms 11060 KB Output is correct
2 Correct 788 ms 20216 KB Output is correct
3 Correct 588 ms 20088 KB Output is correct
4 Correct 747 ms 17912 KB Output is correct