| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1051406 |
2024-08-10T06:07:12 Z |
Requiem |
Žarulje (COI15_zarulje) |
C++17 |
|
242 ms |
43092 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.
* 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
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);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
18776 KB |
Output is correct |
| 2 |
Correct |
5 ms |
19032 KB |
Output is correct |
| 3 |
Correct |
6 ms |
19036 KB |
Output is correct |
| 4 |
Correct |
6 ms |
19032 KB |
Output is correct |
| 5 |
Correct |
6 ms |
19036 KB |
Output is correct |
| 6 |
Correct |
6 ms |
19288 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
95 ms |
24892 KB |
Output is correct |
| 2 |
Correct |
183 ms |
29900 KB |
Output is correct |
| 3 |
Correct |
179 ms |
29816 KB |
Output is correct |
| 4 |
Correct |
183 ms |
29780 KB |
Output is correct |
| 5 |
Correct |
191 ms |
30544 KB |
Output is correct |
| 6 |
Correct |
206 ms |
35924 KB |
Output is correct |
| 7 |
Correct |
223 ms |
42064 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
18776 KB |
Output is correct |
| 2 |
Correct |
5 ms |
19032 KB |
Output is correct |
| 3 |
Correct |
6 ms |
19036 KB |
Output is correct |
| 4 |
Correct |
6 ms |
19032 KB |
Output is correct |
| 5 |
Correct |
6 ms |
19036 KB |
Output is correct |
| 6 |
Correct |
6 ms |
19288 KB |
Output is correct |
| 7 |
Correct |
95 ms |
24892 KB |
Output is correct |
| 8 |
Correct |
183 ms |
29900 KB |
Output is correct |
| 9 |
Correct |
179 ms |
29816 KB |
Output is correct |
| 10 |
Correct |
183 ms |
29780 KB |
Output is correct |
| 11 |
Correct |
191 ms |
30544 KB |
Output is correct |
| 12 |
Correct |
206 ms |
35924 KB |
Output is correct |
| 13 |
Correct |
223 ms |
42064 KB |
Output is correct |
| 14 |
Correct |
14 ms |
19544 KB |
Output is correct |
| 15 |
Correct |
102 ms |
25628 KB |
Output is correct |
| 16 |
Correct |
183 ms |
32456 KB |
Output is correct |
| 17 |
Correct |
197 ms |
30860 KB |
Output is correct |
| 18 |
Correct |
227 ms |
32340 KB |
Output is correct |
| 19 |
Correct |
201 ms |
31056 KB |
Output is correct |
| 20 |
Correct |
220 ms |
36944 KB |
Output is correct |
| 21 |
Correct |
242 ms |
43092 KB |
Output is correct |
