| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 864457 |
2023-10-23T03:22:40 Z |
NeroZein |
Zoltan (COCI16_zoltan) |
C++17 |
|
305 ms |
19152 KB |
#include <bits/stdc++.h>
#define MAX 205000
const long long MOD = 1e9+7;
typedef std::pair<long long,long long> pii;
typedef std::pair<int,int*> pipo;
///The first number is the size of the sequence, and the second one the number of sequences
pii comb(pii a,pii b){
if(a.first==b.first){
///I'm multiplying MOD by two because I will divide by two later
a.second%=(MOD*2);
b.second%=(MOD*2);
return {a.first,a.second+b.second%(MOD*2)};
}else return std::max(a,b);
}
///Basic seg3
pii tab[MAX*4][2]={};
pii query(int l,int r,int x,int la=0,int ra=MAX-1,int pos=1){
if(la>r||ra<l)return tab[0][x];
if(la>=l&&ra<=r){
return tab[pos][x];
}
int m = (la+ra)/2;
return comb(query(l,r,x,la,m,pos*2),query(l,r,x,m+1,ra,(pos*2)+1));
}
void update(int t,pii k,int x,int la=0,int ra=MAX-1,int pos=1){
if(la>t||ra<t)return;
if(la==ra){
tab[pos][x]=comb(tab[pos][x],k);
return;
}
int m = (la+ra)/2;
update(t,k,x,la,m,pos*2);
update(t,k,x,m+1,ra,(pos*2)+1);
tab[pos][x]=comb(tab[pos*2][x],tab[(pos*2)+1][x]);
}
///Binary exponentiation + Mod
long long binpow(long long a,long long b,long long c){
long long r=1;
while(b){
if(b&1)r=(r*a)%c;
b/=2;
a=(a*a)%c;
}
return r;
}
int main()
{
///You can always start an empty subsequence
pii base = {0,1};
int N;
std::cin>>N;
int array[N]={};
for(auto&x:array)std::cin>>x;
int curbesto=0;
///Coordinate Compression
{
std::vector<pipo> vec;
for(auto&x:array)vec.push_back({x,&x});
std::sort(vec.begin(),vec.end());
int cur=3;
int last=-1;
for(auto&x:vec){
if(x.first!=last){
last=x.first;
++cur;
}
*(x.second)=cur;
}
curbesto=cur;
}
///Longest decreasing subsequence (From end to start)
///Notice that if you reverse this sequence it's increasing
for(int i=N-1;i!=-1;--i){
int x = array[i];
auto resposta=query(x+1,MAX-1,0);
resposta=comb(resposta,base);
update(x,{resposta.first+1,resposta.second},0);
}
///Longest increasing subsequence (From end to start)
///Notice that if you reverse this sequence it's decreasing
for(int i=N-1;i!=-1;--i){
int x = array[i];
auto resposta=query(0,x-1,1);
resposta=comb(resposta,base);
update(x,{resposta.first+1,resposta.second},1);
}
///The idea is the following:
///You want the largest decreasing subsequence smaller than X (you will throw everything to the left)
///And the largest increasing subsequence greater or equal than X(You will throw to the right)
///The other N-(LIS.size) don't really matter, you can throw wherever you want.
///That's why we will use binary exponentiation
///Note:
///When I say increasing (or decreasing) I'm referring from the start (position 0) to the end (position N-1)
pii best={1,N};
//std::cout << "curbesto: " << curbesto << '\n';
for(int i=4;i<curbesto+1;++i){
auto a = query(i,MAX-1,0);
a=comb(a,base);
auto b = query(i-1,i-1,1);
b=comb(b,base);
pii c = {a.first+b.first,a.second*b.second};
best=comb(best,c);
//std::cout << i << ' ' << a.first + b.first << ' ' << best.first << ' ' << best.second << '\n';
//std::cout << i << ' ' << a.first << ' ' << a.second << ' ' << b.first << ' ' << b.second << '\n';
}
///The first element can't be thrown to the right nor left: It needs to be in the middle
///That's why we are dividing by two :)
int menos=1;
if(!(best.second&1)){
menos=0;
best.second/=2;
} else {
assert(false);
}
std::cout<<best.first<<" "<<((((best.second))*binpow(2,N-best.first-menos,MOD))%MOD)<<"\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
2 ms |
604 KB |
Output is correct |
| 8 |
Correct |
2 ms |
604 KB |
Output is correct |
| 9 |
Correct |
2 ms |
604 KB |
Output is correct |
| 10 |
Correct |
2 ms |
616 KB |
Output is correct |
| 11 |
Correct |
208 ms |
15104 KB |
Output is correct |
| 12 |
Correct |
178 ms |
13660 KB |
Output is correct |
| 13 |
Correct |
162 ms |
12992 KB |
Output is correct |
| 14 |
Correct |
215 ms |
14116 KB |
Output is correct |
| 15 |
Correct |
260 ms |
16456 KB |
Output is correct |
| 16 |
Correct |
305 ms |
19152 KB |
Output is correct |
| 17 |
Correct |
236 ms |
16208 KB |
Output is correct |
| 18 |
Correct |
237 ms |
16004 KB |
Output is correct |
| 19 |
Correct |
249 ms |
16000 KB |
Output is correct |
| 20 |
Correct |
235 ms |
15992 KB |
Output is correct |
