oj.uz

Submission #112540

# Submission time Handle Problem Language Result Execution time Memory
112540 2019-05-20T13:06:10 Z MAMBA Fish (IOI08_fish) C++17
0 / 100
 1930 ms 13496 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

#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Output isn't 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 380 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 7 ms 384 KB Output isn't correct

Subtask #9
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 298 ms 1980 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 Incorrect 16 ms 512 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #11
0 / 7.0

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

Subtask #12
0 / 7.0

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

Subtask #13
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 589 ms 2988 KB Output is correct
2 Incorrect 943 ms 11612 KB Output isn't correct

Subtask #14
0 / 5.0

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

Subtask #15
0 / 5.0

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

Subtask #16
0 / 5.0

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

Subtask #17
0 / 5.0

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

Subtask #18
0 / 5.0

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

Subtask #19
0 / 5.0

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