Submission #116629

#	Time	Username	Problem	Language	Result	Execution time	Memory
116629		roseanne_pcy	Gap (APIO16_gap)	C++14	Compilation error	0 ms	0 KiB

gap

//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;
}

Compilation message (stderr)

/tmp/ccNGmT9U.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/cci2S0P5.o:gap.cpp:(.text.startup+0x0): first defined here
/tmp/ccNGmT9U.o: In function `main':
grader.cpp:(.text.startup+0x18e): undefined reference to `findGap(int, int)'
collect2: error: ld returned 1 exit status