#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define fi first
#define se second
#define mp make_pair
#define eb emplace_back
#define ALL(x) (x).begin(), (x).end()
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define FORU(i, a, b) for(int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for(int i = (a); i >= (b); --i)
#define IOS cin.tie(0)->sync_with_stdio(false);
#define PROB "COCI16_zoltan"
void Fi(){
if(fopen(PROB".inp", "r")){
freopen(PROB".inp", "r", stdin);
freopen(PROB".out", "w", stdout);
}
}
const int N = 2e5 + 1;
const int MOD = 1e9 + 7;
int a[N], n;
vector<int> X;
using pi = pair<int, int>;
pi comb(const pi &a, const pi &b){
return a.fi == b.fi ? mp(a.fi, (a.se + b.se) % MOD)
: (a.fi > b.fi) ? a : b;
}
pi bitU[N], bitD[N];
void updateU(int i, const pi &v){
while(1 <= i){
bitU[i] = comb(bitU[i], v);
i -= i & -i;
}
}
pi getU(int i){
pi ans = {0, 0};
while(i <= X.size()){
ans = comb(ans, bitU[i]);
i += i & -i;
}
return ans;
}
void updateD(int i, const pi &v){
while(i <= X.size()){
bitD[i] = comb(v, bitD[i]);
i += i & -i;
}
}
pi getD(int i){
pi ans = {0, 0};
while(1 <= i){
ans = comb(bitD[i], ans);
i -= i & -i;
}
return ans;
}
void update(int i, const pi &v){
updateU(i, v);
updateD(i, v);
}
int main(){
IOS;
Fi();
cin >> n;
X.eb(0);
FORU(i, 1, n){
cin >> a[i];
X.eb(a[i]);
}
X.eb(1e9 + 1);
sort(ALL(X));
X.resize(unique(ALL(X)) - X.begin());
update(1, {0, 1});
update(X.size(), {0, 1});
pi ans = {0, 0};
FORU(i, 1, n){
a[i] = lower_bound(ALL(X), a[i]) - X.begin() + 1;
pi lef = getU(a[i] + 1); lef.fi += 1;
pi rig = getD(a[i] - 1); rig.fi += 1;
ans = comb(ans, comb(lef, rig));
if(i == 1) lef.se -= 1;
update(a[i], comb(lef, rig));
}
cout << ans.fi << " " << ans.se;
return 0;
}
Compilation message
zoltan.cpp: In function 'pi getU(int)':
zoltan.cpp:45:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
45 | while(i <= X.size()){
| ~~^~~~~~~~~~~
zoltan.cpp: In function 'void updateD(int, const pi&)':
zoltan.cpp:53:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | while(i <= X.size()){
| ~~^~~~~~~~~~~
zoltan.cpp: In function 'void Fi()':
zoltan.cpp:20:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
20 | freopen(PROB".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
zoltan.cpp:21:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
21 | freopen(PROB".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
332 KB |
Output isn't correct |
| 2 |
Incorrect |
0 ms |
328 KB |
Output isn't correct |
| 3 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 4 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 5 |
Correct |
1 ms |
332 KB |
Output is correct |
| 6 |
Incorrect |
0 ms |
332 KB |
Output isn't correct |
| 7 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 8 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 9 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 10 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 11 |
Incorrect |
53 ms |
5316 KB |
Output isn't correct |
| 12 |
Incorrect |
47 ms |
4648 KB |
Output isn't correct |
| 13 |
Incorrect |
43 ms |
4416 KB |
Output isn't correct |
| 14 |
Incorrect |
64 ms |
4920 KB |
Output isn't correct |
| 15 |
Incorrect |
80 ms |
6128 KB |
Output isn't correct |
| 16 |
Incorrect |
97 ms |
7128 KB |
Output isn't correct |
| 17 |
Incorrect |
69 ms |
5836 KB |
Output isn't correct |
| 18 |
Incorrect |
80 ms |
5828 KB |
Output isn't correct |
| 19 |
Incorrect |
69 ms |
5844 KB |
Output isn't correct |
| 20 |
Incorrect |
76 ms |
5776 KB |
Output isn't correct |
