oj.uz

Submission #234190

# Submission time Handle Problem Language Result Execution time Memory
234190 2020-05-23T13:14:07 Z Leonardo_Paes Fish (IOI08_fish) C++17
0 / 100
 330 ms 22524 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll,ll> pii;

#define f first
#define s second

const int maxn = 5e5+10;

int f, k, m, last[maxn];

ll tree[4*maxn];

pii vet[maxn];

void build(int node, int l, int r){
    if(l == r){
        tree[node] = 1LL;
        return;
    }

    int mid = (l + r) >> 1;

    build(2*node, l, mid), build(2*node+1, mid+1, r);

    tree[node] = (tree[2*node] * tree[2*node+1])%m;
}

void update(int node, int l, int r, int idx, int v){
    if(l == r){
        tree[node] += v;
        return;
    }

    int mid = l + r >> 1;

    if(idx <= mid) update(2*node, l, mid, idx, v);
    else update(2*node+1, mid+1, r, idx, v);

    tree[node] = (tree[2*node] * tree[2*node+1])%m;
}

ll query(int node, int tl, int tr, int l, int r){
    if(tl > r or tr < l) return 1LL;
    if(tl >= l and tr <= r) return tree[node];

    int mid = tl + tr >> 1;

    return (query(2*node, tl, mid, l, r)*query(2*node+1, mid+1, tr, l, r))%m;
}

int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

    cin >> f >> k >> m;

    for(int i=1; i<=f; i++){
        cin >> vet[i].f >> vet[i].s;
        last[vet[i].s] = i;
    }

    sort(vet+1, vet+f+1);

    build(1, 1, f);

    ll ans = 0LL;

    for(int i=1, j=1; i<=f and j<=f; i++){
        while(vet[j].f + vet[j].f <= vet[i].f){
            update(1, 1, f, vet[j].s, 1);
            j++;
        }
        if(last[vet[i].s] == i){
            update(1, 1, f, vet[i].s, 1);
            ans = query(1, 1, f, 1, f);
            update(1, 1, f, vet[i].s, -1);
        }
    }

    cout << (ans-1+m)%m << endl;

    return 0;
}

Compilation message

fish.cpp: In function 'void update(int, int, int, int, int)':
fish.cpp:38:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~
fish.cpp: In function 'll query(int, int, int, int, int)':
fish.cpp:50:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = tl + tr >> 1;
               ~~~^~~~

Subtask #1
0 / 4.0

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

Subtask #2
0 / 4.0

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

Subtask #3
0 / 4.0

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

Subtask #4
0 / 4.0

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

Subtask #5
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Incorrect 5 ms 384 KB Output isn't correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Incorrect 232 ms 22524 KB Output isn't correct

Subtask #7
0 / 6.0

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

Subtask #8
0 / 6.0

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

Subtask #9
0 / 6.0

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

Subtask #10
0 / 6.0

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

Subtask #11
0 / 7.0

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

Subtask #12
0 / 7.0

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

Subtask #13
0 / 7.0

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

Subtask #14
0 / 5.0

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

Subtask #15
0 / 5.0

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

Subtask #16
0 / 5.0

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

Subtask #17
0 / 5.0

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

Subtask #18
0 / 5.0

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

Subtask #19
0 / 5.0

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