Submission #1051406

#	Time	Username	Problem	Language	Result	Execution time	Memory
1051406		Requiem	Žarulje (COI15_zarulje)	C++17	100 / 100	242 ms	43092 KiB

zarulje

#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#define MOD 1000000007
#define inf 1e18
#define fi first
#define se second
#define endl "\n"
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define sz(a) ((int)(a).size())
#define pi 3.14159265359
#define TASKNAME "zarulje"
template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
using namespace std;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;

/**
 * Cho mảng n phần tử tượng trưng cho n bóng đèn (tất cả đều bật) và q truy vấn,
 *
 * Giả sử ta xuất phát từ vị trí i, ta lần lượt xóa 2 bóng đèn ở 2 bên cho đến khi không còn bóng
 * đèn nào:
 * Gọi i là thằng gần nhất bên trái còn bật
 *     j là thằng gần nhất bên phải còn bật
 * Nếu không có j thì tắt i.
 *     không có i thì tắt j.
 * Nếu a[i] < a[j] thì tắt thằng j
 *     a[i] > a[j] thì tắt thằng i
 *     a[i] = a[j] thì tắt thằng nào cx được --> có nhiều kế hoạch
 * Đếm số kế hoạch có thể nếu ta xuất phát từ vị trí i.
 * subtask 0: N <= 20, Q <= 20.
 * subtask1: N <= 2000, Q <= 2000 (22)
 * VỚi 1 truy vấn, ta cần giải trong O(N).
 * Giả sử ta giải cho thằng i. thì liệu ta có cần phải bắt đầu lại từ đầu.
 *
 * Với 1 thằng thì đầu tiên là mình có cái thuật dp[l][r] số lượng kịch bản khi trong đoạn [l, r]
 * Mọi thứ trong random quá nhỉ.
 * Một thằng bị xóa khi nào.
 *
 * Nói chung là giải trong O(N^2). gọi dp[l][r] là kết quả của đoạn [l, r] thì kq của
 * ta nằm ở dp[l][l]
 *
 * subtask2: N <= 1e5, k <= 5 (38).
 *
 * Từ 1 vị trí, thì có 1 số đoạn sẽ là tuyến tính (tức là chỉ có 1 lối đi), ngược
 * lại sẽ có những chỗ mà ta phải nhân đôi.
 *
 * Bây giờ ta cần biết những thông tin gì tại một vị trí. Ta cần biết [l, r] để coi sẽ xóa
 * thằng nào tiếp theo. Thực ra thì [l, r] không phải vấn đề nhưng mà khi gặp 2 thằng giống nhau
 * thì nó sẽ tách thành 2 bài toán con và có thể gây ra độ phức tạp O(N^2). Tức là những đoạn mà
 * mình quan ngại là những đoạn chứa mà 2 thằng 2 bên bằng nhau.
 *
 * Giả sử ta đang xét đoạn [l, r] mà có a[l] = a[r] thì lúc này nếu tồn tại 1 số a[x] < a[l] và
 * khác điểm xuất phát thì ta không cần quan tâm cặp (l, r) này ra sao vì nó sẽ không thể nhân đôi
 * được. Tại sao.
 * Giả sử có a[x] thì nó sẽ chỉ thể bị xóa bởi 1 số a[y] khác nhỏ hơn nó và a[y] sẽ xóa được cái
 * thằng biên giới.
 *
 * Nếu như có 1 đoạn [l, r] chứa vị trí i thì ta có thể nhảy nhanh đến đoạn đó.
 *
 * Bây giờ ta cần 1 thuật khởi tạo O(N) mà giải quyết nhanh bài này được.
 *
 * Mình cần thoát ra khỏi tư duy tuần tự nếu muốn giải nhanh bài này.
 *
 * Xét vị trí i, ta gọi lb[i] và rb[i] là vị trí biên trái và biên phải của đoạn mà vị trí i
 * làm min.
 * Nếu i xuất phát từ bên trái
 *
 * Rời khỏi thuật dp ban đầu
 * Nhận xét của ta: Gọi X là vị trí xuất phát, Gọi i và i + 1 là 2 vị trí nằm bên phải vị trí i.
 * Nếu Ai < Ai + 1 thì ta chắc chắn là bóng đèn i + 1 sẽ bị tắt ngay sau bóng đèn i. Nên ta
 * Tương tự với 1 vị trí bên trái ==> Ta đưa về các vị trí quan trọng sao cho
 * A1 <= A2 <= A3 <= X > A4 >= A5 >= A6 với X là vị trí ta chọn.
 * Bây giờ ta sẽ xóa các số này theo 1 thứ tự nhất định từ lớn đến nhỏ.
 *
 * Giả sử ta có AAAXA thì ta sẽ có bao nhiêu cách xóa. (L + R) thằng A chọn ra L thằng A. xóa cho
 * đến khi 1 bên không còn A thì ta sẽ không quan tâm thằng này nữa.
 *
 * Lúc này ta sẽ tính tích tổ hợp của tất cả các thằng i.
 *
 * subtask3: N <= 1e5, Q <= 1e5. (40)
 * Bây giờ ta cần tối ưu subtask 2.
 Trong subtask 2: để giải cho 1 truy vấn thì ta cần
 làm gì.
 Tìm dãy tăng và dãy giảm xuất phát từ vị trí i.
 Sau đó tính tích tổ hợp.

 Có thể thấy rằng đây là bài query chuyển trạng thái.
 Từ vị trí i lên vị trí i + 1 thì ta có thể dùng stack để tính cái dãy giảm dần kia.
 Nhưng với thằng bên phải thì nó sẽ là 1 thao tác bỏ phần tử.

 Với những thằng bên trái thì nó sẽ tồn tại trong 1 đoạn nào đó trên stack
 --> Ta có thể dùng sweepline từ phải sang để thêm nó vào.

 Khi duyệt từ phải sang, ta kết hợp dùng stack, mỗi lần, ta sẽ cập nhật trên cây segment tree.
 Segment tree này dùng để tính tích của các phần tử.
 */
const int MAXN = 3e5 + 9;

int n, q;
int Query[MAXN], a[MAXN];

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 (a % MOD) * (b % MOD) % MOD;
}

int fact[MAXN], ifact[MAXN];

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;
}

void prep(int n){
    fact[0] = 1;
    for(int i = 1; i <= n; i++){
        fact[i] = mul(fact[i - 1], i);
    }
    ifact[n] = binpow(fact[n], MOD - 2);

    for(int i = n; i >= 1; i--){
        ifact[i - 1] = mul(ifact[i], i);
    }
}

int C(int n, int k){
    return mul(fact[n], mul(ifact[k], ifact[n - k]));
}
namespace subtask1{
    bool check(){
        return n <= 2000 and q <= 2000;
    }

    int dp[2002][2002];

    void solve(){
        dp[1][n] = 1;
        a[0] = -inf;
        a[n + 1] = -inf;
        for(int len = n - 1; len >= 1; len--){
            for(int i = 1, j = i + len - 1; j <= n; j++, i++){
                if (a[i - 1] >= a[j + 1]) add(dp[i][j], dp[i - 1][j]);
                if (a[i - 1] <= a[j + 1]) add(dp[i][j], dp[i][j + 1]);
            }
        }

        for(int i = 1; i <= q; i++){
            cout << dp[Query[i]][Query[i]] << endl;
        }
    }
}

namespace subtask2{
    bool check(){
        return n <= 2e5 and q <= 5;
    }

    int cnt[200005], cntLeft[200005];
    int oneQuery(int p){
        vector<int> stk;
        memset(cnt, 0, sizeof(cnt));
        memset(cntLeft, 0, sizeof(cntLeft));
        for(int i = p + 1; i <= n; i++){
            if (stk.empty()) stk.pb(i);
            else if (a[i] <= a[stk.back()]){
                stk.pb(i);
            }
        }

        for(auto x: stk){  cnt[a[x]]++;  }

        stk.clear();
        for(int i = p - 1; i >= 1; i--){
            if (stk.empty()) stk.pb(i);
            else if (a[i] <= a[stk.back()]){
                stk.pb(i);
            }
        }

        for(auto x: stk){
            cnt[a[x]]++;
            cntLeft[a[x]]++;
        }
        int ans = 1;

        for(int i = 1; i <= 200000; i++){
            ans = mul(ans, C(cnt[i], cntLeft[i]));
//            if (cnt[i] > 0) printf("%d %d %d %d\n",i, cnt[i], cntLeft[i], C(cnt[i], cntLeft[i]));
        }
        return ans;
    }
    void solve(){
        prep(200000);
        for(int i = 1; i <= q; i++){
            cout << oneQuery(Query[i]) << endl;
        }
    }
}

struct ITnode{
    int prod = 1;
    int cntLeft = 0;
    int cnt = 0;
} IT[MAXN << 2];

void updatePos(int node, int l, int r, int pos, int mode, int delta){  //delta: cntLeft / cnt / (cntLeft + cnt)
    if (l == r){
        if (mode == 0) IT[node].cntLeft += delta;
        if (mode == 1) IT[node].cnt += delta;
        if (mode == 2) IT[node].cntLeft += delta, IT[node].cnt += delta;
        IT[node].prod = C(IT[node].cnt, IT[node].cntLeft);
//        cout << l << ' ' << IT[node].cntLeft << ' ' << IT[node].cnt << ' ' << IT[node].prod << endl;

        return;
    }
    else{
        int mid = (l + r) >> 1;
        if (pos <= mid) updatePos(node << 1, l, mid, pos, mode, delta);
        else updatePos(node << 1 | 1, mid + 1, r, pos, mode, delta);
        IT[node].prod = mul(IT[node << 1].prod, IT[node << 1 | 1].prod);
    }
}

int getProd(){
    return IT[1].prod;
}

namespace subtask3{
    bool check(){
         return true;
    }

    vector<ii> event[MAXN];
    int answer[MAXN];

    void solve(){
         prep(200000);
         vector<int> stk;
         for(int i = 1; i < n - 1; i++){
             if (stk.empty()) stk.pb(i);
             else{
                 while(!stk.empty() and a[stk.back()] > a[i]){
                     event[i - 1].pb({a[stk.back()], 1});
                     event[stk.back() - 1].pb({a[stk.back()], -1});
//                     cout << "RANGE1 " << a[stk.back()] << ' ' << stk.back() - 1 << ' ' << i - 1 << endl;
                     stk.pop_back();
                 }

                 stk.pb(i);
             }
         }

         while(!stk.empty()){
              int x = stk.back();
              stk.pop_back();
              event[n - 2].pb({a[x], 1});
              event[x - 1].pb({a[x], -1});
//              cout << "RANGE2 " << a[x] << ' ' << x - 1 << ' ' << n - 2 << endl;
         }

         answer[1] = answer[n] = 1;

         for(int pivot = n - 1; pivot >= 2; pivot--){
             int leftLine = pivot - 1;
             for(auto p: event[leftLine]){
//                 cout << "ADD: " << p.fi << ' ' << p.se << endl;
                 updatePos(1, 1, (int) 2e5, p.fi, 2, p.se);
             }

             if (stk.empty()) {
                 stk.pb(pivot + 1);
                 updatePos(1, 1, (int) 2e5, a[pivot + 1], 1, 1);
             }

             else{
                 while(!stk.empty() and a[pivot + 1] < a[stk.back()]) {
//                       cout << "DEL STACK: " << endl;
                       updatePos(1, 1, (int) 2e5, a[stk.back()], 1, -1);
                       stk.pop_back();
                 }
                 stk.pb(pivot + 1);
                 updatePos(1, 1, (int) 2e5, a[pivot + 1], 1, 1);
             }

             answer[pivot] = getProd();
         }

         for(int i = 1; i <= q; i++){
             cout << answer[Query[i]] << endl;
         }
//         cout <<endl;
    }
}
main()
{
    fast;
   if (fopen(TASKNAME".inp","r")){
        freopen(TASKNAME".inp","r",stdin);
        freopen(TASKNAME".out","w",stdout);
   }
   cin >> n >> q;
   for(int i = 1; i <= n; i++){
       cin >> a[i];
   }
   for(int i = 1; i <= q; i++){
       cin >> Query[i];
   }

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

   if (subtask3::check()) return subtask3::solve(), 0;
}
/**
Warning:
- MLE / TLE?
- Gioi han mang?
- Gia tri max phai luon gan cho -INF
- long long co can thiet khong?
- tran mang.
- code can than hon
**/

Compilation message (stderr)

zarulje.cpp:313:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  313 | main()
      | ^~~~
zarulje.cpp: In function 'int main()':
zarulje.cpp:317:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  317 |         freopen(TASKNAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
zarulje.cpp:318:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  318 |         freopen(TASKNAME".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 22 / 22
• Subtask 2: 38 / 38
• Subtask 3: 40 / 40