Submission #525294

#	Time	Username	Problem	Language	Result	Execution time	Memory
525294		Killer2501	Zoltan (COCI16_zoltan)	C++14	21 / 140	113 ms	14516 KiB

zoltan

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define ull unsigned long long
#define pb push_back
#define pll pair<ll, int>
#define pii pair<int, int>
#define fi first
#define se second
using namespace std;
const int N = 2e5+5;
const int M = 14;
const ll inf = 1e9;
const int base = 350;
const ll mod = 1e9+7;
int n, t, m, k, q, c[N], a[N], b[N];
ll ans, tong, d[N];
vector<int> vi, adj[N], gr[N];
mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count());
string s;
void add(int& x, int y)
{
    x += y;
    if(x >= mod)x -= mod;
    if(x < 0)x += mod;
}
struct BIT
{
    int n;
    vector<pii> fe;
    BIT(int _n)
    {
        n = _n;
        fe.resize(n+1, {0, 0});
    }
    pii merga(pii x, pii y)
    {
        if(x.fi == y.fi)return {x.fi, (1ll*x.se+y.se)%mod};
        return max(x, y);
    }
    void add(int id, pii x)
    {
        for(; id <= n; id += id & -id)fe[id] = merga(fe[id], x);
    }
    pii get(int id)
    {
        pii res;
        res.fi = 0;
        res.se = 0;
        for(; id; id -= id & -id)res = merga(res, fe[id]);
        return res;
    }
};
void sol()
{
    cin >> n;
    for(int i = 1; i <= n; i ++)
    {
        cin >> a[i];
        vi.pb(a[i]);
    }
    sort(vi.begin(), vi.end());
    vi.erase(unique(vi.begin(), vi.end()), vi.end());
    m = vi.size();
    BIT inc(m), dec(m);
    for(int i = n; i > 0; i --)
    {
        a[i] = lower_bound(vi.begin(), vi.end(), a[i]) - vi.begin() + 1;
        pii cur = inc.get(m-a[i]);
        cur.fi += 1;
        if(cur.fi == 1)cur.se = 1;
        //cout << cur.fi <<" "<<cur.se<<'\n';
        inc.fe[m-a[i]+1] = cur;
        inc.add(m-a[i]+2, cur);
        cur = dec.get(a[i]-1);
        cur.fi += 1;
        if(cur.fi == 1)cur.se = 1;
        //cout << cur.fi <<" "<<cur.se<<'\n';
        dec.fe[a[i]] = cur;
        dec.add(a[i]+1, cur);
        pii l = dec.get(a[i]), r = inc.get(m-a[i]+1);
        if(l.fi+r.fi-1 > ans)
        {
            ans = l.fi+r.fi-1;
            tong = 1ll * l.se * r.se % mod;
        }
        else if(l.fi+r.fi-1 == ans)
        {
            tong = (tong + 1ll * l.se * r.se % mod) % mod;
        }
        //cout << l.fi <<" "<<l.se <<" "<<r.fi <<" "<<r.se<<'\n';
    }
    for(int i = 1; i <= n-ans; i ++)tong = tong * 2 % mod;
    cout << ans <<" "<<tong;

}
int main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    #define task "test"
    if(fopen(task".inp", "r"))
	{
		freopen(task".inp", "r", stdin);
		freopen(task".out", "w", stdout);
    }
    int ntest = 1;
    //cin >> ntest;
    while(ntest -- > 0)
    sol();
    return 0;
}
/*
    2 2
  4 2 2 3 5
6 4 2 1 3 5 7
*/

Compilation message (stderr)

zoltan.cpp: In function 'int main()':
zoltan.cpp:105:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |   freopen(task".inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
zoltan.cpp:106:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |   freopen(task".out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 21 / 140