| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 362395 |
2021-02-02T23:56:31 Z |
vkgainz |
Zoltan (COCI16_zoltan) |
C++17 |
|
743 ms |
44656 KB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int MX = 2e5 + 5;
ll mod = 1000000007;
int segDown[2*MX];
int segUp[2*MX];
ll numDown[2*MX];
ll numUp[2*MX];
int dpDown[MX], dpUp[MX];
ll dpNumDown[MX], dpNumUp[MX];
int n;
void upd(int i, int v, bool b) {
i+=n;
if(b) segUp[i] = v;
else segDown[i] = v;
while(i>1) {
i/=2;
if(b) segUp[i] = max(segUp[2*i], segUp[2*i+1]);
else segDown[i] = max(segDown[2*i], segDown[2*i+1]);
}
}
int query(int l, int r, bool b) {
l+=n, r+=n;
int ans = 0;
while(l<r) {
if(l%2) {
if(b) ans = max(ans, segUp[l++]);
else ans = max(ans, segDown[l++]);
}
if(r%2) {
if(b) ans = max(ans, segUp[--r]);
else ans = max(ans, segDown[--r]);
}
l/=2, r/=2;
}
return ans;
}
void updNum(int i, ll v, bool b) {
i+=n;
if(b) numUp[i] += v, numUp[i]%=mod;
else numDown[i] += v, numDown[i]%=mod;
while(i>1) {
i/=2;
if(b) numUp[i] = numUp[2*i] + numUp[2*i+1], numUp[i]%=mod;
else numDown[i] = numDown[2*i] + numDown[2*i+1], numDown[i]%=mod;
}
}
ll queryNum(int l, int r, bool b) {
l+=n, r+=n;
ll ans = 0;
while(l<r) {
if(l%2) {
if(b) ans += numUp[l++];
else ans += numDown[l++];
}
if(r%2) {
if(b) ans += numUp[--r];
else ans += numDown[--r];
}
ans%=mod, l/=2, r/=2;
}
return ans;
}
void compress(vector<int> &a) {
set<int> s;
for(int i=0;i<n;i++) s.insert(a[i]);
map<int,int> m;
int v = 0;
for(auto &it : s) {
m[it] = v++;
}
for(int i=0;i<n;i++) a[i] = m[a[i]];
s.clear();
m.clear();
}
int main() {
cin >> n;
vector<int> a(n);
for(int i=0;i<n;i++) cin >> a[i];
compress(a);
vector<int> upIn[n+1], downIn[n+1];
for(int i=n-1;i>=0;i--) {
int x = query(a[i]+1, n, 1) + 1;
int y = query(0, a[i], 0) + 1;
dpUp[i] = x, dpDown[i] = y;
upd(a[i], dpUp[i], 1);
upd(a[i], dpDown[i], 0);
upIn[dpUp[i]].push_back(i);
downIn[dpDown[i]].push_back(i);
}
for(int i=1;i<=n;i++) {
int r = 0;
for(int x : upIn[i]) {
while(r < upIn[i-1].size() && upIn[i-1][r] <= x) {
updNum(a[upIn[i-1][r]], -dpNumUp[upIn[i-1][r]], 1);
++r;
}
if(dpUp[x] == 1) dpNumUp[x] = 1LL;
else {
dpNumUp[x] = queryNum(a[x] + 1, n, 1);
}
}
while(r < upIn[i-1].size()) {
updNum(a[upIn[i-1][r]], -dpNumUp[upIn[i-1][r]], 1);
++r;
}
for(int x : upIn[i]) {
updNum(a[x], dpNumUp[x], 1);
}
}
for(int i=1;i<=n;i++) {
int r = 0;
for(int x : downIn[i]) {
while(r < downIn[i-1].size() && downIn[i-1][r] <= x) {
updNum(a[downIn[i-1][r]], -dpNumDown[downIn[i-1][r]], 0);
++r;
}
if(dpDown[x] == 1) dpNumDown[x] = 1LL;
else {
dpNumDown[x] = queryNum(0, a[x], 0);
}
}
while(r < downIn[i-1].size()) {
updNum(a[downIn[i-1][r]], -dpNumDown[downIn[i-1][r]], 0);
++r;
}
for(int x : downIn[i]) {
updNum(a[x], dpNumDown[x], 0);
}
}
int mx = 0;
ll ans = 0LL;
for(int i=0;i<n;i++) {
if(dpDown[i] + dpUp[i] - 1 > mx) {
mx = dpDown[i] + dpUp[i] - 1;
ans = (dpNumDown[i]*1LL*dpNumUp[i])%mod;
}
else if(dpDown[i] + dpUp[i] - 1 == mx) {
ans += (dpNumDown[i]*1LL*dpNumUp[i])%mod;
}
}
ll x = 1LL;
for(int i=0;i<n-mx;i++) x *= 2, x%=mod;
ans*=x;
ans%=mod;
if(ans<0) ans+=mod;
cout << mx << " " << ans << "\n";
}
Compilation message
zoltan.cpp: In function 'int main()':
zoltan.cpp:95:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
95 | while(r < upIn[i-1].size() && upIn[i-1][r] <= x) {
| ~~^~~~~~~~~~~~~~~~~~
zoltan.cpp:104:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
104 | while(r < upIn[i-1].size()) {
| ~~^~~~~~~~~~~~~~~~~~
zoltan.cpp:115:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
115 | while(r < downIn[i-1].size() && downIn[i-1][r] <= x) {
| ~~^~~~~~~~~~~~~~~~~~~~
zoltan.cpp:124:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
124 | while(r < downIn[i-1].size()) {
| ~~^~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 3 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 4 |
Correct |
1 ms |
384 KB |
Output is correct |
| 5 |
Correct |
1 ms |
364 KB |
Output is correct |
| 6 |
Correct |
1 ms |
384 KB |
Output is correct |
| 7 |
Incorrect |
2 ms |
632 KB |
Output isn't correct |
| 8 |
Incorrect |
2 ms |
620 KB |
Output isn't correct |
| 9 |
Incorrect |
2 ms |
620 KB |
Output isn't correct |
| 10 |
Incorrect |
2 ms |
620 KB |
Output isn't correct |
| 11 |
Runtime error |
392 ms |
35668 KB |
Memory limit exceeded |
| 12 |
Incorrect |
319 ms |
30956 KB |
Output isn't correct |
| 13 |
Incorrect |
299 ms |
29292 KB |
Output isn't correct |
| 14 |
Incorrect |
455 ms |
31468 KB |
Output isn't correct |
| 15 |
Runtime error |
588 ms |
38784 KB |
Memory limit exceeded |
| 16 |
Runtime error |
743 ms |
44656 KB |
Memory limit exceeded |
| 17 |
Runtime error |
499 ms |
40300 KB |
Memory limit exceeded |
| 18 |
Runtime error |
493 ms |
40300 KB |
Memory limit exceeded |
| 19 |
Runtime error |
502 ms |
40400 KB |
Memory limit exceeded |
| 20 |
Runtime error |
505 ms |
40428 KB |
Memory limit exceeded |
