oj.uz

Submission #102793

# Submission time Handle Problem Language Result Execution time Memory
102793 2019-03-27T14:23:52 Z CorneliuVadimTudor Boat (APIO16_boat) C++14
9 / 100
 121 ms 3972 KB 
#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;
std::vector <int> X;

const int MOD = 1000000007;
int d[1 + MAXG][1 + MAXN];
int C[1 + MAXN], D[1 + MAXN];
int inv[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());

    for(int i = 1; i <= n; i++)
        inv[i] = logPow(i, MOD - 2);

    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;

        X.clear();
        for(auto y: S) X.push_back(y);

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

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

        group++;
        int first = 0;
        for(int prev = 0; prev <= n; prev++){
            while(first < X.size() && X[first] <= prev) first++;
            int ind = first;

            int x = 0;
            while(ind < X.size()){
                x++;
                d[group][X[ind]] = (d[group][X[ind]] + 1LL * d[group - 1][prev] * D[x]) % MOD;
                ind++;
            }
        }

        int ind = 0;
        int prev = d[group][X[ind]];
        ind++;
        while(ind < X.size()){
            int aux = d[group][X[ind]];
            d[group][X[ind]] = (d[group][X[ind]] - prev + MOD) % MOD;
            prev = aux;
            ind++;
        }

        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

boat.cpp: In function 'int main()':
boat.cpp:52:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < V.size(); i = j){
                    ~~^~~~~~~~~~
boat.cpp:54:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(j < V.size() && V[j].time == V[i].time){
               ~~^~~~~~~~~~
boat.cpp:72:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int x = 0; x <= X.size(); x++){
                        ~~^~~~~~~~~~~
boat.cpp:85:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while(first < X.size() && X[first] <= prev) first++;
                   ~~~~~~^~~~~~~~~~
boat.cpp:89:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while(ind < X.size()){
                   ~~~~^~~~~~~~~~
boat.cpp:99:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(ind < X.size()){
               ~~~~^~~~~~~~~~
boat.cpp:114:27: warning: format '%lld' expects argument of type 'long long int', but argument 3 has type 'int' [-Wformat=]
     fprintf(fo,"%lld", ans);
                           ^
boat.cpp:38: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:41: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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2304 KB Output is correct
2 Correct 7 ms 2304 KB Output is correct
3 Correct 7 ms 2304 KB Output is correct
4 Correct 6 ms 2304 KB Output is correct
5 Correct 7 ms 2304 KB Output is correct
6 Correct 6 ms 2304 KB Output is correct
7 Correct 7 ms 2432 KB Output is correct
8 Correct 6 ms 2304 KB Output is correct
9 Correct 7 ms 2276 KB Output is correct
10 Correct 6 ms 2304 KB Output is correct
11 Correct 5 ms 2304 KB Output is correct
12 Correct 8 ms 2304 KB Output is correct
13 Correct 6 ms 2304 KB Output is correct
14 Correct 5 ms 2304 KB Output is correct
15 Correct 6 ms 2304 KB Output is correct
16 Correct 3 ms 640 KB Output is correct
17 Correct 4 ms 768 KB Output is correct
18 Correct 4 ms 768 KB Output is correct
19 Correct 3 ms 768 KB Output is correct
20 Correct 3 ms 768 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2304 KB Output is correct
2 Correct 7 ms 2304 KB Output is correct
3 Correct 7 ms 2304 KB Output is correct
4 Correct 6 ms 2304 KB Output is correct
5 Correct 7 ms 2304 KB Output is correct
6 Correct 6 ms 2304 KB Output is correct
7 Correct 7 ms 2432 KB Output is correct
8 Correct 6 ms 2304 KB Output is correct
9 Correct 7 ms 2276 KB Output is correct
10 Correct 6 ms 2304 KB Output is correct
11 Correct 5 ms 2304 KB Output is correct
12 Correct 8 ms 2304 KB Output is correct
13 Correct 6 ms 2304 KB Output is correct
14 Correct 5 ms 2304 KB Output is correct
15 Correct 6 ms 2304 KB Output is correct
16 Correct 3 ms 640 KB Output is correct
17 Correct 4 ms 768 KB Output is correct
18 Correct 4 ms 768 KB Output is correct
19 Correct 3 ms 768 KB Output is correct
20 Correct 3 ms 768 KB Output is correct
21 Incorrect 121 ms 3972 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2304 KB Output is correct
2 Correct 7 ms 2304 KB Output is correct
3 Correct 7 ms 2304 KB Output is correct
4 Correct 6 ms 2304 KB Output is correct
5 Correct 7 ms 2304 KB Output is correct
6 Correct 6 ms 2304 KB Output is correct
7 Correct 7 ms 2432 KB Output is correct
8 Correct 6 ms 2304 KB Output is correct
9 Correct 7 ms 2276 KB Output is correct
10 Correct 6 ms 2304 KB Output is correct
11 Correct 5 ms 2304 KB Output is correct
12 Correct 8 ms 2304 KB Output is correct
13 Correct 6 ms 2304 KB Output is correct
14 Correct 5 ms 2304 KB Output is correct
15 Correct 6 ms 2304 KB Output is correct
16 Correct 3 ms 640 KB Output is correct
17 Correct 4 ms 768 KB Output is correct
18 Correct 4 ms 768 KB Output is correct
19 Correct 3 ms 768 KB Output is correct
20 Correct 3 ms 768 KB Output is correct
21 Incorrect 121 ms 3972 KB Output isn't correct
22 Halted 0 ms 0 KB -