Submission #45017

#	Time	Username	Problem	Language	Result	Execution time	Memory
45017		OneSubmissionMan	Boat (APIO16_boat)	C++11	9 / 100	103 ms	4816 KiB

boat

# include <bits/stdc++.h>

# define x first    
# define y second
# define mp make_pair
// everything go according to my plan      
# define pb push_back
# define sz(a) (int)(a.size())
# define vec vector         
// shimkenttin kyzdary, dzyn, dzyn, dzyn...
# define y1    Y_U_NO_y1
# define left  Y_U_NO_left
# define right Y_U_NO_right  

using namespace std;

typedef pair <int, int> pii; 
typedef long long ll;
typedef long double ld;

const int Mod = (int)1e9 + 7;
const int MX = 1073741822;
const ll MXLL = 4e18;
const int Sz = 1110111;
// a pinch of soul
inline void Read_rap () {
  ios_base :: sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
}
inline void randomizer3000 () {
  unsigned int seed;
  asm ("rdtsc" : "=A"(seed));
  srand (seed);
}
void files (string problem) {   
  if (fopen ((problem + ".in").c_str(),"r")) {
    freopen ((problem + ".in").c_str(),"r",stdin);
    freopen ((problem + ".out").c_str(),"w",stdout);
  }
}
void localInput(const char in[] = "s") { 
  if (fopen (in, "r")) {
    freopen (in, "r", stdin);
  }
  else
    cerr << "Warning: Input file not found" << endl;
}    
const int N = 500 + 1;

int n;
    
map <int, vec<int> > add;

int dp[2*N][N], pref[2*N][N];      

void Add (int &a, int b) {  
  a += b;
  if (a >= Mod)  a -= Mod;
}      
int binpow (ll a, int b) {
  int res = 1;
  while (b) {
    if (b & 1)
      res = (res * a) % Mod;
    b >>= 1;
    a = (a * a) % Mod;
  }   
  return res;
}           
int inv (int a) {
  return binpow (a, Mod-2);
}    

void Count (int cnt[], int n, int seglen) {
  memset (cnt, 0, (n + 1) * 4);
  static int dv[N];
  for (int i = 1; i <= n; i++)
    dv[i] = inv (i);              
  for (int k = 1; k <= n; k++) {    
    ll kp;
    ll lenp;            
    for (int p = 1; p <= min (seglen, k); p++) {
      if (p > 1) {
        kp = (kp * (k - p + 1) % Mod) * dv[p] % Mod;
        lenp = (lenp * (seglen - p + 1) % Mod) * dv[p] % Mod;
      }
      else
        kp = k, lenp = seglen;
      Add (cnt[k], kp * lenp % Mod);
    }    
  }
  for (int k = 0; k <= n; k++)
    cnt[k]++;  
}     
               
int main()
{
  # ifdef Local
    //localInput();
  # endif
  Read_rap();    

  cin >> n;
  for (int i = 1; i <= n; i++) {
    int a, b; cin >> a >> b;
    add[a].pb (i);     
    add[b + 1].pb (i);
  }                           

  vec <int> len (1);
  vec <vec <int> > v(1);  
  set <int> s;
  for (auto x : add)
    len.pb (x.x), v.pb (x.y);    

  for (int i = 1; i < sz(len) - 1; i++)
    len[i] = len[i + 1] - len[i];
  len.pop_back();  

  for (int i = 0; i <= n; i++)
    pref[0][i] = 1;            
 
                  
  for (int t = 1; t < sz(len); t++) { 
    int seglen = len[t];              
    for (auto y : v[t]) {           
      if (s.count (y)) s.erase (y); else s.insert (y);
    }       
    static vec<int> id;
    id = vec<int> (s.begin(), s.end());
    
    static int cnt[N];
    Count (cnt, sz(id), seglen);
                 
    for (int i = 0; i < sz(id); i++) {
      if (seglen > 1) { 
        for (int j = i + 1; j < sz(id); j++)
          Add (dp[t][id[j]], cnt[j - i + 1 - 2] * 1ll * pref[t - 1][id[i] - 1] % Mod);                                       
      }
      Add (dp[t][id[i]], seglen * 1ll * pref[t - 1][id[i] - 1] % Mod);   
    }     
    /*
    for (int i = 1; i <= n; i++)
      cout << dp[t][i] << ' ';
    cout << endl;
    */
    for (int i = 1; i <= n; i++)
      Add (dp[t][i], dp[t - 1][i]);
    pref[t][0] = 1;
    for (int i = 1; i <= n; i++)
      pref[t][i] = (pref[t][i - 1] + dp[t][i]) % Mod;
  }   
  int ans = pref[sz(len) - 1][n] - 1;
  if (ans < 0)  ans += Mod;

  cout << ans;

  return 0;
}






// Coded by Z..

Compilation message (stderr)

boat.cpp: In function 'void files(std::__cxx11::string)':
boat.cpp:37:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen ((problem + ".in").c_str(),"r",stdin);
     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
boat.cpp:38:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen ((problem + ".out").c_str(),"w",stdout);
     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
boat.cpp: In function 'void localInput(const char*)':
boat.cpp:43:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen (in, "r", stdin);
     ~~~~~~~~^~~~~~~~~~~~~~~~

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