oj.uz

Submission #480657

# Submission time Handle Problem Language Result Execution time Memory
480657 2021-10-17T14:45:44 Z TAMREF Boat (APIO16_boat) C++17
0 / 100
 230 ms 524292 KB 
#include <bits/stdc++.h>
#define va first
#define vb second
#define lb lower_bound
#define ub upper_bound
#define bs binary_search
#define pp push_back
#define ep emplace_back
#define all(v) (v).begin(),(v).end()
#define szz(v) ((int)(v).size())
#define bi_pc __builtin_popcount
#define bi_pcll __builtin_popcountll
#define bi_tz __builtin_ctz
#define bi_tzll __builtin_ctzll
#define fio ios_base::sync_with_stdio(0);cin.tie(0);
#ifdef TAMREF
#define debug(...) fprintf(stderr, __VA_ARGS__)
#else
#define debug(...) 42
#endif
using namespace std;
using ll = long long; using lf = long double; 
using pii = pair<int,int>; using ppi = pair<int,pii>;
using pll = pair<ll,ll>; using pff = pair<lf,lf>;
using ti = tuple<int,int,int>;
using base = complex<double>;
const lf PI = 3.14159265358979323846264338L;
template <typename T>
inline T umax(T& u, T v){return u = max(u, v);}
template <typename T>
inline T umin(T& u, T v){return u = min(u, v);}
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

struct mint {
    static const int mod = 1e9 + 7;
    int v;
    mint(ll v = 0) : v(v % mod) {}
    mint operator+ (mint o) {
        return mint(v + o.v);
    }
    mint operator- (mint o) {
        return mint(v + mod - o.v);
    }
    mint operator* (mint o) {
        return mint(ll(v) * o.v);
    }
    mint operator^ (int n) {
        mint ret(1), pv(v);
        for(;n;n>>=1) {
            if(n & 1) ret = ret * pv;
            pv = pv * pv;
        }
        return ret;
    }
    mint inv() {
        return mint(v) ^ (mod - 2);
    }
    mint operator/ (mint o) {
        return mint(v) * o.inv();
    }
};

mint& operator+= (mint &a, mint b) {
    return a = a + b;
}

mint& operator-= (mint &a, mint b) {
    return a = a - b;
}

int n;
vector<int> cmp;
int a[505], b[505];

mint a_Ijk[505][1005][505]; // i' < i, j' = j, k' = k
mint b_ij[505][1005]; //i' < i, j' < j, k' arb
mint dp[505][1005][505];
mint ans;

int main(){
    fio;
    cin >> n;
    debug("2 * 3 = %d\n", (mint(2) * mint(3)).v);
    for(int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i];
        ++b[i];
        cmp.pp(a[i]); cmp.pp(b[i]);
    }
    sort(all(cmp)); cmp.erase(unique(all(cmp)), cmp.end());
    int d = szz(cmp);
    for(int i = 1; i <= n; i++) {
        a[i] = lb(all(cmp), a[i]) - cmp.begin() + 1;
        b[i] = lb(all(cmp), b[i]) - cmp.begin() + 1;
    }

    for(int i = 1; i <= n; i++) {
        debug("a[%d] = %d, b[%d] = %d\n", i, a[i], i, b[i]);
        for(int j = 1; j < d; j++) {
            b_ij[i][j] += b_ij[i-1][j] + b_ij[i][j-1] - b_ij[i-1][j-1];
            for(int k = 1; k <= n; k++) {
                a_Ijk[i][j][k] += a_Ijk[i-1][j][k];
                if(a[i] <= j && j < b[i]) {
                    mint len = cmp[j] - cmp[j-1];
                    debug("len[%d] = %d\n", j, cmp[j] - cmp[j-1]);
                    if(k == 1) {
                        dp[i][j][k] = (mint(1) + b_ij[i-1][j-1]) * len;
                    }else{
                        debug("reffing %d\n", a_Ijk[i-1][j][k-1].v);
                        debug("modinv(%d) = %d\n", k, mint(k).inv().v);
                        dp[i][j][k] = a_Ijk[i-1][j][k-1] * (len - mint(k - 1)) / mint(k);
                    }
                }
                debug("dp[%d] [%d, %d) [%d] = %d\n", i, j ? cmp[j-1] : 0, j < d ? cmp[j] : -1, k, dp[i][j][k].v);
                a_Ijk[i][j][k] += dp[i][j][k];
                b_ij[i][j] += dp[i][j][k];
                ans += dp[i][j][k];
            }
        }
    }
    cout << (ans).v << endl;
}

Compilation message

boat.cpp: In function 'int main()':
boat.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
boat.cpp:83:5: note: in expansion of macro 'debug'
   83 |     debug("2 * 3 = %d\n", (mint(2) * mint(3)).v);
      |     ^~~~~
boat.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
boat.cpp:97:9: note: in expansion of macro 'debug'
   97 |         debug("a[%d] = %d, b[%d] = %d\n", i, a[i], i, b[i]);
      |         ^~~~~
boat.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
boat.cpp:104:21: note: in expansion of macro 'debug'
  104 |                     debug("len[%d] = %d\n", j, cmp[j] - cmp[j-1]);
      |                     ^~~~~
boat.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
boat.cpp:108:25: note: in expansion of macro 'debug'
  108 |                         debug("reffing %d\n", a_Ijk[i-1][j][k-1].v);
      |                         ^~~~~
boat.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
boat.cpp:109:25: note: in expansion of macro 'debug'
  109 |                         debug("modinv(%d) = %d\n", k, mint(k).inv().v);
      |                         ^~~~~
boat.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
boat.cpp:113:17: note: in expansion of macro 'debug'
  113 |                 debug("dp[%d] [%d, %d) [%d] = %d\n", i, j ? cmp[j-1] : 0, j < d ? cmp[j] : -1, k, dp[i][j][k].v);
      |                 ^~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 224 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 224 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 230 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Runtime error 224 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -