Submission #599620

#	Time	Username	Problem	Language	Result	Execution time	Memory
599620		cadmiumsky	Boat (APIO16_boat)	C++14	100 / 100	688 ms	444 KiB

boat

#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()

using namespace std;
using ll = long long;
const int nmax = 5e2 + 5, mod = 1e9 + 7;

ll inv[nmax];
int active[nmax], dp[nmax], tmpdp[nmax];

int main() {
  inv[1] = 1;
  for(int i = 2; i < nmax; i++) {
    inv[i] = inv[mod % i] * (mod - mod / i) % mod;
  }
  
  vector<pair<int,int>> events;
  vector<int> pos;
  int n;
  cin >> n;
  for(int l, r, i = 1; i <= n; i++) {
    cin >> l >> r;
    events.emplace_back(l, i);
    events.emplace_back(r + 1, -i);
    pos.push_back(l);
    pos.push_back(r + 1);
  }
  sort(all(events));
  sort(all(pos));
  pos.resize(unique(all(pos)) - pos.begin());
  dp[0] = 1;
  
  int ptr = 0, last = 0;
  for(auto poz : pos) {
    int dt = poz - last;
    for(int i = 0; i <= n; i++)
      tmpdp[i] = 0;
    for(int i = 0; i <= n; i++) {
      ll accum = 1, high = dt - 1, cnt = 0;
       for(int j = i + 1; j <= n; j++) {
         if(active[j]) {
           high++;
           cnt++;
           accum = accum * high % mod * inv[cnt] % mod;
           tmpdp[j] = ((ll)tmpdp[j] + (ll)dp[i] * accum) % mod; 
         }
       }
    }
    for(int i = 0; i <= n; i++)
      dp[i] = (dp[i] + tmpdp[i]) % mod;
    while(ptr < events.size() && events[ptr].first <= poz) {
      int x = events[ptr].second;
      active[abs(x)] += (x / abs(x));
      ptr++;
    }
    //cerr << last << ' ' << poz << '\n';
    //for(int i = 1; i <= n; i++)
      //cerr << dp[i] << ' ';
    //cerr << '\n';
    //cerr << '\n';
    last = poz;
  }
  int sum = 0;
  for(int i = 1; i <= n; i++)
    sum = (sum + dp[i]) % mod;
  cout << sum << '\n';
}

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:51:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     while(ptr < events.size() && events[ptr].first <= poz) {
      |           ~~~~^~~~~~~~~~~~~~~

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