oj.uz

Submission #113975

# Submission time Handle Problem Language Result Execution time Memory
113975 2019-05-29T12:13:26 Z dorijanlendvaj Boat (APIO16_boat) C++14
27 / 100
 1151 ms 73084 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
#pragma GCC optimize("unroll-loops")

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=1020,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:230: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:261: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 1151 ms 73084 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 1151 ms 73084 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 638 ms 70908 KB Output is correct
2 Correct 631 ms 70876 KB Output is correct
3 Correct 641 ms 70904 KB Output is correct
4 Correct 644 ms 70776 KB Output is correct
5 Correct 650 ms 70904 KB Output is correct
6 Correct 717 ms 70964 KB Output is correct
7 Correct 733 ms 70904 KB Output is correct
8 Correct 733 ms 71032 KB Output is correct
9 Correct 703 ms 70904 KB Output is correct
10 Correct 729 ms 70932 KB Output is correct
11 Correct 702 ms 71028 KB Output is correct
12 Correct 641 ms 70904 KB Output is correct
13 Correct 648 ms 70904 KB Output is correct
14 Correct 626 ms 70776 KB Output is correct
15 Correct 643 ms 70904 KB Output is correct
16 Correct 315 ms 70620 KB Output is correct
17 Correct 318 ms 70392 KB Output is correct
18 Correct 338 ms 70620 KB Output is correct
19 Correct 313 ms 70520 KB Output is correct
20 Correct 329 ms 70556 KB Output is correct

Subtask #4
0 / 42.0

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