Submission #92576

#	Time	Username	Problem	Language	Result	Execution time	Memory
92576		nikolapesic2802	Zoltan (COCI16_zoltan)	C++14	21 / 140	385 ms	33792 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 N=2e5+5;
vector<int> duzina(N);
vector<vector<int> > start(N);
void add(int i,int d,vector<int> s)
{
    //printf("Addujem %i %i\n",i,d);
    //cout << s << endl;
    for(;i<N;i+=i&(-i))
    {
        if(duzina[i]==d)
        {
            for(auto p:s)
                start[i].pb(p);
        }
        if(duzina[i]<d)
        {
            duzina[i]=d;
            start[i]=s;
        }
    }
}
pair<int,vector<int> > get(int i)
{
    int d=0;
    vector<int> s;
    for(;i;i-=i&(-i))
    {
        if(duzina[i]==d)
        {
            for(auto p:start[i])
                s.pb(p);
        }
        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].clear();
    }
}
const int mod=1e9+7;
int addd(int a,int b)
{
    a+=b;
    if(a>mod)
        a-=mod;
    return a;
}
int sub(int a,int b)
{
    a-=b;
    if(a<0)
        a+=mod;
    return a;
}
int multi(int a,int b)
{
    return ((ll)a*b)%mod;
}
vector<int> powers(N);
int main()
{
    powers[0]=1;
    for(int i=1;i<N;i++)
        powers[i]=addd(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;
    for(int i=0;i<n;i++)
        niz.pb(mapa[niz1[i]]);
    deque<int> q;
    q.pb(niz[0]);
    int minn=niz[0],maxx=niz[0];
    for(int i=1;i<n;i++)
    {
        if(niz[i]<minn)
        {
            minn=niz[i];
            q.push_front(niz[i]);
            continue;
        }
        if(niz[i]>maxx)
        {
            maxx=niz[i];
            q.push_back(niz[i]);
            continue;
        }
        reset();
        int be=-1;
        int sol=0;
        int pos=0;
        for(auto p:q)
        {
            int best;
            vector<int> start;
            tie(best,start)=get(p);
            if(best==0)
            {
                assert(start.size()==0);
                start.pb(pos);
            }
            best++;
            add(p+1,best,start);
            int adding=0;
            for(auto p:start)
            {
                int delta=pos-p+1;
                delta=n-delta-q.size();
                adding=addd(adding,powers[delta]);
            }
            if(be==best)
                sol=addd(sol,adding);
            if(be<best)
            {
                be=best;
                sol=adding;
            }
            pos++;
        }
        for(int j=i;j<n;j++)
        {
            int p=niz[j];
            int best;
            vector<int> start;
            tie(best,start)=get(p);
            if(best==0)
            {
                assert(start.size()==0);
                start.pb(pos);
            }
            best++;
            add(p+1,best,start);
            int adding=0;
            for(auto p:start)
            {
                int delta=pos-p+1;
                delta=n-delta-q.size();
                adding=addd(adding,powers[delta]);
            }
            if(be==best)
                sol=addd(sol,adding);
            if(be<best)
            {
                be=best;
                sol=adding;
            }
            pos++;
        }
        reset();
        pos=0;
        for(int j=n-1;j>=i;j--)
        {
            int p=niz[j];
            int best;
            vector<int> start;
            tie(best,start)=get(p);
            if(best==0)
            {
                assert(start.size()==0);
                start.pb(pos);
            }
            best++;
            add(p+1,best,start);
            int adding=0;
            for(auto p:start)
            {
                int delta=pos-p+1;
                delta=n-delta-q.size();
                adding=addd(adding,powers[delta]);
            }
            if(be==best)
                sol=addd(sol,adding);
            if(be<best)
            {
                be=best;
                sol=adding;
            }
            pos++;
        }
        for(auto p:q)
        {
            int best;
            vector<int> start;
            tie(best,start)=get(p);
            if(best==0)
            {
                assert(start.size()==0);
                start.pb(pos);
            }
            best++;
            add(p+1,best,start);
            int adding=0;
            for(auto p:start)
            {
                int delta=pos-p+1;
                delta=n-delta-q.size();
                adding=addd(adding,powers[delta]);
            }
            if(be==best)
                sol=addd(sol,adding);
            if(be<best)
            {
                be=best;
                sol=adding;
            }
            pos++;
        }
        printf("%i %i\n",be,sol);
        return 0;
    }
    printf("%i %i\n",n,1);
    return 0;
}

Compilation message (stderr)

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

• Subtask 1: 21 / 140