Submission #1086830

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086830		Requiem	Zoltan (COCI16_zoltan)	C++17	140 / 140	404 ms	29024 KiB

zoltan

#include<bits/stdc++.h>
//#define int long long
#define fi first
#define se second
#define ii pair<int, int>
#define iii pair<int, ii>
#define pb push_back
#define fast ios_base::sync_with_stdio(NULL), cin.tie(NULL), cout.tie(NULL)
#define TASKNAME "zoltan"
#define MOD 1000000007
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define FORD(i, a, b) for(int i = a; i >= b; i--)

using namespace std;
template<typename T> bool maximize(T &a, T b){  if (a < b) { a = b; return true; } return false; }
template<typename T> bool minimize(T &a, T b){  if (a > b) { a = b; return true; } return false; }
void add(int &a, int b){
    a += b;
    if (a >= MOD) a -= MOD;
}

void sub(int &a, int b){
    a -= b;
    if (a < 0) a += MOD;
}

int mul(int a, int b){
    return (1LL * a * b) % MOD;
}

/**
cho 1 dãy n số a1, a2, ..., an.

Với 1 thao tác thứ i, ta có thể thêm số ai vào đầu hoặc cuối dãy.

Giả sử dãy con tăng dài nhất mà ta xếp được là M thì ta muốn biết số lượng
dãy con tăng dài nhất độ dài M.

Bây giờ ta có cách nào để tìm dãy con tăng dài nhất.

Giả sử thay vì ta phải thêm điểm thì ta có thể trực tiếp thêm vào điểm
(i, a[i]) và (-i, a[i]).

==> M = dãy con dài nhất sao cho xi > x(i - 1) và yi > y(i - 1).

Liệu nó có đúng là như vậy không.
Bài toán đưa về đếm số lượng dãy con tăng dài nhất.
**/

const int MAXN = 2e5 + 9;
int a[MAXN], n;

int binpow(int a, int b){
    int res = 1;
    while(b > 0){
        if (b & 1) res = mul(res, a);
        b >>= 1;
        a = mul(a, a);
    }
    return res;
}

namespace subtask1{
    bool check(){
        return n <= 20;
    }

    int cnt = 0, mx = 0, dp[21], dpcnt[21];
    deque<int> d;

    void upd(){
        FOR(i, 0, n - 1){
            dp[i] = 1;
            dpcnt[i] = 1;
            FORD(j, i - 1, 0){
                if (d[i] > d[j]){
                    if (maximize(dp[i], dp[j] + 1)){
                        dpcnt[i] = dpcnt[j];
                    }
                    else if (dp[i] == dp[j] + 1){
                        add(dpcnt[i], dpcnt[j]);
                    }
                }
            }
            if (maximize(mx, dp[i])){
                cnt = dpcnt[i];
            }
            else if (mx == dp[i]){
                add(cnt, dpcnt[i]);
            }
//            printf("CUR %lld %lld %lld %lld\n", dp[i], dpcnt[i], cnt, mx);
        }

    }
    void backtrack(int pos){
        if (pos == n + 1){
            upd();
            return;
        }

        d.push_front(a[pos]);
        backtrack(pos + 1);
        d.pop_front();

        if (pos != 1){
            d.push_back(a[pos]);
            backtrack(pos + 1);
            d.pop_back();
        }
    }
    void solve(){
        backtrack(1);
        printf("%d %d\n", mx, cnt);
    }
}

namespace subtask2{
    bool check(){
        return n <= 1000;
    }

    int dp[5001], dpcnt[5001], mx = 0, cnt = 0;
    bool mark[5001];
    map<int, int> mp;
    deque<int> d;
    void solve(){
        FOR(i, 1, n){
            d.pb(a[i]);
            if (i != 1) d.push_front(a[i]);
        }
//        for(int v: d){
//            printf("%lld \n", v);
//        }
        FOR(i, 0, (int) d.size() - 1){
            dp[i] = 1;
            dpcnt[i] = 1;
            FORD(j, i, 0){
                if (d[i] > d[j] and (j >= n - 1 or j <= 2 * n - 2 - i) ){
                    if (maximize(dp[i], dp[j] + 1)){
                        dpcnt[i] = dpcnt[j];
                    }
                    else if (dp[i] == dp[j] + 1){
                        add(dpcnt[i], dpcnt[j]);
                    }
                }
            }
            if (dp[i] > mx) {
                mx = dp[i];
                if (i >= n - 1) cnt = mul(binpow(2, n - mx), dpcnt[i]);
            }
            else if (mx == dp[i]){
                if (i >= n - 1) add(cnt, mul(binpow(2, n - mx), dpcnt[i]));
            }

        }
//        printf("\n");
        printf("%d %d\n", mx, cnt);
    }
}

struct IntervalTree{
    struct Node{
        int maxRange = -1e9;
        int sumRange = 0;
    };
    vector<Node> st;
    int _sz = 0;
    IntervalTree(int sz = 0){
        _sz = sz;
        st.resize(sz * 4 + 9);
    }

    Node mergeNode(Node &a, Node &b){
        Node res;
        res.maxRange = max(a.maxRange, b.maxRange);
        res.sumRange = a.sumRange;
        add(res.sumRange, b.sumRange);
        return res;
    }

    void update(int node, int l, int r, int pos, int val){
        if (l == r){
            st[node].maxRange = st[node].sumRange = val;
            return;
        }

        int mid = (l + r) >> 1;
        if (pos <= mid) update(node << 1, l, mid, pos, val);
        else update(node << 1 | 1, mid + 1, r, pos, val);

        st[node] = mergeNode(st[node << 1], st[node << 1 | 1]);
    }

    void getNode(int node, int l, int r, int u, int v, Node &res){
        if (l >= u and r <= v){
            res = mergeNode(res, st[node]);
            return;
        }
        if (l > v or r < u) return;
        int mid = (l + r) >> 1;
        getNode(node << 1, l, mid, u, v, res);
        getNode(node << 1 | 1, mid + 1, r, u, v, res);
    }

    void update(int pos, int val){
        update(1, 0, _sz, pos, val);
    }
    int getMax(int u, int v){
        if (u > v) return -1e9;
        Node r;
        getNode(1, 0, _sz, u, v, r);
        return r.maxRange;
    }

    int getRange(int u, int v){
        if (u > v) return 0;
        Node r;
        getNode(1, 0, _sz, u, v, r);
        return r.sumRange;
    }
};
namespace subtask3{
    bool check(){
        return true;
    }

    vector<int> layerDP[MAXN];
    vector<int> listVal;
    deque<int> d;
    int dp[2 * MAXN], dpcnt[2 * MAXN], mx = 0, cnt = 0;

    void discretize(){ //roi rac hoa.
        FOR(i, 1, n){
            listVal.pb(a[i]);
        }
        sort(listVal.begin(), listVal.end());
        listVal.erase(unique(listVal.begin(), listVal.end()), listVal.end());

        FOR(i, 1, n){
            a[i] = lower_bound(listVal.begin(), listVal.end(), a[i]) - listVal.begin() + 1;
        }
    }

    void build(){
        FOR(i, 1, n){
            d.push_back(a[i]);
            if (i != 1) d.push_front(a[i]);
        }
    }

    void calculateDP(){
        IntervalTree opt(n + 9);
        FOR(i, 0, (int) d.size() - 1){
            dp[i] = max(1, opt.getMax(1, d[i] - 1) + 1);
            opt.update(d[i], dp[i]);

            layerDP[dp[i]].pb(i);
            if (dp[i] == 1) dpcnt[i] = 1;
        }
    }

    void countDP(){
        IntervalTree cnt(2 * n + 9);
        sort(layerDP[1].begin(), layerDP[1].end(), [&](const int &i1, const int &i2){
             return d[i1] < d[i2];
        });
        FOR(i, 2, n){
            sort(layerDP[i].begin(), layerDP[i].end(), [&](const int &i1, const int &i2){
                 return d[i1] < d[i2];
            });

            int ptr_i = 0, ptr_i1 = 0;
            while(ptr_i < layerDP[i].size() and ptr_i1 < layerDP[i - 1].size()){
                int id1 = layerDP[i][ptr_i];
                int id2 = layerDP[i - 1][ptr_i1];

                if (d[id1] <= d[id2]){
                    if (id1 <= n - 1){
                        add(dpcnt[id1], cnt.getRange(0, id1));
                    }
                    if (id1 > n - 1) {
                        add(dpcnt[id1], cnt.getRange(n - 1, id1 - 1));
                        add(dpcnt[id1], cnt.getRange(0, 2 * n - 2 - id1));
                    }
                    ptr_i++;
                }
                else{
                    cnt.update(id2, dpcnt[id2]);
                    ptr_i1++;
                }
            }

            for(;ptr_i < layerDP[i].size(); ptr_i++){
                int id1 = layerDP[i][ptr_i];
                if (id1 <= n - 1){
                    add(dpcnt[id1], cnt.getRange(0, id1));
                }
                if (id1 > n - 1) {
                    add(dpcnt[id1], cnt.getRange(n - 1, id1 - 1));
                    add(dpcnt[id1], cnt.getRange(0, 2 * n - 2 - id1));
                }

            }

            for(;ptr_i1 < layerDP[i - 1].size(); ptr_i1++){
                int id2 = layerDP[i - 1][ptr_i1];
                cnt.update(id2, dpcnt[id2]);
            }
            for(int v: layerDP[i - 1]){
                cnt.update(v, 0);
            }
            layerDP[i - 1].clear();
            layerDP[i - 1].shrink_to_fit();
        }

    }

    void getAns(){
        FOR(i, 0, (int)d.size() - 1){
            if (maximize(mx, dp[i])){
                if (i >= n - 1) cnt = mul(binpow(2, n - mx), dpcnt[i]);
            }
            else if (mx == dp[i]){
                if (i >= n - 1) add(cnt, mul(binpow(2, n - mx), dpcnt[i]));
            }
        }
    }

    void solve(){
        discretize();
        build();
        calculateDP();
        countDP();
        getAns();
        printf("%d %d\n", mx, cnt);
    }
}
main(){
    fast;
    if (fopen(TASKNAME".inp", "r")){
        freopen(TASKNAME".inp","r",stdin);
        freopen(TASKNAME".out","w",stdout);
    }
    cin >> n;
    FOR(i, 1, n){
        cin >> a[i];
    }

//    if (subtask1::check()) return subtask1::solve(), 0;
//    if (subtask2::check()) return subtask2::solve(), 0;
    if (subtask3::check()) return subtask3::solve(), 0;
}

Compilation message (stderr)

zoltan.cpp: In function 'void subtask3::countDP()':
zoltan.cpp:273:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  273 |             while(ptr_i < layerDP[i].size() and ptr_i1 < layerDP[i - 1].size()){
      |                   ~~~~~~^~~~~~~~~~~~~~~~~~~
zoltan.cpp:273:56: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  273 |             while(ptr_i < layerDP[i].size() and ptr_i1 < layerDP[i - 1].size()){
      |                                                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
zoltan.cpp:293:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  293 |             for(;ptr_i < layerDP[i].size(); ptr_i++){
      |                  ~~~~~~^~~~~~~~~~~~~~~~~~~
zoltan.cpp:305:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  305 |             for(;ptr_i1 < layerDP[i - 1].size(); ptr_i1++){
      |                  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
zoltan.cpp: At global scope:
zoltan.cpp:338:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  338 | main(){
      | ^~~~
zoltan.cpp: In function 'int main()':
zoltan.cpp:341:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  341 |         freopen(TASKNAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
zoltan.cpp:342:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  342 |         freopen(TASKNAME".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 140 / 140