Submission #769993

#	Time	Username	Problem	Language	Result	Execution time	Memory
769993		emad234	Election (BOI18_election)	C++17	0 / 100	1 ms	468 KiB

election

#include <bits/stdc++.h>
#define all(v) ((v).bvin(),(v).end())
#define ll long long
using namespace std;
const ll mod = 1e9 + 7;
const ll mxN = 8e6 + 1;
struct tree{
  int Cdec,Cinc,Tdec,Tinc,Pinc,Pdec,Pall,Tnum;
};
tree seg[mxN];
int N,s,e;
tree combine(tree a, tree b){
  tree c;
  c.Tnum = a.Tnum + b.Tnum;
  c.Cinc = max(a.Cinc - b.Tinc,0) + b.Cinc;
  c.Cdec = max(b.Cdec - a.Tdec,0) + a.Cdec;
  c.Tinc = max(b.Tinc - a.Cinc,0) + a.Tinc;
  c.Tdec = max(a.Tdec - b.Cdec,0) + b.Tdec;
  c.Pinc = a.Pinc + b.Pinc + min(a.Cinc,b.Tinc);
  c.Pdec = b.Pdec + a.Pdec + min(b.Cdec,a.Tdec);
  c.Pall = min(a.Pinc + min({a.Cinc,max((b.Tinc - b.Tdec),0)}) + b.Pall,b.Pdec + min({b.Cdec,max((a.Tdec - a.Tinc),0)}) + a.Pall) ;
  return c;
}
tree query(int l = 1,int r = N,int ind = 1){
  if(l > e || r < s) return {0,0,0,0,0,0,0};
  if(l >= s && r <= e) return seg[ind];
  int md = (l + r) / 2;
  return combine(query(l,md,ind * 2),query(md + 1,r,ind * 2 + 1));
}
void printseg(){
  int p2 = 1;
  for(int i = 1;i <= N * 2 - 1;i++){
    cout<<'{'<<seg[i].Cinc<<','<<seg[i].Cdec<<','<<seg[i].Tinc<<','<<seg[i].Tdec<<','<<seg[i].Tnum<<','<<seg[i].Pinc<<','<<seg[i].Pdec<<','<<seg[i].Pall<<"} ";
    if(i == p2 * 2 - 1){
      cout<<'\n';
      p2 *= 2;
    }
  }
}
signed main()
{
  ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  int n,q;
  string s;
  cin >>n>>s>>q;
  N = exp2(ceil(log2(n)));
  for(int i = 0;i < n;i++){
    if(s[i] == 'C'){
      seg[i + N].Cinc = 1;
      seg[i + N].Cdec = 1;
    }else{
      seg[i + N].Tinc = 1;
      seg[i + N].Tdec = 1;
      seg[i + N].Tnum = 1;
    }
  }
  for(int i = N - 1;i;i--){
    seg[i] = combine(seg[i * 2],seg[i * 2 + 1]);
  }
  // printseg();
  while(q--){
    cin>>s>>e;
    tree qe = query();
    cout<<qe.Tnum - qe.Pall<<'\n';
  }
}

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