oj.uz

Submission #1041014

# Submission time Handle Problem Language Result Execution time Memory
1041014 2024-08-01T13:55:56 Z ssense Zoltan (COCI16_zoltan) C++14
112 / 140
 258 ms 21980 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;
            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 1 ms 348 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 444 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 134 ms 19368 KB Output is correct
12 Correct 117 ms 18976 KB Output is correct
13 Correct 111 ms 12520 KB Output is correct
14 Correct 163 ms 18936 KB Output is correct
15 Correct 206 ms 21568 KB Output is correct
16 Correct 258 ms 19924 KB Output is correct
17 Incorrect 221 ms 21840 KB Output isn't correct
18 Incorrect 175 ms 21976 KB Output isn't correct
19 Incorrect 182 ms 21980 KB Output isn't correct
20 Incorrect 181 ms 21840 KB Output isn't correct