oj.uz

Submission #1051314

# Submission time Handle Problem Language Result Execution time Memory
1051314 2024-08-10T04:20:58 Z Requiem Žarulje (COI15_zarulje) C++17
60 / 100
 22 ms 23192 KB 
#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

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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3160 KB Output is correct
2 Correct 5 ms 8284 KB Output is correct
3 Correct 17 ms 23132 KB Output is correct
4 Correct 16 ms 23000 KB Output is correct
5 Correct 17 ms 23192 KB Output is correct
6 Correct 16 ms 23132 KB Output is correct

Subtask #2
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 7932 KB Output is correct
2 Correct 20 ms 8932 KB Output is correct
3 Correct 18 ms 8728 KB Output is correct
4 Correct 20 ms 9052 KB Output is correct
5 Correct 20 ms 9280 KB Output is correct
6 Correct 21 ms 9308 KB Output is correct
7 Correct 22 ms 9552 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3160 KB Output is correct
2 Correct 5 ms 8284 KB Output is correct
3 Correct 17 ms 23132 KB Output is correct
4 Correct 16 ms 23000 KB Output is correct
5 Correct 17 ms 23192 KB Output is correct
6 Correct 16 ms 23132 KB Output is correct
7 Correct 15 ms 7932 KB Output is correct
8 Correct 20 ms 8932 KB Output is correct
9 Correct 18 ms 8728 KB Output is correct
10 Correct 20 ms 9052 KB Output is correct
11 Correct 20 ms 9280 KB Output is correct
12 Correct 21 ms 9308 KB Output is correct
13 Correct 22 ms 9552 KB Output is correct
14 Incorrect 1 ms 2648 KB Output isn't correct
15 Halted 0 ms 0 KB -