oj.uz

Submission #987647

# Submission time Handle Problem Language Result Execution time Memory
987647 2024-05-23T09:01:46 Z jklepec Fish (IOI08_fish) C++11
100 / 100
 694 ms 50204 KB 
#include <bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for(int i = a; i < b; ++i)
#define REP(i, n) FOR(i, 0, n)
#define _ << " " <<
#define sz(x) ((int) x.size())
#define pb(x) push_back(x)

typedef long long ll;
typedef pair<int, int> point;

const int MAXN = 5e5 + 5, off = 1 << 19;

int mod;

int add(int x, int y) {
  x += y;
  if(x >= mod) return x - mod;
  return x;
}
int mul(int x, int y) {
  return (ll) x * y % mod;
}

int T[2 * off];
int get(int x, int lo, int hi, int a, int b) {
  if(lo >= a && hi <= b) return T[x];
  if(lo >= b || hi <= a) return 1;

  int mid = (lo + hi) >> 1;
  return mul(get(x * 2, lo, mid, a, b), get(x * 2 + 1, mid, hi, a, b));
}
void upd(int x, int v) {
  v %= mod;
  x += off;
  T[x] = v;
  for(x /= 2; x; x /= 2) {
    T[x] = mul(T[x * 2], T[x * 2 + 1]);
  }
}

int c[MAXN], rev[MAXN];
bool bio[MAXN];

vector<point> a;

vector<int> w[MAXN];

int when[MAXN];

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

  int n, k; cin >> n >> k >> mod;
  a.resize(n);

  REP(i, n) {
    cin >> a[i].first >> a[i].second;
    a[i].second --;
  }

  REP(i, 2 * off) {
    T[i] = 1;
  }

  sort(a.rbegin(), a.rend());

  REP(i, n) {
    w[a[i].second].pb(a[i].first);
  }

  int cnt = 0;
  REP(i, n) {
    if(!bio[a[i].second]) {
      bio[a[i].second] = true;
      when[cnt] = i;
      rev[a[i].second] = cnt ++;
    }
  }
  memset(bio, 0, sizeof bio);

  int sol = 0, pt = 0;
  REP(i, n) {
    c[a[i].second] ++;
  }

  REP(i, k) {
    reverse(w[i].begin(), w[i].end());
    c[i] ++;
    upd(rev[i], c[i]);
  }

  int cookie = 0;

  REP(i, n) {
    int boja = a[i].second;

    if(bio[boja]) {
      continue;
    }
    bio[boja] = true;

    while(pt < n && a[pt].first * 2 > a[i].first) {
      upd(rev[a[pt].second], --c[a[pt].second]);
      pt ++;
    }

    int last = c[boja];

    upd(rev[boja], last - 1);
    sol = add(sol, get(1, 0, off, rev[boja], off));

    upd(rev[boja], 1);

    int lo = 0, hi = cookie ++;

    while(lo < hi) {
      int mid = (lo + hi) >> 1;

      int j = when[mid];
      int imaih = upper_bound(w[boja].begin(), w[boja].end(), a[j].first / 2) - w[boja].begin();

      if(imaih < last) {
        hi = mid;
      }
      else {
        lo = mid + 1;
      }
    }

    sol = add(sol, get(1, 0, off, lo, off));
    upd(rev[boja], last);
  }
  cout << sol;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 22364 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 22364 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 22616 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 22364 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 22364 KB Output is correct
2 Correct 5 ms 22364 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 22364 KB Output is correct
2 Correct 146 ms 35244 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 22360 KB Output is correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 22364 KB Output is correct

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 27732 KB Output is correct
2 Correct 77 ms 29324 KB Output is correct

Subtask #10
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 22364 KB Output is correct
2 Correct 9 ms 22672 KB Output is correct
3 Correct 10 ms 22616 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 30916 KB Output is correct
2 Correct 181 ms 35340 KB Output is correct
3 Correct 150 ms 35588 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 35036 KB Output is correct
2 Correct 150 ms 36548 KB Output is correct

Subtask #13
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 30932 KB Output is correct
2 Correct 159 ms 35980 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 35104 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 37276 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 34080 KB Output is correct
2 Correct 369 ms 39228 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 389 ms 38488 KB Output is correct
2 Correct 305 ms 34384 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 312 ms 37348 KB Output is correct
2 Correct 361 ms 39088 KB Output is correct
3 Correct 377 ms 40588 KB Output is correct
4 Correct 348 ms 38992 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 516 ms 40980 KB Output is correct
2 Correct 599 ms 49300 KB Output is correct
3 Correct 694 ms 50204 KB Output is correct
4 Correct 680 ms 47132 KB Output is correct