oj.uz

Submission #112543

# Submission time Handle Problem Language Result Execution time Memory
112543 2019-05-20T13:15:49 Z MAMBA Fish (IOI08_fish) C++17
4 / 100
 1637 ms 13364 KB 
#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

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);
}
ll 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; }

inline 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 r, pll l) {
  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;
  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];
    if (id < ptr)
      add(answer, segGet(0, id + 1).second * segGet(id + 1, k).first);
    else
      add(answer, segGet(0, ptr).second * segGet(ptr, id).first *
                      segGet(id + 1, k).first);

    segAdd(id);
  }
  add(answer, k);
  cout << answer << endl;

  return 0;
}

Compilation message

fish.cpp: In function 'void segInit(int, int, int)':
fish.cpp:71:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = l + r >> 1;
             ~~^~~
fish.cpp: In function 'void segAdd(int, int, int, int)':
fish.cpp:83: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:94:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = l + r >> 1;
             ~~^~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Output isn't correct

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Output isn't correct

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Output isn't correct

Subtask #5
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Incorrect 3 ms 384 KB Output isn't correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 384 KB Output isn't correct

Subtask #8
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 384 KB Output isn't correct

Subtask #9
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 263 ms 1944 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Output is correct
2 Correct 11 ms 384 KB Output is correct
3 Incorrect 9 ms 512 KB Output isn't correct

Subtask #11
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 474 ms 2808 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 746 ms 4440 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 551 ms 2948 KB Output is correct
2 Incorrect 914 ms 4728 KB Output isn't correct

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 880 ms 4544 KB Output isn't correct

Subtask #15
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1072 ms 5380 KB Output isn't correct

Subtask #16
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 844 ms 5808 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #17
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1393 ms 12796 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1100 ms 12852 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1637 ms 13364 KB Output isn't correct
2 Halted 0 ms 0 KB -