oj.uz

Submission #653079

# Submission time Handle Problem Language Result Execution time Memory
653079 2022-10-25T15:18:28 Z Vladth11 Fish (IOI08_fish) C++14
0 / 100
 677 ms 32452 KB 
#include <iostream>
#include <vector>
#include <set>
#include <unordered_set>
#include <algorithm>

#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "

#pragma GCC optimize("Ofast")

using namespace std;
typedef long long ll;
typedef pair <int, int> pii;

const int bSize = 11;
const int bits = 17;
const int NMAX = 500001;

int MOD;

class AINT {
public:
    int aint[NMAX * 4];
    void init() {
        for(int i = 0; i < NMAX * 4; i++)
            aint[i] = 1;
    }
    void add(int node, int st, int dr, int l, int x) {
        if(st == dr) {
            aint[node] += x;
            aint[node] = max(aint[node], 1);
            return;
        }
        int mid = (st + dr) / 2;
        if(l <= mid) {
            add(node * 2, st, mid, l, x);
        } else {
            add(node * 2 + 1, mid + 1, dr, l, x);
        }
        aint[node] = aint[node * 2] * aint[node * 2 + 1];
        aint[node] %= MOD;
    }
    void update(int node, int st, int dr, int l, int x) {
        if(st == dr) {
            aint[node] = x;
            aint[node] = max(aint[node], 1);
            return;
        }
        int mid = (st + dr) / 2;
        if(l <= mid) {
            update(node * 2, st, mid, l, x);
        } else {
            update(node * 2 + 1, mid + 1, dr, l, x);
        }
        aint[node] = aint[node * 2] * aint[node * 2 + 1];
        aint[node] %= MOD;
    }
} aint, banned;

int imp[NMAX];
int col[NMAX];
int maxi[NMAX];
pii v[NMAX];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, k, i;
    cin >> n >> k >> MOD;
    for(i = 1; i <= n; i++) {
        cin >> v[i].first >> v[i].second;
    }
    sort(v + 1, v + n + 1);
    for(i = n; i >= 1; i--) {
        if(!col[v[i].second]) {
            imp[i] = 1;
        }
        col[v[i].second]++;
    }
    aint.init();
    banned.init();
    for(i = 1; i <= n; i++){
        maxi[i] = col[i];
        aint.update(1, 1, n, i, col[i] + 1);
        banned.update(1, 1, n, i, col[i] + 1);
    }
    int dr = n + 1, st = n;
    ll rez = 0;
    for(i = n; i >= 1; i--){
        while(st >= 1 && v[st].first * 2 > v[i].first){
            aint.add(1, 1, n, v[st].second, -1);
            banned.add(1, 1, n, v[st].second, -1);
            col[v[st].second]--;
            st--;
        }
        if(imp[i]){
            rez += banned.aint[1];
            rez %= MOD;
            if(imp[i] && v[i].first * 2 > v[n].first && i != n && maxi[v[i].second] - 1 == col[v[i].second]){
                rez += aint.aint[1];
                rez %= MOD;
            }
        }
        //aint.update(1, 1, n, v[i].second, 1);
        banned.update(1, 1, n, v[i].second, 1);
    }
    cout << rez;
    return 0;
}

Compilation message

fish.cpp: In function 'int main()':
fish.cpp:89:9: warning: unused variable 'dr' [-Wunused-variable]
   89 |     int dr = n + 1, st = n;
      |         ^~

Subtask #1
0 / 4.0

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

Subtask #2
0 / 4.0

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

Subtask #3
0 / 4.0

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

Subtask #4
0 / 4.0

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

Subtask #5
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15952 KB Output is correct
2 Incorrect 7 ms 15956 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15956 KB Output is correct
2 Incorrect 524 ms 27896 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 6.0

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

Subtask #8
0 / 6.0

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

Subtask #9
0 / 6.0

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

Subtask #10
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 16072 KB Output is correct
2 Correct 12 ms 16188 KB Output is correct
3 Incorrect 12 ms 16084 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #11
0 / 7.0

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

Subtask #12
0 / 7.0

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

Subtask #13
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 299 ms 25032 KB Output is correct
2 Incorrect 555 ms 29128 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

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

Subtask #15
0 / 5.0

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

Subtask #16
0 / 5.0

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

Subtask #17
0 / 5.0

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

Subtask #18
0 / 5.0

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

Subtask #19
0 / 5.0

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