Submission #112540

#	Time	Username	Problem	Language	Result	Execution time	Memory
112540		MAMBA	Fish (IOI08_fish)	C++17	0 / 100	1930 ms	13496 KiB

fish

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

#define rep(i, j, k) for (int i = j; i < k; i++)
#define pb push_back
#define all(x) x.begin(), x.end()
#define mt make_tuple

#define iv inline void
#define ii inline int
#define ill inline ll

template <typename S, typename T>
inline bool smin(S& l, T r) {
  return r < l ? l = r, 1 : 0;
}
template <typename S, typename T>
inline bool smax(S& l, T r) {
  return l < r ? l = r, 1 : 0;
}

int MOD = 1e9 + 7;  // 998244353;

template <typename S>
inline S mod(S& l) {
  return l = (l % MOD + MOD) % MOD;
}
template <typename S, typename T>
inline S add(S& l, T r) {
  return mod(l += r);
}
ill po(ll v, ll u) {
  return u ? po(v * v % MOD, u >> 1) * (u & 1 ? v : 1) % MOD : 1;
}
ll gcd(ll v, ll u) { return v ? gcd(u % v, v) : u; }

void fileIO(string s) {
  freopen((s + ".in").c_str(), "r", stdin);
  freopen((s + ".out").c_str(), "w", stdout);
}

inline ostream& operator<<(ostream& o, pll p) {
  return o << '(' << p.first << ' ' << p.second << ')';
}

constexpr int N = 5e5 + 10;

int F, k;
pii p[N];
bitset<N> mark, have;

int arr[N], ptr;

ll answer;

pll seg[N << 2];

inline pll merge(pll l, pll r) {
  return pll(l.first * r.first % MOD, (l.first * r.second + l.second) % MOD);
}

void segInit(int l = 0, int r = k, int id = 1) {
  if (l == r - 1) {
    seg[id] = {1, 1};
    return;
  }
  int mid = l + r >> 1;
  segInit(l, mid, id << 1);
  segInit(mid, r, id << 1 | 1);
  seg[id] = merge(seg[id << 1], seg[id << 1 | 1]);
}

void segAdd(int pos, int l = 0, int r = k, int id = 1) {
  if (l == r - 1) {
    seg[id].first++;
    seg[id].second++;
    return;
  }
  int mid = l + r >> 1;
  if (pos < mid)
    segAdd(pos, l, mid, id << 1);
  else
    segAdd(pos, mid, r, id << 1 | 1);
  seg[id] = merge(seg[id << 1], seg[id << 1 | 1]);
}

pll segGet(int s, int t, int l = 0, int r = k, int id = 1) {
  if (l >= s && r <= t) return seg[id];
  if (l >= t || r <= s) return {1, 0};
  int mid = l + r >> 1;
  // cout << s << ' ' << t << ' ' << l << ' ' << r << ':'
  //     << segGet(s, t, l, mid, id << 1) << segGet(s, t, mid, r, id << 1 | 1)
  //     << endl;
  return merge(segGet(s, t, l, mid, id << 1),
               segGet(s, t, mid, r, id << 1 | 1));
}

int main() {
#ifndef LOCAL
  // fileIO("");
#endif

  cin >> F >> k >> MOD;
  rep(i, 0, F) cin >> p[i].first >> p[i].second;

  sort(p, p + F);

  for (int i = F - 1; ~i; i--)
    if (!have[p[i].second]) {
      arr[p[i].second] = ptr++;
      mark[i] = true;
      have[p[i].second] = true;
    }

  segInit();

  int R = 0;
  rep(i, 0, F) {
    while (R < F && p[i].first * 2 > p[R].first) {
      if (mark[R]) ptr--;
      R++;
    }

    int id = arr[p[i].second];
    ll A = id < ptr ? merge(segGet(0, id), segGet(id + 1, ptr)).second
                    : segGet(0, ptr).second;

    ll B = id >= ptr ? merge(segGet(ptr, id), segGet(id + 1, k)).first
                     : segGet(ptr, k).first;

    add(answer, A * B);

    segAdd(arr[p[i].second]);
  }
  add(answer, k);
  cout << answer << endl;

  return 0;
}

Compilation message (stderr)

fish.cpp: In function 'void segInit(int, int, int)':
fish.cpp:75:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = l + r >> 1;
             ~~^~~
fish.cpp: In function 'void segAdd(int, int, int, int)':
fish.cpp:87:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = l + r >> 1;
             ~~^~~
fish.cpp: In function 'pll segGet(int, int, int, int, int)':
fish.cpp:98:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = l + r >> 1;
             ~~^~~
fish.cpp: In function 'void fileIO(std::__cxx11::string)':
fish.cpp:46:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen((s + ".in").c_str(), "r", stdin);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:47:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen((s + ".out").c_str(), "w", stdout);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 4
• Subtask 2: 0 / 4
• Subtask 3: 0 / 4
• Subtask 4: 0 / 4
• Subtask 5: 0 / 4
• Subtask 6: 0 / 5
• Subtask 7: 0 / 6
• Subtask 8: 0 / 6
• Subtask 9: 0 / 6
• Subtask 10: 0 / 6
• Subtask 11: 0 / 7
• Subtask 12: 0 / 7
• Subtask 13: 0 / 7
• Subtask 14: 0 / 5
• Subtask 15: 0 / 5
• Subtask 16: 0 / 5
• Subtask 17: 0 / 5
• Subtask 18: 0 / 5
• Subtask 19: 0 / 5