Submission #1051314

#	Time	Username	Problem	Language	Result	Execution time	Memory
1051314		Requiem	Žarulje (COI15_zarulje)	C++17	60 / 100	22 ms	23192 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.
 *
 * subtask3: N <= 1e5, Q <= 1e5. (40)
 */
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;
        }
    }
}
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;
}
/**
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:197:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  197 | main()
      | ^~~~
zarulje.cpp: In function 'int main()':
zarulje.cpp:201:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  201 |         freopen(TASKNAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
zarulje.cpp:202:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  202 |         freopen(TASKNAME".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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