| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1086830 |
2024-09-11T14:38:15 Z |
Requiem |
Zoltan (COCI16_zoltan) |
C++17 |
|
404 ms |
29024 KB |
#include<bits/stdc++.h>
//#define int long long
#define fi first
#define se second
#define ii pair<int, int>
#define iii pair<int, ii>
#define pb push_back
#define fast ios_base::sync_with_stdio(NULL), cin.tie(NULL), cout.tie(NULL)
#define TASKNAME "zoltan"
#define MOD 1000000007
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define FORD(i, a, b) for(int i = a; i >= b; i--)
using namespace std;
template<typename T> bool maximize(T &a, T b){ if (a < b) { a = b; return true; } return false; }
template<typename T> bool minimize(T &a, T b){ if (a > b) { a = b; return true; } return false; }
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 (1LL * a * b) % MOD;
}
/**
cho 1 dãy n số a1, a2, ..., an.
Với 1 thao tác thứ i, ta có thể thêm số ai vào đầu hoặc cuối dãy.
Giả sử dãy con tăng dài nhất mà ta xếp được là M thì ta muốn biết số lượng
dãy con tăng dài nhất độ dài M.
Bây giờ ta có cách nào để tìm dãy con tăng dài nhất.
Giả sử thay vì ta phải thêm điểm thì ta có thể trực tiếp thêm vào điểm
(i, a[i]) và (-i, a[i]).
==> M = dãy con dài nhất sao cho xi > x(i - 1) và yi > y(i - 1).
Liệu nó có đúng là như vậy không.
Bài toán đưa về đếm số lượng dãy con tăng dài nhất.
**/
const int MAXN = 2e5 + 9;
int a[MAXN], n;
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;
}
namespace subtask1{
bool check(){
return n <= 20;
}
int cnt = 0, mx = 0, dp[21], dpcnt[21];
deque<int> d;
void upd(){
FOR(i, 0, n - 1){
dp[i] = 1;
dpcnt[i] = 1;
FORD(j, i - 1, 0){
if (d[i] > d[j]){
if (maximize(dp[i], dp[j] + 1)){
dpcnt[i] = dpcnt[j];
}
else if (dp[i] == dp[j] + 1){
add(dpcnt[i], dpcnt[j]);
}
}
}
if (maximize(mx, dp[i])){
cnt = dpcnt[i];
}
else if (mx == dp[i]){
add(cnt, dpcnt[i]);
}
// printf("CUR %lld %lld %lld %lld\n", dp[i], dpcnt[i], cnt, mx);
}
}
void backtrack(int pos){
if (pos == n + 1){
upd();
return;
}
d.push_front(a[pos]);
backtrack(pos + 1);
d.pop_front();
if (pos != 1){
d.push_back(a[pos]);
backtrack(pos + 1);
d.pop_back();
}
}
void solve(){
backtrack(1);
printf("%d %d\n", mx, cnt);
}
}
namespace subtask2{
bool check(){
return n <= 1000;
}
int dp[5001], dpcnt[5001], mx = 0, cnt = 0;
bool mark[5001];
map<int, int> mp;
deque<int> d;
void solve(){
FOR(i, 1, n){
d.pb(a[i]);
if (i != 1) d.push_front(a[i]);
}
// for(int v: d){
// printf("%lld \n", v);
// }
FOR(i, 0, (int) d.size() - 1){
dp[i] = 1;
dpcnt[i] = 1;
FORD(j, i, 0){
if (d[i] > d[j] and (j >= n - 1 or j <= 2 * n - 2 - i) ){
if (maximize(dp[i], dp[j] + 1)){
dpcnt[i] = dpcnt[j];
}
else if (dp[i] == dp[j] + 1){
add(dpcnt[i], dpcnt[j]);
}
}
}
if (dp[i] > mx) {
mx = dp[i];
if (i >= n - 1) cnt = mul(binpow(2, n - mx), dpcnt[i]);
}
else if (mx == dp[i]){
if (i >= n - 1) add(cnt, mul(binpow(2, n - mx), dpcnt[i]));
}
}
// printf("\n");
printf("%d %d\n", mx, cnt);
}
}
struct IntervalTree{
struct Node{
int maxRange = -1e9;
int sumRange = 0;
};
vector<Node> st;
int _sz = 0;
IntervalTree(int sz = 0){
_sz = sz;
st.resize(sz * 4 + 9);
}
Node mergeNode(Node &a, Node &b){
Node res;
res.maxRange = max(a.maxRange, b.maxRange);
res.sumRange = a.sumRange;
add(res.sumRange, b.sumRange);
return res;
}
void update(int node, int l, int r, int pos, int val){
if (l == r){
st[node].maxRange = st[node].sumRange = val;
return;
}
int mid = (l + r) >> 1;
if (pos <= mid) update(node << 1, l, mid, pos, val);
else update(node << 1 | 1, mid + 1, r, pos, val);
st[node] = mergeNode(st[node << 1], st[node << 1 | 1]);
}
void getNode(int node, int l, int r, int u, int v, Node &res){
if (l >= u and r <= v){
res = mergeNode(res, st[node]);
return;
}
if (l > v or r < u) return;
int mid = (l + r) >> 1;
getNode(node << 1, l, mid, u, v, res);
getNode(node << 1 | 1, mid + 1, r, u, v, res);
}
void update(int pos, int val){
update(1, 0, _sz, pos, val);
}
int getMax(int u, int v){
if (u > v) return -1e9;
Node r;
getNode(1, 0, _sz, u, v, r);
return r.maxRange;
}
int getRange(int u, int v){
if (u > v) return 0;
Node r;
getNode(1, 0, _sz, u, v, r);
return r.sumRange;
}
};
namespace subtask3{
bool check(){
return true;
}
vector<int> layerDP[MAXN];
vector<int> listVal;
deque<int> d;
int dp[2 * MAXN], dpcnt[2 * MAXN], mx = 0, cnt = 0;
void discretize(){ //roi rac hoa.
FOR(i, 1, n){
listVal.pb(a[i]);
}
sort(listVal.begin(), listVal.end());
listVal.erase(unique(listVal.begin(), listVal.end()), listVal.end());
FOR(i, 1, n){
a[i] = lower_bound(listVal.begin(), listVal.end(), a[i]) - listVal.begin() + 1;
}
}
void build(){
FOR(i, 1, n){
d.push_back(a[i]);
if (i != 1) d.push_front(a[i]);
}
}
void calculateDP(){
IntervalTree opt(n + 9);
FOR(i, 0, (int) d.size() - 1){
dp[i] = max(1, opt.getMax(1, d[i] - 1) + 1);
opt.update(d[i], dp[i]);
layerDP[dp[i]].pb(i);
if (dp[i] == 1) dpcnt[i] = 1;
}
}
void countDP(){
IntervalTree cnt(2 * n + 9);
sort(layerDP[1].begin(), layerDP[1].end(), [&](const int &i1, const int &i2){
return d[i1] < d[i2];
});
FOR(i, 2, n){
sort(layerDP[i].begin(), layerDP[i].end(), [&](const int &i1, const int &i2){
return d[i1] < d[i2];
});
int ptr_i = 0, ptr_i1 = 0;
while(ptr_i < layerDP[i].size() and ptr_i1 < layerDP[i - 1].size()){
int id1 = layerDP[i][ptr_i];
int id2 = layerDP[i - 1][ptr_i1];
if (d[id1] <= d[id2]){
if (id1 <= n - 1){
add(dpcnt[id1], cnt.getRange(0, id1));
}
if (id1 > n - 1) {
add(dpcnt[id1], cnt.getRange(n - 1, id1 - 1));
add(dpcnt[id1], cnt.getRange(0, 2 * n - 2 - id1));
}
ptr_i++;
}
else{
cnt.update(id2, dpcnt[id2]);
ptr_i1++;
}
}
for(;ptr_i < layerDP[i].size(); ptr_i++){
int id1 = layerDP[i][ptr_i];
if (id1 <= n - 1){
add(dpcnt[id1], cnt.getRange(0, id1));
}
if (id1 > n - 1) {
add(dpcnt[id1], cnt.getRange(n - 1, id1 - 1));
add(dpcnt[id1], cnt.getRange(0, 2 * n - 2 - id1));
}
}
for(;ptr_i1 < layerDP[i - 1].size(); ptr_i1++){
int id2 = layerDP[i - 1][ptr_i1];
cnt.update(id2, dpcnt[id2]);
}
for(int v: layerDP[i - 1]){
cnt.update(v, 0);
}
layerDP[i - 1].clear();
layerDP[i - 1].shrink_to_fit();
}
}
void getAns(){
FOR(i, 0, (int)d.size() - 1){
if (maximize(mx, dp[i])){
if (i >= n - 1) cnt = mul(binpow(2, n - mx), dpcnt[i]);
}
else if (mx == dp[i]){
if (i >= n - 1) add(cnt, mul(binpow(2, n - mx), dpcnt[i]));
}
}
}
void solve(){
discretize();
build();
calculateDP();
countDP();
getAns();
printf("%d %d\n", mx, cnt);
}
}
main(){
fast;
if (fopen(TASKNAME".inp", "r")){
freopen(TASKNAME".inp","r",stdin);
freopen(TASKNAME".out","w",stdout);
}
cin >> n;
FOR(i, 1, n){
cin >> a[i];
}
// if (subtask1::check()) return subtask1::solve(), 0;
// if (subtask2::check()) return subtask2::solve(), 0;
if (subtask3::check()) return subtask3::solve(), 0;
}
Compilation message
zoltan.cpp: In function 'void subtask3::countDP()':
zoltan.cpp:273:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
273 | while(ptr_i < layerDP[i].size() and ptr_i1 < layerDP[i - 1].size()){
| ~~~~~~^~~~~~~~~~~~~~~~~~~
zoltan.cpp:273:56: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
273 | while(ptr_i < layerDP[i].size() and ptr_i1 < layerDP[i - 1].size()){
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
zoltan.cpp:293:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
293 | for(;ptr_i < layerDP[i].size(); ptr_i++){
| ~~~~~~^~~~~~~~~~~~~~~~~~~
zoltan.cpp:305:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
305 | for(;ptr_i1 < layerDP[i - 1].size(); ptr_i1++){
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
zoltan.cpp: At global scope:
zoltan.cpp:338:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
338 | main(){
| ^~~~
zoltan.cpp: In function 'int main()':
zoltan.cpp:341:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
341 | freopen(TASKNAME".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
zoltan.cpp:342:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
342 | freopen(TASKNAME".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4956 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 3 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 4 |
Correct |
2 ms |
5188 KB |
Output is correct |
| 5 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 6 |
Correct |
2 ms |
4952 KB |
Output is correct |
| 7 |
Correct |
3 ms |
5208 KB |
Output is correct |
| 8 |
Correct |
4 ms |
5212 KB |
Output is correct |
| 9 |
Correct |
3 ms |
5212 KB |
Output is correct |
| 10 |
Correct |
4 ms |
5212 KB |
Output is correct |
| 11 |
Correct |
243 ms |
24924 KB |
Output is correct |
| 12 |
Correct |
205 ms |
22268 KB |
Output is correct |
| 13 |
Correct |
194 ms |
21244 KB |
Output is correct |
| 14 |
Correct |
265 ms |
20984 KB |
Output is correct |
| 15 |
Correct |
352 ms |
24796 KB |
Output is correct |
| 16 |
Correct |
404 ms |
27928 KB |
Output is correct |
| 17 |
Correct |
313 ms |
29020 KB |
Output is correct |
| 18 |
Correct |
307 ms |
29020 KB |
Output is correct |
| 19 |
Correct |
332 ms |
29024 KB |
Output is correct |
| 20 |
Correct |
303 ms |
29020 KB |
Output is correct |
