oj.uz

Submission #113973

# Submission time Handle Problem Language Result Execution time Memory
113973 2019-05-29T12:11:00 Z dorijanlendvaj Boat (APIO16_boat) C++14
27 / 100
 1177 ms 72440 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define x first
#define y second
#define pii pair<int,int>
#define pb push_back
#define eb emplace_back

using namespace std;
using namespace __gnu_pbds;

typedef long long int ll;
typedef unsigned long long int ull;
int MOD=1000000007;
int MOD2=998244353;
vector<int> bases;
const ll LLINF=1ll<<60;
const char en='\n';

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void yes() {cout<<"YES"<<en; exit(0);}
void no() {cout<<"NO"<<en; exit(0);}
inline int rund() {int x576363482791fuweh=rng();return abs(x576363482791fuweh)%RAND_MAX;}
template<class T>
void prVec(vector<T> w)
{
	cout<<w.size()<<endl;
	for (int i=0;i<int(w.size())-1;++i) cout<<w[i]<<' ';
	if (w.size()) cout<<w[w.size()-1]<<endl;
}

void M998()
{
	swap(MOD,MOD2);
}

ll raand()
{
	ll a=rund();
	a*=RAND_MAX;
	a+=rund();
    return a;
}

#define rand raand

ll raaand()
{
	return raand()*(MOD-7)+raand();
}

string to_upper(string a)
{
	for (int i=0;i<(int)a.size();++i) if (a[i]>='a' && a[i]<='z') a[i]-='a'-'A';
	return a;
}

string to_lower(string a)
{
	for (int i=0;i<(int)a.size();++i) if (a[i]>='A' && a[i]<='Z') a[i]+='a'-'A';
	return a;
}

ll sti(string a)
{
	ll k=0;
	for (int i=0;i<(int)a.size();++i)
	{
		k*=10;
		k+=a[i]-'0';
	}
	return k;
}

string its(ll k)
{
	if (k==0) return "0";
	string a;
	while (k)
	{
		a.push_back((k%10)+'0');
		k/=10;
	}
	reverse(a.begin(),a.end());
	return a;
}

ll min(ll a,int b)
{
	if (a<b) return a;
	return b;
}

ll min(int a,ll b)
{
	if (a<b) return a;
	return b;
}

ll max(ll a,int b)
{
	if (a>b) return a;
	return b;
}

ll max(int a,ll b)
{
	if (a>b) return a;
	return b;
}

ll gcd(ll a,ll b)
{
	if (b==0) return a;
	return gcd(b,a%b);
}

ll lcm(ll a,ll b)
{
	return a/gcd(a,b)*b;
}

template<class T,class K>
pair<T,K> mp(T a,K b)
{
	return make_pair(a,b);
}

inline int mult(ll a,ll b)
{
	return (a*b)%MOD;
}

inline int pot(int n,int k)
{
	if (k==0) return 1;
	ll a=pot(n,k/2);
	a=mult(a,a);
	if (k%2) return mult(a,n);
	else return a;
}

int divide(int a,int b)
{
	return mult(a,pot(b,MOD-2));
}

inline int sub(int a,int b)
{
	if (a-b>=0) return a-b;
	return a-b+MOD;
}

inline int add(int a,int b)
{
	if (a+b>=MOD) return a+b-MOD;
	return a+b;
}

bool prime(ll a)
{
	if (a==1) return 0;
	for (int i=2;i<=round(sqrt(a));++i)
	{
		if (a%i==0) return 0;
	}
	return 1;
}

ll has(string x)
{
	ll h1=0,h2=0;
	x=to_lower(x);
	for (char a: x)
	{
		h1*=bases[0];
		h1+=a-'a';
		h1%=bases[3];
		h2*=bases[1];
		h2+=a-'a';
		h2%=bases[4];
	}
	return h1*(MOD+13893829)+h2;
}

const int N=1010,M=1<<10,SZ=2907;
int n,fac[N],inf[N],dp[N],pre[N],in[N];
pii h[N];
vector<pii> ha[N][SZ];
vector<pii> so;
vector<int> poi;
set<int> poo;
int seg[M+N][N];
int po[N];
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};

void addH(int i,int j,int x)
{
	int i1=i;
	i=(i^0x183b4278)%SZ;
	for (auto &a: ha[j][i]) if (a.y==i1)
	{
		a.x=add(a.x,x);
		return;
	}
	ha[j][i].pb({x,i1});
}

void upd(int i,int j,int x)
{
	i+=M;
	seg[i][j]=add(seg[i][j],x);
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	for (int i=0;i<10;++i) bases.push_back((rand()%MOD+13893829)%MOD);
	cin>>n;
	fac[0]=1;
	const int MAX=505;
	for (int i=1;i<=MAX;++i) fac[i]=mult(fac[i-1],i),in[i]=divide(1,i);
	inf[MAX]=divide(1,fac[MAX]);
	for (int i=MAX-1;i>=0;--i) inf[i]=mult(inf[i+1],i+1);
	for (int i=0;i<n;++i) cin>>h[i].x>>h[i].y,poo.insert(h[i].x),poo.insert(h[i].y+1);
	for (auto a: poo) poi.pb(a);
	for (int i=1;i<poi.size();++i) so.pb({poi[i-1],poi[i]});
	so.pb({poi.back(),MOD-6});
	upd(0,0,1);
	for (int k=0;k<=MAX;++k) pre[k]+=1;
	dp[0]=1;
	for (int i=0;i<n;++i)
	{
		for (int j=upper_bound(so.begin(),so.end(),mp(h[i].y+1,0))-so.begin()-1;j>=0 && so[j].x>=h[i].x;--j)
		{
			int jj=j+1;
			for (int k=MAX-1;k>=0;--k) upd(jj,k+1,seg[jj+M][k]);
			//for (int k=MAX-1;k>=0;--k) upd(jj,k,-seg[jj+M][k+1]);
			for (int k=0;k<1;++k) upd(jj,k,pre[j]);
			//cout<<en<<i<<' '<<jj<<' '<<so[j].x<<' '<<so[j].y;
			int re=0,r1=1;
			for (int k=0;k<min(MAX,so[j].y-so[j].x);++k)
			{
				r1=mult(r1,so[j].y-so[j].x-k);
				r1=mult(r1,in[k+1]);
				re=add(re,mult(r1,seg[jj+M][k]));
			}
			for (int k=jj;k<=MAX*2;++k) pre[k]=add(pre[k],sub(re,dp[jj]));
			dp[jj]=re;
			//cout<<' '<<re<<endl;
			//cout<<i<<' '<<j<<' '<<so[j].x<<' '<<so[j].y<<endl;
			//for (int k=0;k<MAX;++k) cout<<seg[jj+M][k]<<' ';
			//cout<<endl<<en<<endl;
			//upd(j+1,mult(get(0,j+1),so[j].y-so[j].x));
		}
	}
	int res=0;
	for (int i=1;i<=so.size();++i) for (int k=0;k<min(MAX,so[i-1].y-so[i-1].x);++k) if (1)
	{
		int r1=1;
		for (int j=so[i-1].y-so[i-1].x;j>=so[i-1].y-so[i-1].x-k;--j) r1=mult(r1,j);
		r1=mult(r1,inf[k+1]);
		r1=mult(r1,seg[i+M][k]);
		//if (r1) cout<<i<<' '<<k<<' '<<r1<<endl;
		res=add(res,r1);
	}
	cout<<res;
}

Compilation message

boat.cpp: In function 'int main()':
boat.cpp:229:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=1;i<poi.size();++i) so.pb({poi[i-1],poi[i]});
               ~^~~~~~~~~~~
boat.cpp:260:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=1;i<=so.size();++i) for (int k=0;k<min(MAX,so[i-1].y-so[i-1].x);++k) if (1)
               ~^~~~~~~~~~~

Subtask #1
0 / 9.0

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

Subtask #2
0 / 22.0

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

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 662 ms 70224 KB Output is correct
2 Correct 612 ms 70136 KB Output is correct
3 Correct 629 ms 70292 KB Output is correct
4 Correct 636 ms 70176 KB Output is correct
5 Correct 649 ms 70136 KB Output is correct
6 Correct 707 ms 70392 KB Output is correct
7 Correct 720 ms 70264 KB Output is correct
8 Correct 716 ms 70304 KB Output is correct
9 Correct 723 ms 70288 KB Output is correct
10 Correct 718 ms 70316 KB Output is correct
11 Correct 675 ms 70264 KB Output is correct
12 Correct 634 ms 70264 KB Output is correct
13 Correct 640 ms 70136 KB Output is correct
14 Correct 634 ms 70136 KB Output is correct
15 Correct 639 ms 70136 KB Output is correct
16 Correct 316 ms 69752 KB Output is correct
17 Correct 315 ms 69884 KB Output is correct
18 Correct 314 ms 69880 KB Output is correct
19 Correct 305 ms 70008 KB Output is correct
20 Correct 325 ms 69752 KB Output is correct

Subtask #4
0 / 42.0

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