Submission #577265

#	Time	Username	Problem	Language	Result	Execution time	Memory
577265		NintsiChkhaidze	Zoltan (COCI16_zoltan)	C++14	0 / 140	238 ms	19876 KiB

zoltan

//#include <iostream>
//#include <vector>
//#include <algorithm>
#include <bits/stdc++.h>
#define pb push_back
#define s second
#define f first
#define left (h<<1),l,(l+r)>>1
#define right ((h<<1)|1),((l+r)>>1) + 1,r
#define int long long

using namespace std;

const int N = 200005,mx = 200005,mod=1000000007;
int a[N];
pair <int,int> inc[N],t[4*N],dc[N];
vector <pair<int,int>> d;

void upd(int h,int l,int r,int idx,int val1,int val2){
    if (l == r){
        t[h].f=val1;
        t[h].s+=val2;
        return;
    }
    if (idx > (l+r)>>1) upd(right,idx,val1,val2);
    else upd(left,idx,val1,val2);

    if (t[h*2].f == t[h*2 + 1].f) t[h] = {t[h*2].f,t[h*2+1].s + t[h*2].s};
    else if(t[h*2].f > t[h*2 + 1].f) t[h] = t[h*2];
    else t[h] = t[h*2 + 1];
}

pair<int,int> get(int h,int l,int r,int L,int R){
    if (r < L || R < l) return {0,0};
    if (L <= l && r <= R) return t[h];
    pair <int,int> x = get(left,L,R),y = get(right,L,R);
    if (x.f == y.f) return {x.f,x.s+y.s};
    else if(x.f > y.f) return x;
    return y;
}

void build(int h,int l,int r){
    if (l==r){
        t[h] = {0,0};
        return;
    }
    build(left),build(right);
    t[h] = {0,0};
}

int pwr(int a,int b){
    int res=1;
    while(b){
        if (b%2) res=(res*a)%mod;
        a=(a*a)%mod;
        b/=2;
    }
    return res;
}
signed main() {
    ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
    int n;
    cin>>n;
    for(int i =1; i<=n;i++){
        cin>>a[i];
        d.pb({a[i],i});
    }
    sort(d.begin(),d.end());
    a[d[0].s] = 1;
    for (int i=1;i<d.size();i++){
        a[d[i].s] = a[d[i - 1].s];
        if (d[i].f > d[i - 1].f) a[d[i].s]++;
    }
    //increasing
    for (int i = n; i >= 1; i--){
        pair <int,int> g = get(1,1,mx,a[i] + 1,mx);
        inc[i] = {g.f + 1,g.s};
        if (g.f > 0){
            upd(1,1,mx,a[i],g.f+1,g.s);
        }else{
            inc[i].s = 1;
            upd(1,1,mx,a[i],1,1);
        }
    }

    build(1,1,mx);
    //decreasing
    for (int i = n; i >= 1; i--){
        pair <int,int> g = get(1,1,mx,1,a[i] - 1);
        dc[i] = {g.f + 1,g.s};
        if (g.f > 0){
            upd(1,1,mx,a[i],g.f+1,g.s);
        }else{
            dc[i].s = 1;
            upd(1,1,mx,a[i],1,1);
        }
    }
    int mxlen = 0,ans = 0;
    for (int i = 1; i <= n; i++){
        int cur = inc[i].f + dc[i].f - 1;
        if (mxlen == cur){
            ans = (ans + inc[i].s*dc[i].s)%mod;
        }else if (mxlen < cur){
            mxlen = cur;
            ans = (inc[i].s*dc[i].s)%mod;
        }
    }

    ans = (ans*pwr(2,n - mxlen))%mod;
    cout<<ans;
}

Compilation message (stderr)

zoltan.cpp: In function 'int main()':
zoltan.cpp:70:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |     for (int i=1;i<d.size();i++){
      |                  ~^~~~~~~~~

• Subtask 1: 0 / 140