#include <bits/stdc++.h>
using namespace std;
struct minSegtree{
int n;
vector<int> arr;
vector<int> tree;
minSegtree(vector<int> temp){
int n = temp.size();
arr = temp;
tree.assign(4*n, 0);
build(0, 0, n-1);
}
void build(int ncur, int nleft, int nright){
if(nleft==nright){
tree[ncur] = arr[nleft];
}
else{
int nmid = (nleft+nright)/2;
build(2*ncur+1, nleft, nmid);
build(2*ncur+2, nmid+1, nright);
tree[ncur] = min(tree[2*ncur+1], tree[2*ncur+2]);
}
}
int query(int qleft, int qright, int ncur, int nleft, int nright){
if(qleft>nright || qright<nleft){
return n+1;
}
else if(qleft<=nleft && nright<=qright){
return tree[ncur];
}
else{
int nmid = (nleft+nright)/2;
return min(query(qleft, qright, 2*ncur+1, nleft, nmid), query(qleft, qright, 2*ncur+2, nmid+1, nright));
}
}
};
struct rangeSegtree{
int n;
vector<int> arr;
vector<int> tree;
rangeSegtree(int _n): n(_n){
arr.assign(n+1, 0);
tree.assign(4*n+4, 0);
}
int privgetsum(int qleft, int qright, int ncur, int nleft, int nright){
if(qleft>nright || qright<nleft){
return 0;
}
else if(qleft<=nleft && nright<=qright){
return tree[ncur];
}
else{
int nmid = (nleft+nright)/2;
return privgetsum(qleft, qright, 2*ncur+1, nleft, nmid) + privgetsum(qleft, qright, 2*ncur+2, nmid+1, nright);
}
}
void privupdate(int pos, int val, int ncur, int nleft, int nright){
if(nleft==nright){
arr[pos]+=val;
tree[ncur]+=val;
}
else{
int nmid = (nleft+nright)/2;
if(pos<=nmid){
privupdate(pos, val, 2*ncur+1, nleft, nmid);
}
else{
privupdate(pos, val, 2*ncur+2, nmid+1, nright);
}
tree[ncur]=tree[2*ncur+1]+tree[2*ncur+2];
}
}
void update(int left, int right){
privupdate(left, 1, 0, 0, n);
privupdate(right+1, -1, 0, 0, n);
}
int getAns(){
int maxx = 0;
int ans = 0;
for(int i=0; i<n; i++){
int temp = privgetsum(0, i, 0, 0, n);
if(temp>maxx){
maxx = temp;
ans = i;
}
}
return ans;
}
};
struct segtree{
int n;
vector<pair<int, int> > arr;
vector<int> tree;
vector<bool> flag;
segtree(int _n): n(_n){
arr.resize(n);
tree.resize(4*n);
flag.assign(4*n, false);
build(0, 0, n-1);
}
void propogate(int ncur, int nleft, int nright){
if(nleft!=nright && flag[ncur]==true){
flag[2*ncur+1]=true;
flag[2*ncur+2]=true;
tree[2*ncur+1]=0;
tree[2*ncur+2]=0;
}
}
void build(int ncur, int nleft, int nright){
if(nleft==nright){
tree[ncur] = 1;
arr[nleft] = {nleft, nleft};
}
else{
int nmid = (nleft+nright)/2;
build(2*ncur+1, nleft, nmid);
build(2*ncur+2, nmid+1, nright);
tree[ncur] = tree[2*ncur+1] + tree[2*ncur+2];
}
}
int getSum(int qleft, int qright, int ncur, int nleft, int nright){
if(qleft>nright || qright<nleft || flag[ncur]){
return 0;
}
else if(qleft<=nleft && nright<=qright){
return tree[ncur];
}
else{
int nmid = (nleft+nright)/2;
return getSum(qleft, qright, 2*ncur+1, nleft, nmid) + getSum(qleft, qright, 2*ncur+2, nmid+1, nright);
}
}
void update(int qleft, int qright, int ncur, int nleft, int nright){
if(qleft>nright || qright<nleft || flag[ncur]){
return;
}
else if(qleft<=nleft && nright<=qright){
flag[ncur] = true;
tree[ncur] = 0;
}
else{
int nmid = (nleft+nright)/2;
update(qleft, qright, 2*ncur+1, nleft, nmid);
update(qleft, qright, 2*ncur+2, nmid+1, nright);
tree[ncur]=tree[2*ncur+1]+tree[2*ncur+2];
}
}
int findpos(int pos, int past, int ncur, int nleft, int nright){
if(nleft==nright){
return nleft;
}
else{
propogate(ncur, nleft, nright);
int nmid = (nleft+nright)/2;
if(past+tree[2*ncur+1]>=pos){
return findpos(pos, past, 2*ncur+1, nleft, nmid);
}
else{
return findpos(pos, past+tree[2*ncur+1], 2*ncur+2, nmid+1, nright);
}
}
}
pair<int, int> query(int left, int right){
int curleft = findpos(left, 0, 0, 0, n-1);
int curright = findpos(right, 0, 0, 0, n-1);
update(curleft+1, curright, 0, 0, n-1);
arr[curleft].second = arr[curright].second;
return {arr[curleft].first, arr[curleft].second};
}
};
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E){
segtree poss(N);
vector<int> ss;
vector<int> ee;
for(int i=0; i<C; i++){
pair<int, int> temp = poss.query(S[i]+1, E[i]+1);
ss.push_back(temp.first);
ee.push_back(temp.second);
}
/*
for(int i=0; i<C; i++){
cout << ss[i] << ' ';
}
cout << '\n';
for(int i=0; i<C; i++){
cout << ee[i] << ' ';
}
cout << '\n';
*/
vector<int> arr;
for(int i=0; i<N-1; i++){
arr.push_back(K[i]);
}
minSegtree tree(arr);
rangeSegtree range(N);
for(int i=0; i<C; i++){
if(tree.query(ss[i], ee[i]-1, 0, 0, N)<R){
range.update(ss[i], ee[i]);
}
}
return range.getAns();
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int K[] = {1, 0, 2, 4};
int S[] = {1, 0, 0};
int E[] = {3, 1, 1};
cout << GetBestPosition(10, 3, 3, K, S, E) << '\n';
return 0;
}
Compilation message
/usr/bin/ld: /tmp/ccmqdtg5.o: in function `main':
tournament.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cctD6AZ7.o:grader.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
