# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
1001037 |
2024-06-18T13:22:14 Z |
abczz |
Holiday (IOI14_holiday) |
C++17 |
|
1469 ms |
11344 KB |
//#include"holiday.h"
#include <iostream>
#include <vector>
#include <array>
#include <algorithm>
#include <queue>
#define ll long long
using namespace std;
ll n, x, z, cl, cr, f, G[100000];
queue <array<ll, 4>> Q[2];
array <ll, 2> A[100000];
struct SegTree{
vector <ll> st{vector <ll> (400000, 0)};
vector <ll> cnt{vector <ll> (400000, 0)};
void update(ll id, ll l, ll r, ll q, bool b) {
if (l == r) {
if (b) st[id] = A[l][0], cnt[id] = 1;
else st[id] = cnt[id] = 0;
return;
}
ll mid = (l+r)/2;
if (q <= mid) update(id*2, l, mid, q, b);
else update(id*2+1, mid+1, r, q, b);
st[id] = st[id*2] + st[id*2+1];
cnt[id] = cnt[id*2] + cnt[id*2+1];
}
ll k;
ll init_query(ll K) {
k = K;
return kth_query(1, 0, n-1);
}
ll kth_query(ll id, ll l, ll r) {
if (k >= cnt[id]) {
k -= cnt[id];
return st[id];
}
if (l == r) return 0;
ll mid = (l+r)/2;
if (cnt[id*2] >= k) return kth_query(id*2, l, mid);
else {
k -= cnt[id*2];
return st[id*2] + kth_query(id*2+1, mid+1, r);
}
}
}ST;
ll solve(ll l, ll r, ll optL, ll optR) {
ll mid = (l+r)/2;
while (cl < mid) {
ST.update(1, 0, n-1, G[cl], 0);
++cl;
}
cr = max(cr, mid);
while (cr < optL) {
ST.update(1, 0, n-1, G[cr], 1);
++cr;
}
ll opt = -1, optVal = -1, cur, m = z-(x-mid)-max(0LL, optL-mid);
for (int i=max(mid, optL); i<=optR; ++i) {
if (m <= 0) break;
ST.update(1, 0, n-1, G[i], 1);
cur = ST.init_query(m);
if (cur >= optVal) {
opt = i;
optVal = cur;
}
--m;
}
for (int i=max(mid, optL); i<=optR; ++i) {
ST.update(1, 0, n-1, G[i], 0);
}
//cout << mid << " " << optVal << " " << opt << endl;
if (l != mid) Q[1].push({l, mid-1, optL, opt});
if (mid != r) Q[1].push({mid+1, r, opt, optR});
return optVal;
}
void sharky() {
Q[0].push({0, x, 0, n-1});
while (!Q[0].empty()) {
cl = cr = 0;
while (!Q[0].empty()) {
auto [l, r, ql, qr] = Q[0].front();
Q[0].pop();
f = max(f, solve(l, r, ql, qr));
}
swap(Q[0], Q[1]);
while (cl < cr) {
ST.update(1, 0, n-1, G[cl], 0);
++cl;
}
}
}
long long int findMaxAttraction(int _n, int start, int d, int attraction[]) {
n = _n, x = start, z = d;
for (int i=0; i<n; ++i) A[i] = {attraction[i], i};
sort(A, A+n, [](auto a, auto b) {
return a[0] > b[0];
});
for (int i=0; i<n; ++i) {
G[A[i][1]] = i;
}
sharky();
for (int i=0; i<n/2; ++i) {
swap(G[i], G[n-1-i]);
}
x = n-1-x;
sharky();
return f;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
9052 KB |
Output is correct |
2 |
Correct |
2 ms |
9052 KB |
Output is correct |
3 |
Correct |
3 ms |
9052 KB |
Output is correct |
4 |
Correct |
3 ms |
9168 KB |
Output is correct |
5 |
Correct |
3 ms |
9304 KB |
Output is correct |
6 |
Correct |
2 ms |
9052 KB |
Output is correct |
7 |
Correct |
3 ms |
9052 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
564 ms |
10672 KB |
Output is correct |
2 |
Correct |
528 ms |
10576 KB |
Output is correct |
3 |
Correct |
560 ms |
10576 KB |
Output is correct |
4 |
Correct |
650 ms |
10664 KB |
Output is correct |
5 |
Correct |
858 ms |
10688 KB |
Output is correct |
6 |
Correct |
180 ms |
9556 KB |
Output is correct |
7 |
Correct |
407 ms |
9960 KB |
Output is correct |
8 |
Correct |
509 ms |
10236 KB |
Output is correct |
9 |
Correct |
127 ms |
9556 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
9052 KB |
Output is correct |
2 |
Correct |
11 ms |
9192 KB |
Output is correct |
3 |
Correct |
10 ms |
9180 KB |
Output is correct |
4 |
Correct |
22 ms |
9252 KB |
Output is correct |
5 |
Correct |
19 ms |
9052 KB |
Output is correct |
6 |
Correct |
7 ms |
9052 KB |
Output is correct |
7 |
Correct |
6 ms |
9052 KB |
Output is correct |
8 |
Correct |
7 ms |
9052 KB |
Output is correct |
9 |
Correct |
7 ms |
9052 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
528 ms |
11344 KB |
Output is correct |
2 |
Correct |
537 ms |
11324 KB |
Output is correct |
3 |
Correct |
327 ms |
10064 KB |
Output is correct |
4 |
Correct |
18 ms |
9052 KB |
Output is correct |
5 |
Correct |
6 ms |
9052 KB |
Output is correct |
6 |
Correct |
6 ms |
9052 KB |
Output is correct |
7 |
Correct |
6 ms |
9048 KB |
Output is correct |
8 |
Correct |
1459 ms |
10776 KB |
Output is correct |
9 |
Correct |
1469 ms |
10644 KB |
Output is correct |