| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1051265 |
2024-08-10T02:36:43 Z |
Requiem |
Žarulje (COI15_zarulje) |
C++17 |
|
22 ms |
27140 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 (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
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);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2908 KB |
Output is correct |
| 2 |
Correct |
5 ms |
10456 KB |
Output is correct |
| 3 |
Correct |
22 ms |
26960 KB |
Output is correct |
| 4 |
Correct |
16 ms |
26968 KB |
Output is correct |
| 5 |
Correct |
17 ms |
27140 KB |
Output is correct |
| 6 |
Correct |
17 ms |
26940 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
4952 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2908 KB |
Output is correct |
| 2 |
Correct |
5 ms |
10456 KB |
Output is correct |
| 3 |
Correct |
22 ms |
26960 KB |
Output is correct |
| 4 |
Correct |
16 ms |
26968 KB |
Output is correct |
| 5 |
Correct |
17 ms |
27140 KB |
Output is correct |
| 6 |
Correct |
17 ms |
26940 KB |
Output is correct |
| 7 |
Incorrect |
4 ms |
4952 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
