Submission #986078

#	Time	Username	Problem	Language	Result	Execution time	Memory
986078		salmon	Boat (APIO16_boat)	C++14	100 / 100	725 ms	1892 KiB

boat

#include <bits/stdc++.h>
using namespace std;

int N;
pair<int,int> lst[510];
int a, b;
long long int mod = 1'000'000'007;
long long int p[510];
long long int fact[510];
vector<int> de;
vector<int> bat[1100];
map<int,int> mep;

long long int expo(long long int x, long long int b, long long int mul){
    if(mul == 0) return x;
    if(mul % 2 == 1){
        return expo(x * b % mod, b * b % mod, mul / 2);
    }
    else{
        return expo(x, b * b % mod, mul / 2);
    }
}

int main(){

    scanf(" %d",&N);

    for(int i = 1; i <= N; i++){
        scanf(" %d",&a);
        scanf(" %d",&b);

        lst[i] = {a,b};

        de.push_back(a);
        de.push_back(b + 1);
        p[i] = 0;
    }

    p[N + 1] = 0;
    p[0] = 1;

    fact[0] = 1;
    for(int i = 1; i < 510; i++){
        fact[i] = fact[i - 1] *  i % mod;
    }

    sort(de.begin(),de.end());
    de.resize(unique(de.begin(),de.end()) - de.begin());

    for(int i = 0; i < de.size(); i++){
        mep[de[i]] = i;
    }

    for(int i = 1; i <= N; i++){
        for(int j = 0; j < de.size(); j++){
            if(lst[i].first <= de[j] && de[j] <= lst[i].second){
                bat[j].push_back(i);
            }
        }
    }

    for(int i = 0; i < de.size() - 1; i++){
        long long int mul[510];

        int c = de[i + 1] - de[i];

        mul[0] = c;

        for(int i = 1; i < 509; i++){
            mul[i] = mul[i - 1] * (i + c) % mod;
        }

        for(int i = 0; i < 509; i++){
            mul[i] = expo(mul[i], fact[i + 1], mod - 2);
            //printf("%lld ",mul[i]);
        }

        vector<int> v = {0};
        long long int pst[510];

        for(int i = 0; i <= 501; i++){
            pst[i] = 0;
        }

        for(int j = 0; j < bat[i].size(); j++){
            v.push_back(bat[i][j]);
            long long int sum = 0;

            for(int k = 0; k < v.size() - 1; k++){
                int ni = v.size();


                for(int i = v[ni - 2 - k]; i <= v[ni - 1 - k] - 1; i++){
                    sum = (sum + p[i] * mul[k]) % mod;
                }
            }

            pst[bat[i][j]] = sum;
        }

        for(int i = 0; i <= 501; i++){
            p[i] = (p[i] + pst[i]) % mod;
        }
    }

    long long int ans = 0;

    for(int i = 1; i <= N; i++){
        ans = (ans + p[i]) % mod;
    }


    printf("%lld",ans);
}
/*
3
1 2
2 4
2 4

2
1 2
2 4

3
2 2
4 4
4 4
*/

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:50:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     for(int i = 0; i < de.size(); i++){
      |                    ~~^~~~~~~~~~~
boat.cpp:55:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |         for(int j = 0; j < de.size(); j++){
      |                        ~~^~~~~~~~~~~
boat.cpp:62:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     for(int i = 0; i < de.size() - 1; i++){
      |                    ~~^~~~~~~~~~~~~~~
boat.cpp:85:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |         for(int j = 0; j < bat[i].size(); j++){
      |                        ~~^~~~~~~~~~~~~~~
boat.cpp:89:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |             for(int k = 0; k < v.size() - 1; k++){
      |                            ~~^~~~~~~~~~~~~~
boat.cpp:26:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |     scanf(" %d",&N);
      |     ~~~~~^~~~~~~~~~
boat.cpp:29:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |         scanf(" %d",&a);
      |         ~~~~~^~~~~~~~~~
boat.cpp:30:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |         scanf(" %d",&b);
      |         ~~~~~^~~~~~~~~~

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