제출 #1197873

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1197873		jorgitox	Boat (APIO16_boat)	C++20	0 / 100	1 ms	324 KiB

boat

/*
  Pura gente del Coach Moy

  
*/

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using pi = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;

#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define SZ(x) ((int)(x).size())
#define ALL(x) begin(x), end(x)
#define RALL(x) rbegin(x), rend(x)
#define FOR(i, a, b) for (int i = (int)a; i < (int)b; ++i)
#define ROF(i, a, b) for (int i = (int)a - 1; i >= (int)b; --i)
#define INF 1e18
#define ENDL '\n'

const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
const ll MOD = 1000000007;

inline int add(int x, int y, int m) {
  return x + y < m ? x + y : x + y - m;
}
inline int sub(int x, int y, int m) {
  return x >= y ? x - y : x - y + m;
}
inline int mul(int x, int y, int m) {
  return int((ll)x * y % m);
}

int modPow(int x, int n, int m){
  if(n == 0)
    return 1;

  int u = modPow(x, n / 2, m) % m;
  u = mul(u, u, m);

  if(n & 1)
    u = mul(u, x, m);
  
  return u;
}

signed main() {
  cin.tie(0)->sync_with_stdio(0);

  int n; cin >> n;

  vector<pi> a(n); FOR(i, 0, n) cin >> a[i].first >> a[i].second;

  map<int, int> mp; 
  FOR(i, 0, n){
    if(mp.find(a[i].first) == mp.end()) mp[a[i].first] = SZ(mp);
    if(mp.find(a[i].second) == mp.end()) mp[a[i].second] = SZ(mp);
  }

  map<int, int> rmp;
  FOR(i, 0, n){
    rmp[mp[a[i].first]] = a[i].first; a[i].first = mp[a[i].first];
    rmp[mp[a[i].second]] = a[i].second; a[i].second = mp[a[i].second];
  }

  vi dp(SZ(mp));

  ROF(i, n, 0){
    int l = a[i].first, r = a[i].second;
    int x = rmp[l];

    FOR(j, l, r + 1){
      int y = rmp[j + 1];
      dp[i] = add(dp[i], mul(y - x + 1, dp[j], MOD), MOD);
    }

    int y = rmp[r];

    dp[i] = add(dp[i], y - x + 1, MOD);
  }

  cout << dp[0] - 1;

  return 0;
}

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