Submission #92579

#	Time	Username	Problem	Language	Result	Execution time	Memory
92579		nikolapesic2802	Zoltan (COCI16_zoltan)	C++14	140 / 140	318 ms	20288 KiB

zoltan

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>

#define ll long long
#define pb push_back
#define sz(x) (int)(x).size()
#define mp make_pair
#define f first
#define s second
#define all(x) x.begin(), x.end()

using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;

template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>; ///find_by_order(),order_of_key()
template<class T1, class T2> ostream& operator<<(ostream& os, const pair<T1,T2>& a) { os << '{' << a.f << ", " << a.s << '}'; return os; }
template<class T> ostream& operator<<(ostream& os, const vector<T>& a) {
	os << '{';
	for(int i=0;i<sz(a);i++)
	{
		if(i>0&&i<sz(a))
			os << ", ";
		os << a[i];
	}
	os << '}';
    return os;
}
const int mod=1e9+7;
int add(int a,int b)
{
    a+=b;
    if(a>=mod)
        a-=mod;
    return a;
}
int multi(int a,int b)
{
    return ((ll)a*b)%mod;
}
const int N=2e5+5;
vector<int> duzina(N);
vector<int> start(N);
void update(int i,int d,int s)
{
    for(;i<N;i+=i&(-i))
    {
        if(duzina[i]==d)
        {
            start[i]=add(start[i],s);
        }
        if(duzina[i]<d)
        {
            duzina[i]=d;
            start[i]=s;
        }
    }
}
pair<int,int> get(int i)
{
    int d=0;
    int s=0;
    for(;i;i-=i&(-i))
    {
        if(duzina[i]==d)
        {
            s=add(s,start[i]);
        }
        if(duzina[i]>d)
        {
            d=duzina[i];
            s=start[i];
        }
    }
    return make_pair(d,s);
}
void reset()
{
    for(int i=0;i<N;i++)
    {
        duzina[i]=0;
        start[i]=0;
    }
}
vector<int> powers(N);
int main()
{
    powers[0]=1;
    for(int i=1;i<N;i++)
        powers[i]=add(powers[i-1],powers[i-1]);
    int n;
	scanf("%i",&n);
	vector<int> niz,niz1(n);
	for(int i=0;i<n;i++)
        scanf("%i",&niz1[i]);
    vector<int> ss=niz1;
    sort(all(ss));
    ss.erase(unique(all(ss)),ss.end());
    map<int,int> mapa;
    for(int i=0;i<ss.size();i++)
        mapa[ss[i]]=i+1;
    for(int i=0;i<n;i++)
        niz.pb(mapa[niz1[i]]);
    reverse(all(niz));
    vector<pair<int,int> > f,b;
    reset();
    for(auto p:niz)
    {
        int best;
        int num;
        tie(best,num)=get(p);
        if(best==0)
            num=1;
        best++;
        f.pb({best,num});
        update(p+1,best,num);
    }
    reset();
    vector<int> rev;
    for(auto p:niz)
    {
        rev.pb(N-p);
    }
    niz=rev;
    for(auto p:niz)
    {
        int best;
        int num;
        tie(best,num)=get(p);
        if(best==0)
            num=1;
        best++;
        b.pb({best,num});
        update(p+1,best,num);
    }
    int best=0;
    int sum=0;
    for(int i=0;i<n;i++)
    {
        int p=f[i].f+b[i].f-1;
        int num=multi(powers[n-p],multi(f[i].s,b[i].s));
        if(best==p)
            sum=add(sum,num);
        if(best<p)
        {
            best=p;
            sum=num;
        }
    }
    printf("%i %i\n",best,sum);
}

Compilation message (stderr)

zoltan.cpp: In function 'int main()':
zoltan.cpp:102:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<ss.size();i++)
                 ~^~~~~~~~~~
zoltan.cpp:94:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i",&n);
  ~~~~~^~~~~~~~~
zoltan.cpp:97:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i",&niz1[i]);
         ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 140 / 140