#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
const int BLOCK = 400;
const int MAX = 2e5 + 5;
int tree[MAX];
void update(int pos, int val){
while(pos < MAX){
tree[pos] += val;
pos += pos & (-pos);
}
}
int ask(int l, int r){
if(r < l) return 0;
if(l != 1) return ask(1, r) - ask(1, l - 1);
int ans = 0;
while(r > 0){
ans += tree[r];
r -= r & (-r);
}
return ans;
}
vector<int> mp[MAX];
vector<int> query(int i){
if(!mp[i].empty()) return mp[i];
return mp[i] = ask(i - 1);
}
int find_best(int n) {
vector<int> order(n);
srand(time(0));
iota(order.begin(), order.end(), 1);
random_shuffle(order.begin(), order.end());
vector<int> a;
int cnt = 0;
set<int> st;
for (int i = 0; i < n; i++)
{
st.insert(i + 1);
}
for (int j = 0; j < min(500, n); ++j)
{
int i = order[j];
a = query(i);
if(a[0] + a[1] == 0) return i - 1;
if(a[0] + a[1] < cnt){
update(i, 1);
st.erase(i);
}
else{
cnt = a[0] + a[1];
}
}
vector<int> blocks;
int c = 0;
while(true){
auto itr = st.lower_bound(c);
if(itr == st.end()){
--itr;
}
a = query(*itr);
if(a[0] + a[1] == 0) return (*itr) - 1;
if(a[0] + a[1] < cnt){
update(*itr, 1);
st.erase(itr);
continue;
}
c = *itr;
blocks.push_back(c);
c += MAX;
if(prev(st.end()) == itr){
break;
}
}
for(int i = 0; i < blocks.size() - 1; ++i){
int b1 = blocks[i], b2 = blocks[i + 1];
if(b1 == b2) continue;
while(query(b1)[0] - query(b2)[0] - ask(b1, b2) > 0){
int l = b1, r = b2;
while(l <= r){
int x = (l + r) / 2;
auto itr = st.lower_bound(x);
if(itr == st.end() || (*itr) > r){
--itr;
}
int mid = *itr;
a = query(mid);
if(a[0] + a[1] == 0){
return mid - 1;
}
if(a[0] + a[1] < cnt){
update(mid, 1);
st.erase(mid);
break;
}
a[0] -= query(b1)[0] + ask(b1, mid);
a[1] -= query(b2)[1] + ask(mid, b2);
if(a[1] > 0){
l = mid + 1;
}
else{
r = mid - 1;
}
}
}
}
}
Compilation message
prize.cpp: In function 'int find_best(int)':
prize.cpp:87:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
87 | for(int i = 0; i < blocks.size() - 1; ++i){
| ~~^~~~~~~~~~~~~~~~~~~
prize.cpp:38:24: warning: control reaches end of non-void function [-Wreturn-type]
38 | vector<int> order(n);
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
58 ms |
28988 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
54 ms |
28996 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
