oj.uz

Submission #488632

# Submission time Handle Problem Language Result Execution time Memory
488632 2021-11-19T20:01:30 Z Victor Zoltan (COCI16_zoltan) C++17
70 / 140
 537 ms 56832 KB 
#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define per(i, a, b) for (int i = (b - 1); i >= (a); --i)
#define trav(a, x) for (auto &a : x)

#define all(x) x.begin(), x.end()
#define sz(x) x.size()
#define pb push_back
#define debug(x) cout << #x << " = " << x << endl

#define umap unordered_map
#define uset unordered_set

typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;

const int INF = 1'000'000'007;

struct Node {
    Node *l, *r;
    int len = 0, lo, hi;
    ll cnt = 1;
    Node(int L, int R) : lo(L), hi(R) {
        if (hi - lo != 1) {
            int mid = (lo + hi) >> 1;
            l = new Node(lo, mid);
            r = new Node(mid, hi);
        }
    }

    pair<int, ll> query(int L, int R) {
        if (hi <= L || R <= lo) return {0, 1};
        if (L <= lo && hi <= R) return {len, cnt};
        return combine(l->query(L, R), r->query(L, R));
    }

    void update(int pos, int nlen, ll ncnt) {
        if (pos < lo || hi <= pos) return;
        if (hi - lo == 1) {
            tie(len, cnt) = combine({len, cnt}, {nlen, ncnt});
            return;
        }
        l->update(pos,nlen,ncnt); r->update(pos,nlen,ncnt);
        tie(len,cnt)=combine({l->len,l->cnt},{r->len,r->cnt});
    }

    pair<int, ll> combine(pair<int, ll> v1, pair<int, ll> v2) {
        int len1, len2;
        ll cnt1, cnt2;
        tie(len1, cnt1) = v1;
        tie(len2, cnt2) = v2;

        if (len2 < len1) return {len1, cnt1};
        if (len1 < len2) return {len2, cnt2};
        return {len1, (cnt1 + cnt2) % INF};
    }
};

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);

    int ans = 0, arr[200001], n;
    ll cnt = 0;
    set<int> nums;
    umap<int, int> compress;

    cin >> n;
    rep(i, 0, n) cin >> arr[i], nums.insert(arr[i]);
    int pos = 0;
    trav(num, nums) compress[num] = pos++;
    rep(i, 0, n) arr[i] = compress[arr[i]];


    Node lis(0,pos);
    Node lds(0,pos);
    per(i,0,n){
        int num=arr[i];
        int len_lis,len_lds;
        ll cnt_lis,cnt_lds;

        tie(len_lis,cnt_lis)=lis.query(0,num);
        tie(len_lds,cnt_lds)=lds.query(num+1,pos);
        ++len_lis; ++len_lds;
        
        if(len_lis==1)cnt_lis=1;
        if(len_lds==1)cnt_lds=1;

        lis.update(num,len_lis,cnt_lis);
        lds.update(num,len_lds,cnt_lds);


        int cur_len=len_lis+len_lds-1;
        ll cur_cnt=cnt_lis*cnt_lds;

        //cout<<"i = "<<i<<" num = "<<num<<endl;
        //cout<<"cur len = "<<cur_len<<" cur cnt = "<<cur_cnt<<endl;
        //cout<<"len lis = "<<len_lis<<" cnt lis = "<<cnt_lis<<endl;
        //cout<<"len lds = "<<len_lds<<" cnt lds = "<<cnt_lds<<endl;
        //cout<<endl;

        if(cur_len>ans){
            ans=cur_len;
            cnt=0;

        }
        if(cur_len>=ans)cnt=(cnt+cur_cnt)%INF;
    }

    rep(i,0,n-ans)cnt=(cnt<<1)%INF;
    cout<<ans<<' '<<cnt<<endl;
    return 0;
}

Subtask #1
70.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 972 KB Output is correct
2 Correct 1 ms 972 KB Output is correct
3 Correct 0 ms 972 KB Output is correct
4 Correct 1 ms 972 KB Output is correct
5 Correct 1 ms 972 KB Output is correct
6 Correct 1 ms 972 KB Output is correct
7 Correct 1 ms 1356 KB Output is correct
8 Correct 1 ms 1356 KB Output is correct
9 Correct 2 ms 1356 KB Output is correct
10 Correct 2 ms 1356 KB Output is correct
11 Runtime error 243 ms 44468 KB Memory limit exceeded
12 Runtime error 216 ms 38820 KB Memory limit exceeded
13 Runtime error 202 ms 36880 KB Memory limit exceeded
14 Runtime error 331 ms 39056 KB Memory limit exceeded
15 Runtime error 437 ms 47936 KB Memory limit exceeded
16 Runtime error 537 ms 56832 KB Memory limit exceeded
17 Runtime error 272 ms 46984 KB Memory limit exceeded
18 Runtime error 269 ms 46804 KB Memory limit exceeded
19 Runtime error 261 ms 46904 KB Memory limit exceeded
20 Runtime error 275 ms 46964 KB Memory limit exceeded