oj.uz

답안 #54685

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
54685 2018-07-04T15:18:01 Z SpaimaCarpatilor Fish (IOI08_fish) C++17
41 / 100
 630 ms 66560 KB 
#include<bits/stdc++.h>

using namespace std;

const int maxN = 500000;
int N, K, mod, l[maxN + 9], t[maxN + 9], f[maxN + 9], lastCovered[maxN + 9];
pair < int, int > v[maxN + 9];

void read ()
{
    scanf ("%d %d %d", &N, &K, &mod);
    for (int i=1; i<=N; i++)
        scanf ("%d %d", &v[i].first, &v[i].second);
    sort (v + 1, v + N + 1);
    for (int i=1; i<=N; i++)
        l[i] = v[i].first, t[i] = v[i].second;
}

namespace segtree {
    int aint[4 * maxN + 5];
    void build (int nod, int st, int dr)
    {
        aint[nod] = 1;
        if (st == dr) return ;
        int mij = (st + dr) >> 1, f1 = nod << 1, f2 = f1 | 1;
        build (f1, st, mij);
        build (f2, mij + 1, dr);
    }

    void change (int nod, int st, int dr, int pos, int val)
    {
        if (st == dr)
        {
            aint[nod] = val;
            return ;
        }
        int mij = (st + dr) >> 1, f1 = nod << 1, f2 = f1 | 1;
        if (pos <= mij) change (f1, st, mij, pos, val);
        else change (f2, mij + 1, dr, pos, val);
        aint[nod] = (aint[f1] * aint[f2]) % mod;
    }

    int ansQ;
    void query (int nod, int st, int dr, int x, int y)
    {
        if (x <= st && dr <= y)
        {
            ansQ = (ansQ * aint[nod]) % mod;
            return ;
        }
        int mij = (st + dr) >> 1, f1 = nod << 1, f2 = f1 | 1;
        if (x <= mij) query (f1, st, mij, x, y);
        if (mij < y) query (f2, mij + 1, dr, x, y);
    }

    int prod (int st, int dr)
    {
        ansQ = 1, dr = min (dr, N), st = max (st, 1);
        if (st <= dr) query (1, 1, N, st, dr);
        return ansQ;
    }
}

int minJ[maxN + 9], lst[maxN + 9], nxt[maxN + 9];
void buildMinJ ()
{
    int j = 0;
    for (int i=1; i<=N; i++)
    {
        while (j <= N && l[j] < 2 * l[i]) j ++;
        minJ[i] = j;
    }
}

void buildNxtLst ()
{
    for (int i=1; i<=N; i++)
    {
        if (lst[t[i]] != 0)
            nxt[lst[t[i]]] = i;
        lst[t[i]] = i;
    }
}

int ans = 0;
void computeAnswer ()
{
    int i = 0;
    for (int j=1; j<=N; j++)
    {
        while (l[i + 1] * 2 <= l[j])
            i ++, f[t[i]] ++, lastCovered[t[i]] = i,
            segtree::change (1, 1, N, lst[t[i]], f[t[i]] + 1);
        if (lst[t[j]] == j)
        {
            ///I take the max frequency for t[i]
            int k = minJ[nxt[lastCovered[t[j]]]];
            ans = (ans + segtree::prod (1, j - 1) * segtree::prod (j + 1, k - 1)) % mod;
            ///I take any number of t[i], but the max frequency
            ans = (ans + f[t[j]] * segtree::prod (1, j - 1)) % mod;
        }
    }
}

int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);

read (), segtree::build (1, 1, N);
buildNxtLst ();
buildMinJ ();
computeAnswer ();
printf ("%d\n", ans);
return 0;
}

Compilation message

fish.cpp: In function 'void read()':
fish.cpp:11:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d %d %d", &N, &K, &mod);
     ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:13:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ("%d %d", &v[i].first, &v[i].second);
         ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 376 KB Output is correct

Subtask #2
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct

Subtask #3
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 420 KB Output isn't correct

Subtask #4
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 472 KB Output isn't correct

Subtask #5
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 604 KB Output is correct
2 Correct 4 ms 680 KB Output is correct

Subtask #6
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 812 KB Output is correct
2 Correct 296 ms 22760 KB Output is correct

Subtask #7
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 22760 KB Output isn't correct

Subtask #8
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 22760 KB Output is correct

Subtask #9
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 118 ms 22760 KB Output is correct
2 Correct 168 ms 22760 KB Output is correct

Subtask #10
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 22760 KB Output is correct
2 Incorrect 8 ms 22760 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #11
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 210 ms 27936 KB Output is correct
2 Incorrect 371 ms 39260 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #12
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 321 ms 45344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 173 ms 45344 KB Output is correct
2 Correct 315 ms 56704 KB Output is correct

Subtask #14
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 298 ms 62016 KB Output is correct

Subtask #15
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 341 ms 66560 KB Memory limit exceeded

Subtask #16
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 278 ms 66560 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #17
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 505 ms 66560 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 419 ms 66560 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 630 ms 66560 KB Memory limit exceeded
2 Halted 0 ms 0 KB -