oj.uz

Submission #1041004

# Submission time Handle Problem Language Result Execution time Memory
1041004 2024-08-01T13:46:14 Z ssense Zoltan (COCI16_zoltan) C++14
84 / 140
 225 ms 23288 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);
        // 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);
        // 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;
        }
        if(ans == 0)
        {
            ans = 1;
            count = 1;
        }
        else if(ans == 1)
        {
            count++;
        }
        update1(0, 0, b.size()+1, a[i], smaller.fr+1, max(1LL, smaller.sc));
        update2(0, 0, b.size()+1, a[i], bigger.fr+1, max(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

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
84.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 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 Incorrect 0 ms 348 KB Output isn't correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 2 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 Incorrect 144 ms 20504 KB Output isn't correct
12 Incorrect 121 ms 19956 KB Output isn't correct
13 Incorrect 113 ms 13520 KB Output isn't correct
14 Correct 163 ms 20208 KB Output is correct
15 Correct 203 ms 23284 KB Output is correct
16 Correct 225 ms 21848 KB Output is correct
17 Incorrect 171 ms 23120 KB Output isn't correct
18 Incorrect 193 ms 23288 KB Output isn't correct
19 Incorrect 210 ms 23128 KB Output isn't correct
20 Incorrect 221 ms 23244 KB Output isn't correct