oj.uz

Submission #558854

# Submission time Handle Problem Language Result Execution time Memory
558854 2022-05-08T19:29:17 Z Sweezy Boat (APIO16_boat) C++17
9 / 100
 1050 ms 13552 KB 
#include <bits/stdc++.h>
 
using namespace std;
#define int long long
 
template <typename A, typename B>
string to_string(pair<A, B> p);
 
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);
 
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);
 
string to_string(const string& s) {
  return '"' + s + '"';
}
 
string to_string(const char* s) {
  return to_string((string) s);
}
 
string to_string(bool b) {
  return (b ? "true" : "false");
}
 
string to_string(vector<bool> v) {
  bool first = true;
  string res = "{";
  for (int i = 0; i < static_cast<int>(v.size()); i++) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}
 
template <size_t N>
string to_string(bitset<N> v) {
  string res = "";
  for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
  }
  return res;
}
 
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
 
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
 
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}
 
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}
  
void debug_out() { cerr << endl; }
 
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
 
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif
 
#define all(a) (a).begin(), (a).end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define reps(i, s, n) for (int i = s; i < (n); ++i)
#define pb push_back
#define sz(a) (int) (a.size())
 
const int mod = 1e9 + 7;

void solve() {
  int n;
  cin >> n;
  vector<int> a(n), b(n), cs;
  rep(i, n) {
    cin >> a[i] >> b[i];
    cs.pb(a[i]);
    cs.pb(b[i]);
  }
 
  sort(all(cs));
  cs.erase(unique(all(cs)), cs.end());
  map<int, int> mp;
  vector<int> l, r;
  rep(i, sz(cs)) {
    if ((i == 0 ? 0 : cs[i - 1]) + 1 <= cs[i] - 1) {
      l.pb((i == 0 ? 0 : cs[i - 1]) + 1);
      r.pb(cs[i] - 1);
    }
    mp[cs[i]] = sz(l);
    l.pb(cs[i]);
    r.pb(cs[i]);
  }
  rep(i, n) {
    a[i] = mp[a[i]];
    b[i] = mp[b[i]];
    debug(a[i], b[i]);
  }

  auto add = [&] (int &a, int b) -> void {
    (a += b) %= mod;
  };
 
  auto mul = [&] (int a, int b) -> int {
    return a * b % mod;
  };
 
  auto binpow = [&] (int a, int n) -> int {
    int res = 1;
    while (n) {
      if (n % 2) {
        res = mul(res, a);
      }
      a = mul(a, a);
      n /= 2;
    }
    return res;
  };
 
  auto inv = [&] (int val) {
    return binpow(val, mod - 2);
  };
 
  vector<int> f(n + 1), rf(n + 1);
  f[0] = rf[0] = 1;
  reps(i, 1, n + 1) {
    f[i] = mul(f[i - 1], i);
    rf[i] = inv(f[i]);
  }
 
  auto choose = [&] (int n, int k) {
    int res = 1;
    reps(i, 1, k + 1) {
      res = mul(res, n - k + i);
    }
    return mul(res, rf[k]);
  };

  // [i]: 1
  // 0 0 0 0 0 1 7 1 3 1 0 0 
  // [i]: 2
  // 0 0 0 1 53 1 35 9 33 13 42 14 
  // [i]: 3
  // 0 1 24 1 1484 55 497 99 0 0 0 0 

  // [i, x, j, cnt]: 3 6 3 1
  // [dp[i][x]]: 399
  // [i, x, j, cnt]: 3 6 2 2
  // [dp[i][x]]: 441
  // [i, x, j, cnt]: 3 6 1 3
  // [dp[i][x]]: 497

  int segs = sz(l);
  vector<vector<int>> C(segs, vector<int> (n + 1));
  rep(seg, segs) {
    rep(i, n + 1) {
      C[seg][i] = choose(r[seg] - l[seg] + 1, i);
    }
    reps(i, 2, n + 1) {
      add(C[seg][i], C[seg][i - 1]);
    }
  }
 
  int answer = 0;
  vector<vector<int>> dp(n, vector<int> (segs));
  rep(i, n) {
    reps(seg, a[i], b[i] + 1) {
      int len = r[seg] - l[seg] + 1;
      int cnt = 0;
      for (int j = i; j >= 0; j--) {
        if (a[j] <= seg && seg <= b[j]) {
          cnt++;
          if (cnt > len) break;
          debug(i, seg, j, cnt);
          if (j == 0 || seg == 0) {
            add(dp[i][seg], C[seg][cnt]);
          } else {
            add(dp[i][seg], mul(dp[j - 1][seg - 1], C[seg][cnt]));
          }
          debug(dp[i][seg]);
        }
      }
    }
    debug(i, dp[i]);
    reps(j, 1, segs) {
      add(dp[i][j], dp[i][j - 1]);
    }
    add(answer, dp[i][b[i]]);
    rep(j, segs) {
      add(dp[i][j], (i ? dp[i - 1][j] : 1));
    }
  }

  cout << answer;

  // vector<vector<int>> C(sz(segs), vector<int> (n + 1)), Cs(n + 1, vector<int> (n + 1));
  // rep(i, sz(segs)) {
  //   rep(j, min(segs[i].second - segs[i].first + 1, n) + 1) {
  //     C[i][j] = choose(segs[i].second - segs[i].first + 1, j);
  //   }
  // }
  // rep(i, n + 1) {
  //   rep(j, i + 1) {
  //     Cs[i][j] = choose(i, j);
  //   }
  // }
}
 
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  solve();
  return 0;
}

Compilation message

boat.cpp: In function 'void solve()':
boat.cpp:91:20: warning: statement has no effect [-Wunused-value]
   91 | #define debug(...) 42
      |                    ^~
boat.cpp:128:5: note: in expansion of macro 'debug'
  128 |     debug(a[i], b[i]);
      |     ^~~~~
boat.cpp:91:20: warning: statement has no effect [-Wunused-value]
   91 | #define debug(...) 42
      |                    ^~
boat.cpp:205:11: note: in expansion of macro 'debug'
  205 |           debug(i, seg, j, cnt);
      |           ^~~~~
boat.cpp:91:20: warning: statement has no effect [-Wunused-value]
   91 | #define debug(...) 42
      |                    ^~
boat.cpp:211:11: note: in expansion of macro 'debug'
  211 |           debug(dp[i][seg]);
      |           ^~~~~
boat.cpp:91:20: warning: statement has no effect [-Wunused-value]
   91 | #define debug(...) 42
      |                    ^~
boat.cpp:215:5: note: in expansion of macro 'debug'
  215 |     debug(i, dp[i]);
      |     ^~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 609 ms 8180 KB Output is correct
2 Correct 625 ms 8184 KB Output is correct
3 Correct 618 ms 8180 KB Output is correct
4 Correct 615 ms 8184 KB Output is correct
5 Correct 598 ms 8268 KB Output is correct
6 Correct 616 ms 8284 KB Output is correct
7 Correct 627 ms 8180 KB Output is correct
8 Correct 629 ms 8372 KB Output is correct
9 Correct 598 ms 8184 KB Output is correct
10 Correct 618 ms 8184 KB Output is correct
11 Correct 614 ms 8180 KB Output is correct
12 Correct 604 ms 8184 KB Output is correct
13 Correct 626 ms 8180 KB Output is correct
14 Correct 619 ms 8184 KB Output is correct
15 Correct 622 ms 8288 KB Output is correct
16 Correct 109 ms 1740 KB Output is correct
17 Correct 118 ms 1756 KB Output is correct
18 Correct 116 ms 1712 KB Output is correct
19 Correct 123 ms 1980 KB Output is correct
20 Correct 110 ms 1728 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 609 ms 8180 KB Output is correct
2 Correct 625 ms 8184 KB Output is correct
3 Correct 618 ms 8180 KB Output is correct
4 Correct 615 ms 8184 KB Output is correct
5 Correct 598 ms 8268 KB Output is correct
6 Correct 616 ms 8284 KB Output is correct
7 Correct 627 ms 8180 KB Output is correct
8 Correct 629 ms 8372 KB Output is correct
9 Correct 598 ms 8184 KB Output is correct
10 Correct 618 ms 8184 KB Output is correct
11 Correct 614 ms 8180 KB Output is correct
12 Correct 604 ms 8184 KB Output is correct
13 Correct 626 ms 8180 KB Output is correct
14 Correct 619 ms 8184 KB Output is correct
15 Correct 622 ms 8288 KB Output is correct
16 Correct 109 ms 1740 KB Output is correct
17 Correct 118 ms 1756 KB Output is correct
18 Correct 116 ms 1712 KB Output is correct
19 Correct 123 ms 1980 KB Output is correct
20 Correct 110 ms 1728 KB Output is correct
21 Incorrect 1050 ms 13552 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 609 ms 8180 KB Output is correct
2 Correct 625 ms 8184 KB Output is correct
3 Correct 618 ms 8180 KB Output is correct
4 Correct 615 ms 8184 KB Output is correct
5 Correct 598 ms 8268 KB Output is correct
6 Correct 616 ms 8284 KB Output is correct
7 Correct 627 ms 8180 KB Output is correct
8 Correct 629 ms 8372 KB Output is correct
9 Correct 598 ms 8184 KB Output is correct
10 Correct 618 ms 8184 KB Output is correct
11 Correct 614 ms 8180 KB Output is correct
12 Correct 604 ms 8184 KB Output is correct
13 Correct 626 ms 8180 KB Output is correct
14 Correct 619 ms 8184 KB Output is correct
15 Correct 622 ms 8288 KB Output is correct
16 Correct 109 ms 1740 KB Output is correct
17 Correct 118 ms 1756 KB Output is correct
18 Correct 116 ms 1712 KB Output is correct
19 Correct 123 ms 1980 KB Output is correct
20 Correct 110 ms 1728 KB Output is correct
21 Incorrect 1050 ms 13552 KB Output isn't correct
22 Halted 0 ms 0 KB -