oj.uz

Submission #1041034

# Submission time Handle Problem Language Result Execution time Memory
1041034 2024-08-01T14:06:01 Z ssense Zoltan (COCI16_zoltan) C++14
112 / 140
 233 ms 23120 KB 
#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)
    {
        tree1[v] = make_pair(val1, 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)
    {
        tree2[v] = make_pair(val1, 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+1, smaller.sc);
        update2(0, 0, b.size()+1, a[i], bigger.fr+1, 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

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:55:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |     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:71:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   71 |     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:86:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   86 |     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:102:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  102 |     int mid = l+r>>1;
      |               ~^~

Subtask #1
112.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 436 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 1 ms 344 KB Output is correct
8 Correct 2 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 127 ms 20048 KB Output is correct
12 Correct 117 ms 21592 KB Output is correct
13 Correct 105 ms 13136 KB Output is correct
14 Correct 136 ms 20000 KB Output is correct
15 Correct 178 ms 22612 KB Output is correct
16 Correct 233 ms 23120 KB Output is correct
17 Incorrect 166 ms 22612 KB Output isn't correct
18 Incorrect 158 ms 22732 KB Output isn't correct
19 Incorrect 157 ms 22608 KB Output isn't correct
20 Incorrect 154 ms 22680 KB Output isn't correct