oj.uz

Submission #448619

# Submission time Handle Problem Language Result Execution time Memory
448619 2021-07-31T07:43:00 Z prvocislo Fish (IOI08_fish) C++17
100 / 100
 491 ms 47912 KB 
#include <iostream>
#include <vector>
#include <algorithm>
typedef long long ll;
using namespace std;

int f, k, m;
void add(int& a, const int& b) { a += b; if (a >= m) a -= m; }
int mul(const int& a, const int& b) { return (a * b) % m; }
const int maxn = 1 << 19, inf = 1e9 + 5;
//const int maxn = 4, inf = 1e9 + 5;
vector<int> st(maxn * 2, 1);
void upd(int i)
{
    add(st[i += maxn], 1);
    for (i = (i >> 1); i > 0; i >>= 1) st[i] = mul(st[i << 1], st[i << 1 | 1]);
}
int query(int l, int r)
{
    int ans = 1;
    for (l += maxn, r += maxn+1; l < r; l >>= 1, r >>= 1)
    {
        if (l & 1) ans = mul(ans, st[l++]);
        if (r & 1) ans = mul(ans, st[--r]);
    }
    return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> f >> k >> m;
    vector<pair<int, int> > fish(f);
    vector<int> longest(k, -1), order(k, -1);
    vector<bool> is_long(f, false);
    vector<vector<int> > typ(k, vector<int>(1, inf));
    for (int i = 0; i < f; i++) cin >> fish[i].first >> fish[i].second, fish[i].second--;
    int num = k;
    sort(fish.begin(), fish.end());
    for (int i = f - 1; i >= 0; i--)
    {
        if (order[fish[i].second] == -1)
        {
            is_long[i] = true;
            order[fish[i].second] = --num;
            longest[num] = fish[i].first;
        }
        fish[i].second = order[fish[i].second];
        typ[fish[i].second].push_back(fish[i].first);
    }
    int j = -1, ans = 0;
    for (int i = 0; i < f; i++) if (is_long[i])
    {
        while (fish[j + 1].first * 2 <= fish[i].first)
            upd(fish[++j].second), typ[fish[j].second].pop_back();
        //cout << query(0, fish[i].second) << "\n";
        add(ans, mul(query(0, fish[i].second-1), (m + st[maxn+fish[i].second] - 1) % m));
        int r = lower_bound(longest.begin(), longest.end(), typ[fish[i].second].back() * 2) - longest.begin() - 1;
        //cout << query(0, fish[i].second - 1) << "*" << query(fish[i].second + 1, r) << "\n";
        add(ans,  mul(query(0, fish[i].second - 1), query(fish[i].second + 1, r)));
    }
    cout << ans << "\n";
    return 0;
}

Subtask #1
4.0 / 4.0

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

Subtask #2
4.0 / 4.0

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

Subtask #3
4.0 / 4.0

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

Subtask #4
4.0 / 4.0

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

Subtask #5
4.0 / 4.0

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

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4428 KB Output is correct
2 Correct 206 ms 10972 KB Output is correct

Subtask #7
6.0 / 6.0

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

Subtask #8
6.0 / 6.0

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

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 7468 KB Output is correct
2 Correct 119 ms 11188 KB Output is correct

Subtask #10
6.0 / 6.0

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

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 8780 KB Output is correct
2 Correct 254 ms 10904 KB Output is correct
3 Correct 223 ms 11316 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 229 ms 11244 KB Output is correct
2 Correct 227 ms 18532 KB Output is correct

Subtask #13
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 8852 KB Output is correct
2 Correct 231 ms 11384 KB Output is correct

Subtask #14
5.0 / 5.0

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

Subtask #15
5.0 / 5.0

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

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 13044 KB Output is correct
2 Correct 259 ms 16964 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 362 ms 19052 KB Output is correct
2 Correct 250 ms 21552 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 290 ms 19316 KB Output is correct
2 Correct 330 ms 24876 KB Output is correct
3 Correct 319 ms 29744 KB Output is correct
4 Correct 380 ms 24760 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 444 ms 22412 KB Output is correct
2 Correct 440 ms 46916 KB Output is correct
3 Correct 380 ms 47912 KB Output is correct
4 Correct 491 ms 41740 KB Output is correct