#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX = 2e5 + 5;
const int BLOCK = 400;
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;
}
int intRand(){
return (rand() << 14) | rand();
}
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(450, (int)order.size()); ++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()) break;
if(query(*itr)[0] + query(*itr)[1] < cnt){
update(*itr, 1);
st.erase(itr);
continue;
}
c = *itr;
blocks.push_back(c);
c = c + BLOCK;
}
if(*prev(st.end()) != blocks.back()){
blocks.push_back(*prev(st.end()));
}
for (int i = 0; i < blocks.size() - 1; i++)
{
int l = blocks[i], r = blocks[i + 1];
if(query(r)[2] - query(l)[2] - ask(l, r) == 0) continue;
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 && !ask(mid, mid)){
update(mid, 1);
st.erase(mid);
break;
}
a[0] -= query(blocks[i + 1])[1] + ask(blocks[i], mid - 1);
a[1] -= query(blocks[i])[0] + ask(mid + 1, blocks[i + 1]);
if(a[1] > 0){
l = mid + 1;
}
else{
r = mid - 1;
}
}
}
}
Compilation message
prize.cpp: In function 'int find_best(int)':
prize.cpp:87:23: 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:42:24: warning: control reaches end of non-void function [-Wreturn-type]
42 | vector<int> order(n);
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
57 ms |
29012 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
56 ms |
29032 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
