답안 #44993 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
44993	2018-04-10T10:04:48 Z	OneSubmissionMan	Boat (APIO16_boat)	C++11	9 / 100	194 ms	4808 KB

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);
}    
               
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 * (seglen - k + 1) % Mod * 1ll * 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

#	결과	실행 시간	메모리	Grader output
1	Correct	9 ms	4344 KB	Output is correct
2	Correct	11 ms	4456 KB	Output is correct
3	Correct	11 ms	4532 KB	Output is correct
4	Correct	9 ms	4544 KB	Output is correct
5	Correct	9 ms	4544 KB	Output is correct
6	Correct	10 ms	4576 KB	Output is correct
7	Correct	9 ms	4576 KB	Output is correct
8	Correct	10 ms	4584 KB	Output is correct
9	Correct	9 ms	4756 KB	Output is correct
10	Correct	9 ms	4756 KB	Output is correct
11	Correct	10 ms	4756 KB	Output is correct
12	Correct	9 ms	4756 KB	Output is correct
13	Correct	10 ms	4756 KB	Output is correct
14	Correct	9 ms	4756 KB	Output is correct
15	Correct	9 ms	4808 KB	Output is correct
16	Correct	3 ms	4808 KB	Output is correct
17	Correct	3 ms	4808 KB	Output is correct
18	Correct	4 ms	4808 KB	Output is correct
19	Correct	3 ms	4808 KB	Output is correct
20	Correct	4 ms	4808 KB	Output is correct

Subtask #2
0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	9 ms	4344 KB	Output is correct
2	Correct	11 ms	4456 KB	Output is correct
3	Correct	11 ms	4532 KB	Output is correct
4	Correct	9 ms	4544 KB	Output is correct
5	Correct	9 ms	4544 KB	Output is correct
6	Correct	10 ms	4576 KB	Output is correct
7	Correct	9 ms	4576 KB	Output is correct
8	Correct	10 ms	4584 KB	Output is correct
9	Correct	9 ms	4756 KB	Output is correct
10	Correct	9 ms	4756 KB	Output is correct
11	Correct	10 ms	4756 KB	Output is correct
12	Correct	9 ms	4756 KB	Output is correct
13	Correct	10 ms	4756 KB	Output is correct
14	Correct	9 ms	4756 KB	Output is correct
15	Correct	9 ms	4808 KB	Output is correct
16	Correct	3 ms	4808 KB	Output is correct
17	Correct	3 ms	4808 KB	Output is correct
18	Correct	4 ms	4808 KB	Output is correct
19	Correct	3 ms	4808 KB	Output is correct
20	Correct	4 ms	4808 KB	Output is correct
21	Incorrect	194 ms	4808 KB	Output isn't correct
22	Halted	0 ms	0 KB	-

Subtask #3
0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	27 ms	4808 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #4
0 / 42.0

#	결과	실행 시간	메모리	Grader output
1	Correct	9 ms	4344 KB	Output is correct
2	Correct	11 ms	4456 KB	Output is correct
3	Correct	11 ms	4532 KB	Output is correct
4	Correct	9 ms	4544 KB	Output is correct
5	Correct	9 ms	4544 KB	Output is correct
6	Correct	10 ms	4576 KB	Output is correct
7	Correct	9 ms	4576 KB	Output is correct
8	Correct	10 ms	4584 KB	Output is correct
9	Correct	9 ms	4756 KB	Output is correct
10	Correct	9 ms	4756 KB	Output is correct
11	Correct	10 ms	4756 KB	Output is correct
12	Correct	9 ms	4756 KB	Output is correct
13	Correct	10 ms	4756 KB	Output is correct
14	Correct	9 ms	4756 KB	Output is correct
15	Correct	9 ms	4808 KB	Output is correct
16	Correct	3 ms	4808 KB	Output is correct
17	Correct	3 ms	4808 KB	Output is correct
18	Correct	4 ms	4808 KB	Output is correct
19	Correct	3 ms	4808 KB	Output is correct
20	Correct	4 ms	4808 KB	Output is correct
21	Incorrect	194 ms	4808 KB	Output isn't correct
22	Halted	0 ms	0 KB	-

답안 #44993

Compilation message

Subtask #1 9.0 / 9.0

Subtask #2 0 / 22.0

Subtask #3 0 / 27.0

Subtask #4 0 / 42.0

Subtask #1
9.0 / 9.0

Subtask #2
0 / 22.0

Subtask #3
0 / 27.0

Subtask #4
0 / 42.0