| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 116629 | roseanne_pcy | Gap (APIO16_gap) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//Power Of Ninja Go
#include <bits/stdc++.h>
//#ifdef atom #else #endif
using namespace std;
typedef long long ll; typedef pair<int, int> ii;
#define X first
#define Y second
#define vi vector<int>
#define vii vector< ii >
#define pb push_back
const int maxn = 505;
const int md = 1e9+7;
int A[maxn], B[maxn];
int vA[maxn], vB[maxn];
int dp[maxn][maxn];
int fact[maxn], lim;
vi foo;
void add(int &a, int b)
{
a += b;
if(a>= md) a -= md;
}
void sub(int &a, int b)
{
a -= b;
if(a< 0) a += md;
}
int mul(int a, int b)
{
return (1LL*a*b)%md;
}
int ft[maxn];
int findsum(int x)
{
int res = 0;
for(; x; x-=x&(-x)) add(res, ft[x]);
return res;
}
int ask(int a, int b)
{
if(a> b) return 0;
int res = findsum(b);
sub(res, findsum(a-1));
return res;
}
void update(int x, int dx)
{
for(; x<= lim; x+=x&(-x)) add(ft[x], dx);
}
int main()
{
//#ifndef atom freopen(".in", "r", stdin); freopen(".out", "w", stdout); #endif
int n; cin >> n;
for(int i = 1; i<= n; i++)
{
cin >> A[i] >> B[i];
vA[i] = A[i]; vB[i] = B[i];
foo.pb(A[i]); foo.pb(B[i]);
}
foo.pb(-1);
sort(foo.begin(), foo.end());
foo.resize(unique(foo.begin(), foo.end())-foo.begin());
for(int i = 1; i<= n; i++)
{
A[i] = lower_bound(foo.begin(), foo.end(), A[i])-foo.begin();
B[i] = lower_bound(foo.begin(), foo.end(), B[i])-foo.begin();
//cout << A[i] << " " << B[i] << endl;
}
lim = foo.size()-1;
for(int i = 2; i< (int) foo.size(); i++)
{
fact[i] = foo[i]-foo[i-1];
}
for(int j = 1; j<= B[n]; j++) dp[n][j] = min(vB[n]-vA[n]+1, vB[n]-foo[j]+1)+1;
for(int j = 1; j<= lim; j++) update(j, mul(dp[n][j], fact[j]));
for(int i = n-1; i>= 1; i--)
{
for(int j = 1; j<= A[i]; j++)
{
dp[i][j] = ask(A[i]+1, B[i]);
add(dp[i][j], dp[i+1][j]);
//printf("dp*[%d][%d] = %d\n", i, j, dp[i][j]);
add(dp[i][j], dp[i+1][B[i]+1]);
}
for(int j = A[i]+1; j<= B[i]; j++)
{
dp[i][j] = ask(j+1, B[i]);
printf("dp[%d][%d] = %d\n", i, j, dp[i][j]);
add(dp[i][j], dp[i+1][j]);
add(dp[i][j], dp[i+1][B[i]+1]);
//printf("dp[%d][%d] = %d\n", i, j, dp[i][j]);
}
for(int j = B[i]+1; j<= lim; j++) add(dp[i][j], dp[i+1][j]);
memset(ft, 0, sizeof ft);
for(int j = 1; j<= lim; j++) update(j, mul(dp[i][j], fact[j]));
}
for(int i = 1; i<= n; i++)
{
for(int j = 1; j<= lim; j++)
{
cout << dp[i][j] << " \n"[j == lim];
}
}
int res = dp[1][1]; sub(res, 1);
cout << res << endl;
}