oj.uz

Submission #44972

# Submission time Handle Problem Language Result Execution time Memory
44972 2018-04-10T09:02:30 Z OneSubmissionMan Boat (APIO16_boat) C++11
0 / 100
 27 ms 6776 KB 
# 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[N][2*N], pref[N][2*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);
}    
               
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());
   
    for (int i = 0; i < sz(id); i++) {
      if (seglen > 1) { 
        ll sum = 0;   
        ll C = seglen;           
        for (int j = i+1; j < sz(id); j++) {
          int k = j - i + 1;    
          if (k <= seglen) {
            C = (C*k) % Mod * inv (seglen - k + 1) % Mod;
            sum = (sum + C) % Mod;
          }
          Add (dp[t][id[j]], sum * 1ll * pref[t - 1][id[i] - 1] % Mod);
        }                                 
      }                  
      Add (dp[t][id[i]], pref[t - 1][id[i] - 1] * 1ll * seglen % Mod);
    }                   
    pref[t][0] = 1;
    for (int i = 1; i <= n; i++)
      pref[t][i] = (pref[t][i - 1] + dp[t][i] + 0ll + dp[t - 1][i]) % Mod;
  }        
  
  cout << pref[sz(len) - 1][n];

  return 0;
}






// Coded by Z..

Compilation message

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
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 12 ms 6776 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 12 ms 6776 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Runtime error 12 ms 6776 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -