#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;
}
int lz[N * 4];
pi ST[N * 4];
int mul(const int &a, const int &b){
return (1LL * a * b) % MOD;
}
void down(int id){
ST[id * 2].se = mul(ST[id * 2].se, lz[id]);
ST[id * 2 + 1].se = mul(ST[id * 2 + 1].se, lz[id]);
lz[id * 2] = mul(lz[id * 2], lz[id]);
lz[id * 2 + 1] = mul(lz[id * 2 + 1], lz[id]);
lz[id] = 1;
}
void update(const int &i, const pi &v, int id = 1, int be = 1, int en = X.size()){
if(be == en){
ST[id] = comb(ST[id], v);
return;
}
int mi = (be + en) / 2;
if(lz[id] > 1) down(id);
if(i <= mi) update(i, v, id * 2, be, mi);
else update(i, v, id * 2 + 1, mi + 1, en);
ST[id] = comb(ST[id * 2], ST[id * 2 + 1]);
}
void updateChoice(){
ST[1].se = (ST[1].se * 2) % MOD;
lz[1] = (lz[1] * 2) % MOD;
}
pi query(const int &l, const int &r, int id = 1, int be = 1, int en = X.size()){
if(r < be || en < l) return {0, 0};
if(l <= be && en <= r) return ST[id];
int mi = (be + en) / 2;
if(lz[id] > 1) down(id);
return comb(query(l, r, id * 2, be, mi), query(l, r, id * 2 + 1, mi + 1, en));
}
int p2[N];
void init(){
p2[0] = 1;
FORU(i, 1, n) p2[i] = (p2[i - 1] * 2) % MOD;
}
int main(){
IOS;
Fi();
cin >> n;
init();
FORU(i, 1, n){
cin >> a[i];
X.eb(a[i]);
}
memset(lz, 1, sizeof(lz));
sort(ALL(X));
X.resize(unique(ALL(X)) - X.begin());
pi ans = {0, 0};
FORU(i, 1, n){
a[i] = lower_bound(ALL(X), a[i]) - X.begin() + 1;
pi lef = query(a[i] + 1, X.size()); lef.fi += 1;
pi rig = query(1, a[i] - 1); rig.fi += 1;
updateChoice();
pi tmp = comb({1, p2[i - 1]}, comb(lef, rig));
update(a[i], tmp);
tmp.se = mul(tmp.se, p2[n - i]);
ans = comb(ans, tmp);
}
cout << ans.fi << " " << ans.se;
return 0;
}
Compilation message
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 |
2 ms |
3404 KB |
Output isn't correct |
| 2 |
Incorrect |
2 ms |
3404 KB |
Output isn't correct |
| 3 |
Incorrect |
2 ms |
3404 KB |
Output isn't correct |
| 4 |
Correct |
1 ms |
3404 KB |
Output is correct |
| 5 |
Correct |
1 ms |
3404 KB |
Output is correct |
| 6 |
Correct |
2 ms |
3404 KB |
Output is correct |
| 7 |
Incorrect |
2 ms |
3404 KB |
Output isn't correct |
| 8 |
Incorrect |
3 ms |
3404 KB |
Output isn't correct |
| 9 |
Incorrect |
2 ms |
3404 KB |
Output isn't correct |
| 10 |
Incorrect |
2 ms |
3496 KB |
Output isn't correct |
| 11 |
Incorrect |
155 ms |
9496 KB |
Output isn't correct |
| 12 |
Incorrect |
151 ms |
9220 KB |
Output isn't correct |
| 13 |
Incorrect |
125 ms |
7056 KB |
Output isn't correct |
| 14 |
Incorrect |
160 ms |
9248 KB |
Output isn't correct |
| 15 |
Incorrect |
229 ms |
9664 KB |
Output isn't correct |
| 16 |
Incorrect |
260 ms |
10012 KB |
Output isn't correct |
| 17 |
Incorrect |
205 ms |
10028 KB |
Output isn't correct |
| 18 |
Incorrect |
210 ms |
10008 KB |
Output isn't correct |
| 19 |
Incorrect |
210 ms |
10124 KB |
Output isn't correct |
| 20 |
Incorrect |
205 ms |
10016 KB |
Output isn't correct |
