oj.uz

답안 #525287

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
525287 2022-02-11T09:10:21 Z Killer2501 Zoltan (COCI16_zoltan) C++14
119 / 140
 104 ms 16328 KB 
#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 int 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, (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.add(m-a[i]+1, cur);
        cur = dec.get(a[i]-1);
        cur.fi += 1;
        if(cur.fi == 1)cur.se = 1;
        //cout << cur.fi <<" "<<cur.se<<'\n';
        dec.add(a[i], cur);
    }
    for(int i = 1; i <= m; i ++)
    {
        pii l = dec.get(i), r = inc.get(m-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-(ans == 1); 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

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

Subtask #1
119.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9676 KB Output is correct
2 Correct 6 ms 9712 KB Output is correct
3 Correct 5 ms 9676 KB Output is correct
4 Correct 5 ms 9676 KB Output is correct
5 Correct 5 ms 9676 KB Output is correct
6 Incorrect 6 ms 9676 KB Output isn't correct
7 Correct 5 ms 9724 KB Output is correct
8 Correct 5 ms 9724 KB Output is correct
9 Correct 5 ms 9732 KB Output is correct
10 Correct 6 ms 9700 KB Output is correct
11 Correct 63 ms 14724 KB Output is correct
12 Correct 61 ms 14128 KB Output is correct
13 Correct 51 ms 13820 KB Output is correct
14 Correct 72 ms 14324 KB Output is correct
15 Correct 91 ms 15532 KB Output is correct
16 Correct 104 ms 16328 KB Output is correct
17 Correct 75 ms 15216 KB Output is correct
18 Incorrect 75 ms 15308 KB Output isn't correct
19 Correct 76 ms 15228 KB Output is correct
20 Incorrect 77 ms 15224 KB Output isn't correct