Submission #1051265

#	Time	Username	Problem	Language	Result	Execution time	Memory
1051265		Requiem	Žarulje (COI15_zarulje)	C++17	22 / 100	22 ms	27140 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 (28)
 * 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 (32).
 * 
 * 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 đoạn 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.
 * 
 * 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;
}
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 <= 1e5 and q <= 5;
    }

    void solve(){

    }
}
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;
} 
/**
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:115:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  115 | main()
      | ^~~~
zarulje.cpp: In function 'int main()':
zarulje.cpp:119:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  119 |         freopen(TASKNAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
zarulje.cpp:120:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  120 |         freopen(TASKNAME".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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