oj.uz

Submission #110809

# Submission time Handle Problem Language Result Execution time Memory
110809 2019-05-12T09:25:53 Z tictaccat Boat (APIO16_boat) C++14
0 / 100
 3 ms 384 KB 
#include <bits/stdc++.h>

using namespace std;

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

int 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 < 2; i++) {
        int k = lower_bound(bin.begin(),bin.end(),a[i]) - bin.begin();
        int pre = 1;
        for (int j = 0; j < k; j++) {pre += ways[j]; 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

boat.cpp: In function 'int main()':
boat.cpp:29:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (; k+1 < bin.size() && bin[k+1] <= b[i]; k++) {
                ~~~~^~~~~~~~~~~~
boat.cpp:39: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
0 / 9.0

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

Subtask #2
0 / 22.0

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

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

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