#include <bits/stdc++.h>
using namespace std;
struct treap{
const int dydis = 1e5 * 3;
struct node{
int l = -1, r = -1;
int w, val1, val2;
int sz = 1;
int leftmost = 1e9;
int rightmost = 1e9;
};
vector<node> tree;
int dbInd = 0;
int root = -1;
int newN(int x, int y){
tree[dbInd].val1 = tree[dbInd].leftmost = x; tree[dbInd].val2 = tree[dbInd].rightmost = y;
tree[dbInd].w = rand();
return dbInd++;
}
void update(int v){
tree[v].sz = 1;
tree[v].leftmost = tree[v].val1;
tree[v].rightmost = tree[v].val2;
if(tree[v].l != -1){
tree[v].sz += tree[tree[v].l].sz;
tree[v].leftmost = tree[tree[v].l].leftmost;
}
if(tree[v].r != -1) {
tree[v].sz += tree[tree[v].r].sz;
tree[v].rightmost = tree[tree[v].r].rightmost;
}
}
int merge(int l, int r){
if(l == -1) return r;
if(r == -1) return l;
if(tree[l].w > tree[r].w){
int bs = merge(tree[l].r, r);
tree[l].r = bs;
update(l);
return l;
}else{
int bs = merge(l, tree[r].l);
tree[r].l = bs;
update(r);
return r;
}
}
pair<int, int> split(int v, int x){
if(v == -1) return {-1, -1};
int lsz = 0;
if(tree[v].l != -1) lsz = tree[tree[v].l].sz;
//cout << "split nuo " << v << ". jo val1 = " << tree[v].val1 << ", o lsz = " << lsz << endl;
if(lsz <= x){ // as kairej
auto bus = split(tree[v].r, x-lsz-1);
tree[v].r = bus.first;
update(v);
return {v, bus.second};
}else{
auto bus = split(tree[v].l, x);
tree[v].l = bus.second;
update(v);
return {bus.first, v};
}
}
void print(int v = -2){
if(v == -2) v = root;
if(v == -1) return;
print(tree[v].l);
cout <<v << ": " << tree[v].val1 << "; " << tree[v].val2 << ", leftmost: " << tree[v].leftmost << ", raitmost: " << tree[v].rightmost << " | l = " << tree[v].l << ", r = " << tree[v].r << endl;
print(tree[v].r);
}
treap(){
tree.resize(dydis);
}
};
const int dydis = 1e5 + 10;
vector<int> fins[dydis + 1];
struct seg_tree{
struct node{
int l, r;
vector<int> val;
};
int dbInd = 0;
int n;
vector <node> tree;
void build(int v){
if(v >= n){
tree[v].l = tree[v].r = dbInd;
tree[v].val = fins[dbInd];
dbInd++;
}else{
build(v*2);
build(v*2+1);
tree[v].l = tree[v*2].l;
tree[v].r = tree[v*2+1].r;
for(auto x : tree[v*2].val) tree[v].val.push_back(x);
for(auto x : tree[v*2+1].val) tree[v].val.push_back(x);
}
sort(tree[v].val.begin(), tree[v].val.end());
//if(tree[v].val.size()) {cout << "fins[" << tree[v].l << "; " << tree[v].r << "]: "; for(auto x : tree[v].val) cout << x<< " "; cout << endl;}
}
seg_tree(int dd){
n = dd;
tree.resize(2 * n + 1);
build(1);
}
int getVal(int v, int l, int r, int l1, int r1){
if(l <= tree[v].l && tree[v].r <= r){
//cout << endl;
//for(auto x : tree[v].val) cout << x << " "; cout << " ";
//cout <<l1 << " ir " << r1 << " pridedu [" << tree[v].l << "; " << tree[v].r << "] = " << ((int)(upper_bound(tree[v].val.begin(), tree[v].val.end(), r1) - lower_bound(tree[v].val.begin(), tree[v].val.end(), l1))) << endl;
return upper_bound(tree[v].val.begin(), tree[v].val.end(), r1) - lower_bound(tree[v].val.begin(), tree[v].val.end(), l1);
}else if(r < tree[v].l || tree[v].r < l){
return 0;
}else{
return getVal(v*2, l, r, l1, r1) + getVal(v*2+1, l, r, l1, r1);
}
}
};
int n, m, as;
vector<pair<int, int> > vec, rl;
vector<int> mas;
int tevas[dydis];
int le[dydis], ri[dydis];
treap medis;
int l, r, a1, a2, a3, nj;
pair<int, int> prm, ant;
int GetBestPosition(int N, int C, int RR, int *K, int *S, int *E) {
n = N; m = C; as = RR;
for(int i = 0; i < n; i++) tevas[i] = le[i] = ri[i];
for(int i = 0; i < m; i++) vec.push_back({S[i], E[i]});
for(int i = 0; i < n-1; i++) mas.push_back(K[i]);
for(int i = 0; i < n; i++) medis.root = medis.merge(medis.root, medis.newN(i, i));
//medis.print();
//cout << endl;
for(auto x : vec){
l = x.first;
r = x.second;
//cout << "medis dabar: \n"; medis.print();
//cout << "\nimsiu " << l << "; " << r << ", t.y. pirma splitinsiu " << l-1 << endl;
//cout << endl;
prm = medis.split(medis.root, l-1);
ant = medis.split(prm.second, r-l);
a1 = prm.first;
a2 = ant.first;
a3 = ant.second;
//cout << "isskaidau taip: \n";
//cout << "a1:\n";medis.print(a1); cout << endl << "a2:\n"; medis.print(a2); cout << endl << "a3:\n"; medis.print(a3); cout << endl;
nj = medis.newN(medis.tree[a2].leftmost, medis.tree[a2].rightmost);
rl.push_back({medis.tree[a2].leftmost, medis.tree[a2].rightmost});
//cout << ", tai pridesiu " << medis.tree[a2].leftmost << " - " << medis.tree[a2].rightmost << endl;
//cout << endl;
medis.root = medis.merge(medis.merge(a1, nj), a3);
// man reik a3;
}
for(auto x : rl){
//cout << "[" << x.first << "; " << x.second << "]\n";
fins[x.first].push_back(x.second);
}
for(int i = 0; i <= n; i++){
//cout <<i << ": "; for(auto x : fins[i]) cout << x << " "; cout << endl;
}
seg_tree medis(dydis);
mas.push_back(as);
int L = -1, R = n;
for(int i = mas.size()-1; i > -1; i--) if(mas[i] > mas.back()) L = max(L, i);
pair<int, int> ans = {-1, -1};
for(int i = mas.size()-1; i > -1; i--){
if(i != (int)mas.size()-1) swap(mas[i+1], mas[i]);
if(L == i){
while(L != -1 && mas[L] <= mas[i]) L--;
}
if(i != (int)mas.size()-1 && mas[i+1] > mas[i]) R = i+1;
//cout << "intervale [" << L+1 << "; " << i << "] - [" << i << "; " << R-1 << "], yra " << medis.getVal(1, L+1, i, i, R-1) << endl;
//cout << "i = " << i << ", L = " << L << ", R = " << R << endl;
ans = max(ans, make_pair(medis.getVal(1, L+1, i, i, R-1), -i));
}
// cout << ans.first << " yra ats" << endl;
return -ans.second;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
18252 KB |
Output is correct |
| 2 |
Correct |
12 ms |
18216 KB |
Output is correct |
| 3 |
Correct |
13 ms |
18332 KB |
Output is correct |
| 4 |
Correct |
13 ms |
18380 KB |
Output is correct |
| 5 |
Correct |
12 ms |
18236 KB |
Output is correct |
| 6 |
Correct |
13 ms |
18400 KB |
Output is correct |
| 7 |
Correct |
13 ms |
18380 KB |
Output is correct |
| 8 |
Correct |
13 ms |
18412 KB |
Output is correct |
| 9 |
Correct |
13 ms |
18252 KB |
Output is correct |
| 10 |
Correct |
13 ms |
18324 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
18468 KB |
Output is correct |
| 2 |
Correct |
22 ms |
19148 KB |
Output is correct |
| 3 |
Correct |
15 ms |
18472 KB |
Output is correct |
| 4 |
Correct |
21 ms |
19148 KB |
Output is correct |
| 5 |
Correct |
20 ms |
19140 KB |
Output is correct |
| 6 |
Correct |
20 ms |
18980 KB |
Output is correct |
| 7 |
Correct |
21 ms |
19216 KB |
Output is correct |
| 8 |
Correct |
29 ms |
19220 KB |
Output is correct |
| 9 |
Correct |
14 ms |
18460 KB |
Output is correct |
| 10 |
Correct |
23 ms |
19264 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
114 ms |
25152 KB |
Output is correct |
| 2 |
Correct |
233 ms |
35596 KB |
Output is correct |
| 3 |
Correct |
86 ms |
21688 KB |
Output is correct |
| 4 |
Correct |
238 ms |
35616 KB |
Output is correct |
| 5 |
Correct |
226 ms |
34936 KB |
Output is correct |
| 6 |
Correct |
225 ms |
32084 KB |
Output is correct |
| 7 |
Correct |
247 ms |
35624 KB |
Output is correct |
| 8 |
Correct |
228 ms |
35604 KB |
Output is correct |
| 9 |
Correct |
58 ms |
20508 KB |
Output is correct |
| 10 |
Correct |
73 ms |
21800 KB |
Output is correct |
