| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 640555 |
2022-09-14T21:33:13 Z |
KYoA_A |
Zoltan (COCI16_zoltan) |
C++17 |
|
151 ms |
13276 KB |
/*---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---*/
#include "bits/stdc++.h"
using namespace std;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define dbg(x...)
#endif
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define rrep(a, b, c) for(int a = (b); a > c; --a)
#define each(a, b) for(auto& a : b)
#define sz(x) (int)(x).size()
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define vi vector<int>
#define ar array
template<class T> using V = vector<T>;
template<class T> using pq = priority_queue<T>;
template<class T> using pqg = priority_queue<T, vector<T>, greater<T>>;
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define eb emplace_back
#define rsz resize
#define bk back()
#define pi pair<int, int>
#define pl pair<ll, ll>
#define mp make_pair
#define f first
#define s second
#define pct(x) __builtin_popcount(x)
constexpr int fsb(int x) {return __builtin_ffs(x) - 1;} // first set bit
constexpr int log2(int x) {return x == 0 ? 0 : 31-__builtin_clz(x);} // floor(log2(x))
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
template <class T> bool umin(T& a, const T& b){return b<a?a=b, 1:0;}
template <class T> bool umax(T& a, const T& b){return a<b?a=b, 1:0;}
const int d4i[4]={-1, 0, 1, 0}, d4j[4]={0, 1, 0, -1};
const int d8i[8]={-1, -1, 0, 1, 1, 1, 0, -1}, d8j[8]={0, 1, 1, 1, 0, -1, -1, -1};
using ll = long long;
using ld = long double;
using str = string;
const int inf = (int)1e9 + 5;
const ll infl = (ll)1e18 + 5;
const ld PI = acos((ld)-1);
const int MOD = 1e9 + 7;
const int N = 2e5 + 10;
/*---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---*/
template<class T> struct Seg { // comb(ID,b) = b
const T ID{}; T comb(T a, T b) {
if(a.f != b.f) return max(a, b);
return {a.f, (a.s + b.s)%MOD};
}
int n; vector<T> seg;
void init(int _n) {
n = 1;
while(n < _n) n<<=1;
seg.assign(2*n,ID);
}
void pull(int p) { seg[p] = comb(seg[2*p],seg[2*p+1]); }
void upd(int p, T val) { // set val at position p
p += n;
seg[p] = comb(seg[p], val); for (p /= 2; p; p /= 2) pull(p); }
T query(int l, int r) { // sum on interval [l, r]
T ra = ID, rb = ID;
for (l += n, r += n+1; l < r; l /= 2, r /= 2) {
if (l&1) ra = comb(ra,seg[l++]);
if (r&1) rb = comb(seg[--r],rb);
}
return comb(ra,rb);
}
};
#define int ll
void solve(istream &cin = std::cin, ostream &cout = std::cout){
int n; cin >> n;
vi v(n); each(x, v) cin >> x;
vi a = v;
sort(all(a));
a.erase(unique(all(a)), a.end());
each(x, v) x = lb(all(a), x) - a.begin() + 1;
reverse(all(v));
rrep(i, n-1, -1) v.eb(v[i]);
Seg<pi> s;
s.init(n + 2);
s.upd(0, {0, 1});
pi ans{};
each(x, v){
auto y = s.query(0, x - 1);
y.f++;
ans = s.comb(ans, y);
s.upd(x, y);
}
int z = n - ans.f;
ll x = ans.s;
while(z){
x = x*2%MOD;
--z;
}
x = x*((MOD + 1)/2)%MOD;
cout << ans.f << ' ' << x << '\n';
}
void gen(stringstream &s){
int n = 1 + rng()%15;
s << n << '\n';
rep(i, 0, n) s << 1 + rng()%n << ' ';
}
void stress(istream &cin = std::cin, ostream &cout = std::cout){
int n; cin >> n;
vi v(n); each(x, v) cin >> x;
vi a;
pi ans{};
function<void(int)> go = [&](int i){
if(i == n){
// dbg(a, ans)
Seg<pi> s; s.init(n + 2);
s.upd(0, {0, 1});
each(x, a){
auto y = s.query(0, x - 1);
y.f++;
ans = s.comb(ans, y);
s.upd(x, y);
}
return;
}
a.eb(v[i]); go(i + 1); a.pop_back();
a.insert(a.begin(), v[i]); go(i + 1); a.erase(a.begin());
};
a.eb(v[0]);
go(1);
cout << ans.s << '\n';
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
// stress();
// #define STRESS
#ifdef STRESS
for (int cnt = 1;; cnt++)
{
stringstream ss, in1, out1, in2, out2;
gen(ss);
in1 << ss.str();
in2 << ss.str();
solve(in1, out1);
stress(in2, out2);
if (out1.str() != out2.str())
{
cout << "fail: " << cnt << endl;
cout << ss.str() << endl;
cout << "solve:" << endl;
cout << out1.str() << endl;
cout << "stress:" << endl;
cout << out2.str() << endl;
break;
}
else if (cnt % 100 == 0)
cout << "ok: " << cnt << endl;
}
#endif
// solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| 11 |
Correct |
90 ms |
12240 KB |
Output is correct |
| 12 |
Correct |
79 ms |
11676 KB |
Output is correct |
| 13 |
Correct |
69 ms |
7392 KB |
Output is correct |
| 14 |
Correct |
98 ms |
11720 KB |
Output is correct |
| 15 |
Correct |
121 ms |
12548 KB |
Output is correct |
| 16 |
Correct |
151 ms |
13276 KB |
Output is correct |
| 17 |
Correct |
108 ms |
13156 KB |
Output is correct |
| 18 |
Correct |
108 ms |
13128 KB |
Output is correct |
| 19 |
Correct |
108 ms |
13104 KB |
Output is correct |
| 20 |
Correct |
110 ms |
13228 KB |
Output is correct |
