oj.uz

Submission #44990

# Submission time Handle Problem Language Result Execution time Memory
44990 2018-04-10T09:48:17 Z OneSubmissionMan Boat (APIO16_boat) C++11
9 / 100
 210 ms 4844 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[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);
}    
               
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.back() = 1;
      
  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 * (seglen - k + 1) % Mod * inv (k)) % 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);
    }               
    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

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

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4344 KB Output is correct
2 Correct 10 ms 4452 KB Output is correct
3 Correct 9 ms 4488 KB Output is correct
4 Correct 11 ms 4488 KB Output is correct
5 Correct 9 ms 4536 KB Output is correct
6 Correct 11 ms 4564 KB Output is correct
7 Correct 9 ms 4564 KB Output is correct
8 Correct 9 ms 4640 KB Output is correct
9 Correct 9 ms 4656 KB Output is correct
10 Correct 9 ms 4720 KB Output is correct
11 Correct 9 ms 4720 KB Output is correct
12 Correct 10 ms 4720 KB Output is correct
13 Correct 9 ms 4720 KB Output is correct
14 Correct 9 ms 4720 KB Output is correct
15 Correct 10 ms 4844 KB Output is correct
16 Correct 4 ms 4844 KB Output is correct
17 Correct 4 ms 4844 KB Output is correct
18 Correct 4 ms 4844 KB Output is correct
19 Correct 5 ms 4844 KB Output is correct
20 Correct 3 ms 4844 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4344 KB Output is correct
2 Correct 10 ms 4452 KB Output is correct
3 Correct 9 ms 4488 KB Output is correct
4 Correct 11 ms 4488 KB Output is correct
5 Correct 9 ms 4536 KB Output is correct
6 Correct 11 ms 4564 KB Output is correct
7 Correct 9 ms 4564 KB Output is correct
8 Correct 9 ms 4640 KB Output is correct
9 Correct 9 ms 4656 KB Output is correct
10 Correct 9 ms 4720 KB Output is correct
11 Correct 9 ms 4720 KB Output is correct
12 Correct 10 ms 4720 KB Output is correct
13 Correct 9 ms 4720 KB Output is correct
14 Correct 9 ms 4720 KB Output is correct
15 Correct 10 ms 4844 KB Output is correct
16 Correct 4 ms 4844 KB Output is correct
17 Correct 4 ms 4844 KB Output is correct
18 Correct 4 ms 4844 KB Output is correct
19 Correct 5 ms 4844 KB Output is correct
20 Correct 3 ms 4844 KB Output is correct
21 Incorrect 210 ms 4844 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4344 KB Output is correct
2 Correct 10 ms 4452 KB Output is correct
3 Correct 9 ms 4488 KB Output is correct
4 Correct 11 ms 4488 KB Output is correct
5 Correct 9 ms 4536 KB Output is correct
6 Correct 11 ms 4564 KB Output is correct
7 Correct 9 ms 4564 KB Output is correct
8 Correct 9 ms 4640 KB Output is correct
9 Correct 9 ms 4656 KB Output is correct
10 Correct 9 ms 4720 KB Output is correct
11 Correct 9 ms 4720 KB Output is correct
12 Correct 10 ms 4720 KB Output is correct
13 Correct 9 ms 4720 KB Output is correct
14 Correct 9 ms 4720 KB Output is correct
15 Correct 10 ms 4844 KB Output is correct
16 Correct 4 ms 4844 KB Output is correct
17 Correct 4 ms 4844 KB Output is correct
18 Correct 4 ms 4844 KB Output is correct
19 Correct 5 ms 4844 KB Output is correct
20 Correct 3 ms 4844 KB Output is correct
21 Incorrect 210 ms 4844 KB Output isn't correct
22 Halted 0 ms 0 KB -