Submission #110812

#	Time	Username	Problem	Language	Result	Execution time	Memory
110812		tictaccat	Boat (APIO16_boat)	C++14	9 / 100	6 ms	384 KiB

boat

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int MAX = 500 + 5;
const int MOD = 1e9 + 7;

int N,ans;
vector<int> a(MAX), b(MAX), ways(2*MAX), newWays(2*MAX), bin; //ways[i] = ways of ending between bin[i] and bin[i+1]-1

main() {

    cin >> N;

    for (int i = 0; i < N; i++) {
        cin >> a[i] >> b[i];
        b[i]++;
        bin.push_back(a[i]);
        bin.push_back(b[i]);
    }

    sort(bin.begin(),bin.end());
    bin.erase(unique(bin.begin(),bin.end()),bin.end());

    for (int i = 0; i < N; i++) {
        int pre = 1, k = 0;
        for (; bin[k] < a[i]; k++) {pre += ways[k]; pre %= MOD;}
        for (; k+1 < bin.size() && bin[k+1] <= b[i]; k++) {
            int sz = bin[k+1] - bin[k];
            newWays[k] += pre + ways[k] * sz % MOD * (sz-1) % MOD / 2;
            newWays[k] %= MOD;
            pre += ways[k]*sz;
            pre %= MOD;
        }
        ways = newWays;
    }

    for (int k = 0; k < bin.size(); k++) {ans += ways[k]*(bin[k+1]-bin[k]); ans %= MOD;}

    cout << (ans < 0 ? ans + MOD : ans) << "\n";

    return 0;
}

Compilation message (stderr)

boat.cpp:13:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
boat.cpp: In function 'int main()':
boat.cpp:30:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (; k+1 < bin.size() && bin[k+1] <= b[i]; k++) {
                ~~~~^~~~~~~~~~~~
boat.cpp:40:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int k = 0; k < bin.size(); k++) {ans += ways[k]*(bin[k+1]-bin[k]); ans %= MOD;}
                     ~~^~~~~~~~~~~~

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