Submission #73873

#	Time	Username	Problem	Language	Result	Execution time	Memory
73873		jiajunlee	Election (BOI18_election)	C++14	0 / 100	9 ms	376 KiB

election

#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;


typedef long long LL;


const LL MAXN = 500050;
const LL INF = MAXN * 10005;

struct vote
{
  LL minLR, sumLR, minRL, sumRL;
};

typedef struct vote Vote;

LL n, q;
char election[MAXN] = {};
Vote seg_Tree[MAXN * 4] = {};

void built_Tree(LL i, LL j, LL pos)
{
  if(i > j)return;
  
  if(i == j)
  {
    LL val;
    if(election[i] == 'C')val = 1;
    else val = -1;
    seg_Tree[pos].minLR = val;
    seg_Tree[pos].sumLR = val;
    seg_Tree[pos].minRL = val;
    seg_Tree[pos].sumRL = val;
    return;
  }

  LL mid = i + ((j-i)/2);
  built_Tree(i, mid, pos*2);
  built_Tree(mid+1, j, (pos*2) + 1);
  if( (seg_Tree[pos*2].minLR == mid-i+1) && (seg_Tree[pos*2+1].minLR == j-mid) )
  {
    seg_Tree[pos].minLR = seg_Tree[pos].sumLR = seg_Tree[pos].minRL = seg_Tree[pos].sumRL = j-i+1;
    return; 
  }
  seg_Tree[pos].minLR = min(seg_Tree[pos*2].minLR , seg_Tree[pos*2].sumLR + seg_Tree[(pos*2)+1].minLR);
  seg_Tree[pos].sumLR = 
  seg_Tree[pos*2].sumLR + seg_Tree[(pos*2)+1].sumLR; 
  
  seg_Tree[pos].minRL = min(seg_Tree[(pos*2)+1].minRL , seg_Tree[(pos*2)+1].sumRL + seg_Tree[pos*2].minRL);
  seg_Tree[pos].sumRL = 
  seg_Tree[(pos*2)+1].sumRL + seg_Tree[pos*2].sumRL; 

  return;
}

Vote find_Ans(LL i, LL j, LL lo, LL hi, LL pos)
{
  Vote ans;
  ans.minLR = INF;
  ans.sumLR = 0;
  ans.minRL = INF;
  ans.sumRL = 0;
  if(i > j || lo > hi || j < lo || hi < i)return ans;
  else if(i <= lo && hi <= j)return ans = seg_Tree[pos];
  else
  {
    LL mid = lo + ( (hi-lo) / 2);
    Vote A = find_Ans(i, j, lo, mid, pos*2);
    Vote B = find_Ans(i, j, mid+1, hi, (pos*2) + 1);

    ans.minLR = min(A.minLR , A.sumLR + B.minLR);
    ans.sumLR = A.sumLR + B.sumLR; 

    ans.minRL = min(B.minRL , B.sumRL + A.minRL);
    ans.sumRL = B.sumRL + A.sumRL; 
    
    return ans;
  }
}

int main(void)
{
  /****
  for(LL i0 = 0; i0 < MAXN * 4; i0++)
  {
    seg_Tree[i0].minLR = INF;
    seg_Tree[i0].sumLR = 0;
    seg_Tree[i0].minRL = INF;
    seg_Tree[i0].sumRL = 0;
  }
  ****/
  cin >> n;
  for(LL i0 = 1; i0 <= n; i0++)
  {
    cin >> election[i0];
    //cout << election[i0];
  }
  //cout << endl;
  built_Tree(1, n, 1);
  /****
  LL skip = 2;
  for(LL i0 = 1; i0 <= 4*n; i0++)
  {
    cout << "(" << seg_Tree[i0].minLR << ":" << seg_Tree[i0].minRL << ") ";
    if(i0+1 == skip)
    {
      cout << endl;
      skip *= 2;
    }
  }
  cout << endl;
  ****/
  cin >> q;
  for(LL i0 = 0; i0 < q; i0++)
  {
    LL i, j;
    cin >> i >> j;
    Vote ans = find_Ans(i, j, 1, n, 1);
    LL temp = min(ans.minLR, ans.minRL);
    if(temp > 0)temp = 0;
    cout << abs(temp) << endl;
    //Find Answer
    //cout << "Ya" << endl;
  }
  return 0;
}

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