Submission #987647

#	Time	Username	Problem	Language	Result	Execution time	Memory
987647		jklepec	Fish (IOI08_fish)	C++11	100 / 100	694 ms	50204 KiB

fish

#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 / 4
• Subtask 2: 4 / 4
• Subtask 3: 4 / 4
• Subtask 4: 4 / 4
• Subtask 5: 4 / 4
• Subtask 6: 5 / 5
• Subtask 7: 6 / 6
• Subtask 8: 6 / 6
• Subtask 9: 6 / 6
• Subtask 10: 6 / 6
• Subtask 11: 7 / 7
• Subtask 12: 7 / 7
• Subtask 13: 7 / 7
• Subtask 14: 5 / 5
• Subtask 15: 5 / 5
• Subtask 16: 5 / 5
• Subtask 17: 5 / 5
• Subtask 18: 5 / 5
• Subtask 19: 5 / 5