oj.uz

Submission #1041006

# Submission time Handle Problem Language Result Execution time Memory
1041006 2024-08-01T13:49:01 Z ssense Zoltan (COCI16_zoltan) C++14
112 / 140
 212 ms 21844 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 = (2e5)+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;
        }
        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 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 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 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 126 ms 19364 KB Output is correct
12 Correct 117 ms 18768 KB Output is correct
13 Correct 106 ms 12496 KB Output is correct
14 Correct 140 ms 18980 KB Output is correct
15 Correct 172 ms 21588 KB Output is correct
16 Correct 212 ms 20048 KB Output is correct
17 Incorrect 154 ms 21840 KB Output isn't correct
18 Incorrect 156 ms 21840 KB Output isn't correct
19 Incorrect 154 ms 21844 KB Output isn't correct
20 Incorrect 160 ms 21844 KB Output isn't correct