oj.uz

Submission #653314

# Submission time Handle Problem Language Result Execution time Memory
653314 2022-10-26T14:19:02 Z Vladth11 Fish (IOI08_fish) C++14
75 / 100
 1282 ms 59132 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 = 23;
const int NMAX = 500001;
 
int MOD;
int dm;
 
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);
          	aint[node] %= MOD;
            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;
    }
    int query(int node, int st, int dr, int a, int b){
        if(a <= st && dr <= b)
            return aint[node];
        int mid = (st + dr) / 2;
        int prod = 1;
        if(a <= mid){
            prod *= query(node * 2, st, mid, a, b);
            prod %= MOD;
        }
        if(b > mid){
            prod *= query(node * 2 + 1, mid + 1, dr, a, b);
            prod %= MOD;
        }
        return prod;
    }
    void update(int node, int st, int dr, int l, int x) {
        if(st == dr) {
            dm = aint[node];
            aint[node] = x;
          	aint[node] %= MOD;
            //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 f[NMAX];
pii cine[NMAX];
vector <int> g[NMAX];
 
int afla(int x, int col){
    int r = -1;
    int pas = (1 << bits);
    while(pas){
        if(r + pas < g[col].size() && g[col][r + pas] * 2 <= x)
            r += pas;
        pas /= 2;
    }
    return r;
}
 
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;
        g[v[i].second].push_back(v[i].first);
    }
    sort(v + 1, v + n + 1);
    for(i = n; i >= 1; i--) {
        if(!col[v[i].second]) {
            imp[i] = 1;
        }
        col[v[i].second]++;
    }
    int cnt = 0;
    for(i = 1; i <= n; i++){
        if(imp[i]){
            cine[++cnt] = v[i];
            f[cine[cnt].second] = cnt;
        }
    }
    aint.init();
    banned.init();
    for(i = 1; i <= n; i++){
        sort(g[i].begin(), g[i].end());
        maxi[i] = col[i];
        if(!f[i]) continue;
        aint.update(1, 1, n, f[i], col[i] + 1);
        banned.update(1, 1, n, f[i], col[i] + 1);
    }
    int dr = n, st = n;
    int rez = 0;
    for(i = n; i >= 1; i--){
        while(st >= 1 && v[st].first * 2 > v[i].first){
            aint.add(1, 1, n, f[v[st].second], -1);
            banned.add(1, 1, n, f[v[st].second], -1);
            col[v[st].second]--;
            st--;
        }
        if(i == n){
            for(int j = 1; j <= n; j++){
                maxi[j] = col[j];
            }
        }
        if(imp[i]){
            if(i != n){
                aint.update(1, 1, n, f[v[i].second], 1);
                int r = f[v[i].second];
                int pas = (1 << bits);
                while(pas){
                    if(r + pas <= k && v[i].first * 2 > cine[r + pas].first && col[v[i].second] - 1 == afla(cine[r + pas].first, v[i].second))
                        r += pas;
                    pas /= 2;
                }
                rez += aint.query(1, 1, n, 1, r);
                aint.update(1, 1, n, f[v[i].second], col[v[i].second] + 1);
                banned.add(1, 1, n, f[v[i].second], -1);
                rez %= MOD;
            }
            if(col[v[i].second] > 0 || i == n) /// avem frecventa mai mare ca 1..0
                rez += banned.aint[1];
            rez %= MOD;
            banned.update(1, 1, n, f[v[i].second], 1);
        }
    }
    cout << rez;
    return 0;
}

Compilation message

fish.cpp: In function 'int afla(int, int)':
fish.cpp:92:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |         if(r + pas < g[col].size() && g[col][r + pas] * 2 <= x)
      |            ~~~~~~~~^~~~~~~~~~~~~~~
fish.cpp: In function 'int main()':
fish.cpp:132:9: warning: unused variable 'dr' [-Wunused-variable]
  132 |     int dr = n, st = n;
      |         ^~

Subtask #1
4.0 / 4.0

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

Subtask #2
4.0 / 4.0

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

Subtask #3
4.0 / 4.0

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

Subtask #4
4.0 / 4.0

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

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 27784 KB Output is correct
2 Correct 13 ms 27732 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 27732 KB Output is correct
2 Correct 340 ms 36120 KB Output is correct

Subtask #7
6.0 / 6.0

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

Subtask #8
6.0 / 6.0

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

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 31472 KB Output is correct
2 Correct 202 ms 32148 KB Output is correct

Subtask #10
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 27860 KB Output is correct
2 Incorrect 19 ms 27804 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #11
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 33352 KB Output is correct
2 Incorrect 363 ms 36016 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 267 ms 37376 KB Output is correct
2 Correct 408 ms 36812 KB Output is correct

Subtask #13
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 34704 KB Output is correct
2 Incorrect 424 ms 36668 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #14
5.0 / 5.0

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

Subtask #15
5.0 / 5.0

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

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 454 ms 36156 KB Output is correct
2 Correct 688 ms 42100 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 832 ms 42112 KB Output is correct
2 Correct 598 ms 39760 KB Output is correct

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 619 ms 43196 KB Output is correct
2 Correct 723 ms 41884 KB Output is correct
3 Incorrect 730 ms 45960 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 985 ms 45092 KB Output is correct
2 Correct 1257 ms 59132 KB Output is correct
3 Correct 1282 ms 59072 KB Output is correct
4 Correct 1161 ms 54360 KB Output is correct