Submission #1041049

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041049		ssense	Zoltan (COCI16_zoltan)	C++14	140 / 140	209 ms	20048 KiB

zoltan

#include <iostream>
#include <algorithm>
#include <vector>
#include <array>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <chrono>
#include <random>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <iomanip>
#include <bitset>
#include <limits.h>
#include <cassert>

#define fr first
#define sc second

using namespace std;

#define int long long

const int MOD = (1e9)+7;

const int N = (3e5)+5;

pair<int, int> tree1[4*N], tree2[4*N];

pair<int, int> combine(pair<int, int> a, pair<int, int> b)
{
    int mx = max(a.fr, b.fr);
    int ans = 0;
    if(a.fr == mx){ans+=a.sc;}
    if(b.fr == mx){ans+=b.sc;}
    ans%=MOD;
    return make_pair(mx, ans);
}

void update1(int v, int l, int r, int pos, int val1, int val2)
{
    if(pos < l || pos > r)
    {
        return;
    }
    if(l == r)
    {
        if(tree1[v].fr < val1)
        {
            tree1[v] = make_pair(val1, val2);
        }
        else
        {
            tree1[v].sc+=val2;
        }
        return;
    }
    int mid = l+r>>1;
    update1(2*v+1, l, mid, pos, val1, val2);
    update1(2*v+2, mid+1, r, pos, val1, val2);
    tree1[v] = combine(tree1[2*v+1], tree1[2*v+2]);
}

pair<int, int> get1(int v, int l, int r, int tl, int tr)
{
    if(r < tl || l > tr)
    {
        return make_pair(0, 0);
    }
    if(l >= tl && r <= tr)
    {
        return tree1[v];
    }
    int mid = l+r>>1;
    return combine(get1(2*v+1, l, mid, tl, tr), get1(2*v+2, mid+1, r, tl, tr));
}

void update2(int v, int l, int r, int pos, int val1, int val2)
{
    if(pos < l || pos > r)
    {
        return;
    }
    if(l == r)
    {
        if(tree2[v].fr < val1)
        {
            tree2[v] = make_pair(val1, val2);
        }
        else
        {
            tree2[v].sc+=val2;
        }
        return;
    }
    int mid = l+r>>1;
    update2(2*v+1, l, mid, pos, val1, val2);
    update2(2*v+2, mid+1, r, pos, val1, val2);
    tree2[v] = combine(tree2[2*v+1], tree2[2*v+2]);
}

pair<int, int> get2(int v, int l, int r, int tl, int tr)
{
    if(r < tl || l > tr)
    {
        return make_pair(0, 0);
    }
    if(l >= tl && r <= tr)
    {
        return tree2[v];
    }
    int mid = l+r>>1;
    return combine(get2(2*v+1, l, mid, tl, tr), get2(2*v+2, mid+1, r, tl, tr));
}


void solve()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    vector<int> b = a;
    sort(b.begin(), b.end());
    b.resize(unique(b.begin(), b.end())-b.begin());
    for(int i = 0; i < n; i++)
    {
        a[i] = lower_bound(b.begin(), b.end(), a[i]) - b.begin() + 1;
    }
    int ans = 0, count = 0;
    for(int i = n-1; i >= 0; i--)
    {
        pair<int, int> smaller = get1(0, 0, b.size()+1, 0, a[i]-1);
        smaller.sc = max(smaller.sc, 1LL);
        // cout << a[i] << " SMALL: " << smaller.fr << " " << smaller.sc << endl;
        pair<int, int> bigger = get2(0, 0, b.size()+1, a[i]+1, b.size()+1);
        bigger.sc = max(bigger.sc, 1LL);
        // cout << a[i] << " BIG: " << bigger.fr << " " << bigger.sc << endl;
        if(smaller.fr + bigger.fr+1 == ans)
        {
            count+=(smaller.sc*bigger.sc)%MOD;
            count%=MOD;
        }
        else if(smaller.fr + bigger.fr+1 > ans)
        {
            ans = smaller.fr + bigger.fr+1;
            count = (smaller.sc*bigger.sc)%MOD;
        }
        update1(0, 0, b.size()+1, a[i], smaller.fr+1LL, smaller.sc);
        update2(0, 0, b.size()+1, a[i], bigger.fr+1LL, bigger.sc);
    }
    cout << ans << " ";
    for(int i = ans; i < n; i++)
    {
        count*=2;
        count%=MOD;
    }
    cout << count << endl;
}

int32_t main()
{
    int t = 1;
    //cin >> t;
    while(t--)
    {
        solve();
    }
}

/*
#include <iostream>
#include <algorithm>
#include <vector>
#include <array>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <chrono>
#include <random>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <iomanip>
#include <bitset>
#include <cassert>
*/

Compilation message (stderr)

zoltan.cpp: In function 'void update1(long long int, long long int, long long int, long long int, long long int, long long int)':
zoltan.cpp:62:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   62 |     int mid = l+r>>1;
      |               ~^~
zoltan.cpp: In function 'std::pair<long long int, long long int> get1(long long int, long long int, long long int, long long int, long long int)':
zoltan.cpp:78:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   78 |     int mid = l+r>>1;
      |               ~^~
zoltan.cpp: In function 'void update2(long long int, long long int, long long int, long long int, long long int, long long int)':
zoltan.cpp:100:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  100 |     int mid = l+r>>1;
      |               ~^~
zoltan.cpp: In function 'std::pair<long long int, long long int> get2(long long int, long long int, long long int, long long int, long long int)':
zoltan.cpp:116:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  116 |     int mid = l+r>>1;
      |               ~^~

• Subtask 1: 140 / 140