Submission #490815

#	Time	Username	Problem	Language	Result	Execution time	Memory
490815		EJOI2019Andrew	Election (BOI18_election)	C++14	0 / 100	4 ms	332 KiB

election

/**
We have empty array and queries:
0: add x in the end of array
1: on segment l..r for number x find such a[i] that (a[i] xor x) is maximal
2: delete last k elements from array
3: on segment l..r for number x find amount of numbers >=x
4: on segment l..r find k-th element (if sorted)
1 <= M <= 500000
1 <= x <= 500000
1 <= L <= R <= n
**/

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define mp make_pair

const int N = 5e5 + 11;
const int MAX=524287;

int v[N*60],l1[N*60],r1[N*60],kol;
int root[N];

void update(int deep, int i1, int i2, int l, int r, int x)
{
    if (l==r) {v[i1]=v[i2]+1; return;}
    int mid=(l+r)>>1;
    if ((x&(1<<deep))==0)
    {
        kol++;
        l1[i1]=kol;
        r1[i1]=r1[i2];
        update(deep-1,l1[i1],l1[i2],l,mid,x);
    } else
    {
        kol++;
        r1[i1]=kol;
        l1[i1]=l1[i2];
        update(deep-1,r1[i1],r1[i2],mid+1,r,x);
    }
    v[i1]=v[l1[i1]]+v[r1[i1]];
}

void build(int i, int l, int r)
{
    v[i]=0;
    if (l==r) return;
    int mid=(l+r)>>1;
    kol++;
    l1[i]=kol;
    kol++;
    r1[i]=kol;
    build(l1[i],l,mid);
    build(r1[i],mid+1,r);
}

int get1(int deep, int i1, int i2, int l, int r, int x)
{
    if (l==r) return l;
    int mid=(l+r)>>1;
    //cout<<l<<" "<<r<<" "<<x<<endl;
    if ((x&(1<<deep))==0)
    {
        //cout<<"0 - "<<v[r1[i2]]-v[r1[i1]]<<endl;
        if (v[r1[i2]]-v[r1[i1]]>0) return get1(deep-1,r1[i1],r1[i2],mid+1,r,x);
        return get1(deep-1,l1[i1],l1[i2],l,mid,x);
    } else
    {
        //cout<<"1 - "<<v[l1[i2]]-v[l1[i1]]<<endl;
        if (v[l1[i2]]-v[l1[i1]]>0) return get1(deep-1,l1[i1],l1[i2],l,mid,x);
        return get1(deep-1,r1[i1],r1[i2],mid+1,r,x);
    }
}

int get3(int deep, int i1, int i2, int l, int r, int x)
{
    if (l==r) return v[i2]-v[i1];
    int mid=(l+r)>>1;
    if (x<=mid) return get3(deep-1,l1[i1],l1[i2],l,mid,x);
    else return v[l1[i2]]-v[l1[i1]]+get3(deep-1,r1[i1],r1[i2],mid+1,r,x);
}

int get4(int i1, int i2, int l, int r, int x)
{
    if (l==r) return l;
    int mid=(l+r)>>1;
    int k=v[l1[i2]]-v[l1[i1]];
    if (k>=x) return get4(l1[i1],l1[i2],l,mid,x);
    else return get4(r1[i1],r1[i2],mid+1,r,x-k);
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n,m;
    cin>>n;
  string s;
  cin>>s>>m;

  for(int i=0; i<m; ++i)
  {
   int l,r;
    cin>>l>>r;
    --l,--r;
    int c(0),c1(0),cnt(0),f(0),cnt1(0);
    for(int j=l; j<=r; ++j)
    {
      cnt+=(s[j]=='C');
      cnt1+=(s[j]=='T');
      if(cnt<cnt1-f)
      {
      ++f;
       ++c;
    }

    }
    cnt=0,f=0,cnt1=0;
    for(int j=r; j>=l; --j)
    {
      cnt+=(s[j]=='C');
      cnt1+=(s[j]=='T');
      if(cnt<cnt1-f)
      {
      ++f;
       ++c1;
    }
    }
    cout<<max(c,c1)<<"\n";
  }


}

• Subtask 1: 0 / 28
• Subtask 2: 0 / 54
• Subtask 3: 0 / 18