Submission #102790

#	Time	Username	Problem	Language	Result	Execution time	Memory
102790		CorneliuVadimTudor	Boat (APIO16_boat)	C++14	58 / 100	2015 ms	4224 KiB

boat

#include <bits/stdc++.h>
#define MAXN 1000
#define MAXG 2000

struct Event{
    int time, node, tip;
    bool operator < (const Event &aux) const{
        return time < aux.time;
    }
};
std::vector <Event> V;
std::set <int> S;

const int MOD = 1000000007;
int d[1 + MAXG][1 + MAXN];
int C[1 + MAXN], D[1 + MAXN];

inline int logPow(int a, int n){
    int p = 1;
    while(n){
        if(n % 2) p = 1LL * p * a % MOD;
        a = 1LL * a * a % MOD;
        n /= 2;
    }
    return p;
}

int main(){
    FILE*fi,*fo;
    //fi = fopen("a.in","r");
    //fo = fopen("a.out","w");
    fi = stdin;
    fo = stdout;

    int n;
    fscanf(fi,"%d", &n);
    for(int i = 1; i <= n; i++){
        int a, b;
        fscanf(fi,"%d%d", &a, &b);
        V.push_back({a, i, 1});
        V.push_back({b + 1, i, -1});
    }
    std::sort(V.begin(), V.end());

    int j = 0, group = 0;
    d[group][0] = 1;
    for(int i = 0; i < V.size(); i = j){
        j = i;
        while(j < V.size() && V[j].time == V[i].time){
            if(V[j].tip == 1) S.insert(V[j].node);
            else S.erase(V[j].node);
            j++;
        }
        if(!S.size()) continue;

        int len = V[j].time - V[i].time;
        C[0] = 1;
        for(int p = 1; p <= std::min((int)S.size(), len); p++){
            C[p] = 1LL * C[p - 1] * (len - p + 1) % MOD;
            C[p] = 1LL * C[p] * logPow(p, MOD - 2) % MOD;
        }

        for(int x = 0; x <= S.size(); x++){
            int Cxp = 1;
            D[x] = 0;
            for(int p = 1; p <= std::min(x, len); p++){
                Cxp = 1LL * Cxp * (x - p + 1) % MOD;
                Cxp = 1LL * Cxp * logPow(p, MOD - 2) % MOD;
                D[x] = (D[x] + 1LL * C[p] * Cxp % MOD) % MOD;
            }
        }

        group++;
        for(int prev = 0; prev <= n; prev++){
            auto next = S.begin();
            while(next != S.end() && *next <= prev) next++;

            int x = 0;
            while(next != S.end()){
                x++;
                d[group][*next] = (d[group][*next] + 1LL * d[group - 1][prev] * D[x]) % MOD;
                next++;
            }
        }

        auto next = S.begin();
        int prev = d[group][*next];
        next++;
        while(next != S.end()){
            int aux = d[group][*next];
            d[group][*next] = (d[group][*next] - prev + MOD) % MOD;
            prev = aux;
            next++;
        }

        for(int prev = 0; prev <= n; prev++)
            d[group][prev] = (d[group][prev] + d[group - 1][prev]) % MOD;
    }

    int ans = 0;
    for(int prev = 1; prev <= n; prev++)
        ans = (ans + d[group][prev]) % MOD;

    fprintf(fo,"%lld", ans);

    return 0;
}

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:47:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < V.size(); i = j){
                    ~~^~~~~~~~~~
boat.cpp:49:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(j < V.size() && V[j].time == V[i].time){
               ~~^~~~~~~~~~
boat.cpp:63:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int x = 0; x <= S.size(); x++){
                        ~~^~~~~~~~~~~
boat.cpp:104:27: warning: format '%lld' expects argument of type 'long long int', but argument 3 has type 'int' [-Wformat=]
     fprintf(fo,"%lld", ans);
                           ^
boat.cpp:36:11: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf(fi,"%d", &n);
     ~~~~~~^~~~~~~~~~~~~
boat.cpp:39:15: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf(fi,"%d%d", &a, &b);
         ~~~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 22 / 22
• Subtask 3: 27 / 27
• Subtask 4: 0 / 42