| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 142603 |
2019-08-10T02:28:36 Z |
12tqian |
Boat (APIO16_boat) |
C++14 |
|
755 ms |
12408 KB |
#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
const double PI = 4 * atan(1);
#define sz(x) (int)(x).size()
#define ll long long
#define ld long double
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define pii pair <int, int>
#define vi vector<int>
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define vpi vector<pair<int, int>>
#define vpd vector<pair<double, double>>
#define pd pair<double, double>
#define f0r(i,a) for(int i=0;i<a;i++)
#define f1r(i,a,b) for(int i=a;i<b;i++)
#define trav(a, x) for (auto& a : x)
void fast_io(){
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
}
void io(string taskname){
string fin = taskname + ".in";
string fout = taskname + ".out";
const char* FIN = fin.c_str();
const char* FOUT = fout.c_str();
freopen(FIN, "r", stdin);
freopen(FOUT, "w", stdout);
fast_io();
}
const ll MOD = 1e9 + 7;
const int MAX = 505;
vector<pair<ll, ll>> bounds;
vector<pair<ll, ll>> ranges;
ll dp[MAX*3][MAX];
ll choose[3*MAX][MAX];
vi possible[MAX];
template<class T, int SZ> struct Seg { // SZ should be power of 2
T ID = 0; // comb(ID,b) must equal b
T comb(T a, T b) {
return (a+b)%MOD;
} // easily change this to min or max
T seg[2*SZ];
Seg() { memset(seg,0,sizeof seg); }
void upd(int p, T value) { // set value at position p
seg[p += SZ] = value;
for (p /= 2; p; p /= 2) seg[p] = comb(seg[2*p],seg[2*p+1]);
}
T query(int l, int r) { // sum on interval [l, r]
r ++; T lres = ID, rres = ID; // make sure non-commutative operations work
for (l += SZ, r += SZ; l < r; l /= 2, r /= 2) {
if (l&1) lres = comb(lres,seg[l++]);
if (r&1) rres = comb(seg[--r],rres);
}
return comb(lres,rres);
}
};
Seg<ll, 2048> seg;
long long modInverse(long long b){
long long ex = MOD - 2;
if (b==1){
return 1;
}
long long r = 1;
while (ex ){
if (ex&1){
r=(r * b)%MOD;
}
ex = ex >> 1;
b = (b * b)%MOD;
}
return r;
}
int main(){
fast_io();
int n;
cin >> n;
set<ll> nums;
f0r(i, n){
int ai, bi;
cin >> ai >> bi;
bounds.eb(mp(ai, bi));
nums.insert(ai);
nums.insert(bi);
}
vi tmp;
for(auto x: nums) tmp.eb(x);
f0r(i, sz(tmp) -1){
if(tmp[i+1]-tmp[i]>1) ranges.eb(tmp[i]+1, tmp[i+1]-1);
}
for(auto x: tmp) ranges.eb(mp(x, x));
sort(all(ranges));
f0r(i, 3*sz(ranges)){
f0r(j, i){
if(j == 0){
choose[i][j] = 1;
}
else{
choose[i][j] = choose[i][j-1];
choose[i][j] *= (ranges[i].s - ranges[i].f+1 -j+ 1);
choose[i][j] %= MOD;
choose[i][j] *= modInverse(j);
choose[i][j] %= MOD;
}
}
}
f0r(i, n){
f0r(j, sz(ranges)){
if(bounds[i].f<= ranges[j].f && bounds[i].s>= ranges[j].s){
possible[i].eb(j);
}
}
}
int to = 0;
int from = 1;
f0r(i, n){
unordered_map<int, ll> change;
for(int j: possible[i]){
f1r(t, 2, n+1){
if(dp[j][t-1] == 0) break;
dp[j][t] = dp[j][t-1];
change[j] += (dp[j][t]*choose[j][t])%MOD;
change[j] %= MOD;
}
dp[j][1] = (j == 0? 0:seg.query(0, j-1)) + 1;
change[j] += (dp[j][1]*choose[j][1])%MOD;
change[j] %= MOD;
}
for(int j: possible[i]){
seg.upd(j, seg.query(j, j)+ change[j]);
}
}
cout << seg.query(0, sz(ranges) - 1) << endl;
return 0;
}
Compilation message
boat.cpp:1:0: warning: ignoring #pragma comment [-Wunknown-pragmas]
#pragma comment(linker, "/stack:200000000")
boat.cpp: In function 'int main()':
boat.cpp:143:9: warning: unused variable 'to' [-Wunused-variable]
int to = 0;
^~
boat.cpp:144:9: warning: unused variable 'from' [-Wunused-variable]
int from = 1;
^~~~
boat.cpp: In function 'void io(std::__cxx11::string)':
boat.cpp:47:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen(FIN, "r", stdin);
~~~~~~~^~~~~~~~~~~~~~~~~
boat.cpp:48:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen(FOUT, "w", stdout);
~~~~~~~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
755 ms |
12408 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
755 ms |
12408 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
152 ms |
6800 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
755 ms |
12408 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
