Submission #69593

#	Time	Username	Problem	Language	Result	Execution time	Memory
69593		octopuses	Election (BOI18_election)	C++17	100 / 100	1525 ms	83376 KiB

election

//Giorgi Kldiashvili

#include <bits/stdc++.h>

#define ll long long
#define fr first
#define sc second
#define M 1000000007ll

using namespace std;

const int N = 500020;

char ch[N];
bool C[N];
int L[N], R[N], D[N];
int F[2 * N], answer[N];
int n, m;
int A, B;
int K[N];
vector < pair < int, int > > q[N];
int T[3 * N], t[3 * N], tt[3 * N];

void upd(int v, int x)
{
  if(x == 1)
    t[v] = 0;
  else
  {
    t[v + v] += t[v];
    T[v + v] += t[v];
    t[v + v + 1] += t[v];
    T[v + v + 1] += t[v];
    t[v] = 0;
  }
}

void Build(int v, int tl, int tr)
{
  if(tl == tr - 1)
  {
    T[v] = -R[tl];
    t[v] = -R[tl];
    return;
  }
  Build(v + v, tl, tl + tr >> 1);
  Build(v + v + 1, tl + tr >> 1, tr);
  T[v] = max(T[v + v], T[v + v + 1]);
}

void update(int v, int tl, int tr, int l, int val)
{
  if(tr <= l) return;
  if(l <= tl)
  {
    T[v] += val;
    t[v] += val;
    return;
  }
  upd(v, tr - tl);
  update(v + v, tl, tl + tr >> 1, l, val);
  update(v + v + 1, tl + tr >> 1, tr, l, val);
  T[v] = max(T[v + v], T[v + v + 1]);
}

int get(int v, int tl, int tr, int l, int r)
{
  if(r <= tl || tr <= l)
    return -1e9;
  if(l <= tl && tr <= r)
    return T[v];
  int x, y;
  upd(v, tr - tl);
  x = get(v + v, tl, tl + tr >> 1, l, r);
  y = get(v + v + 1, tl + tr >> 1, tr, l, r);
  return max(x, y);
}

void build(int v, int tl, int tr)
{
  if(tl == tr - 1)
  {
    tt[v] = L[tl];
    return;
  }
  build(v + v, tl, tl + tr >> 1);
  build(v + v + 1, tl + tr >> 1, tr);
  tt[v] = max(tt[v + v], tt[v + v + 1]);
}

int Get(int v, int tl, int tr, int l, int r)
{
  if(r <= tl || tr <= l)
    return -1e9;
  if(l <= tl && tr <= r)
    return tt[v];
  int x, y;
  x = Get(v + v, tl, tl + tr >> 1, l, r);
  y = Get(v + v + 1, tl + tr >> 1, tr, l, r);
  return max(x, y);
}

int main()
{
  scanf("%d\n", &n);
  scanf("%s", &ch);
  L[0] = 500002;
  for(int i = 0; i < 3 * N; ++ i)
    T[i] = -1e9;
  for(int i = 1; i <= n; ++ i)
  {
    int x = (ch[i - 1] == 'C')?-1:1;
    L[i] = L[i - 1] + x;
  }
  build(1, 1, n + 1);
  for(int i = n; i >= 1; -- i)
  {
    int x = (ch[i - 1] == 'C')?1:-1;
    R[i] = R[i + 1] + x;
  }
  scanf("%d", &m);
  for(int i = 1; i <= m; ++ i)
  {
    int x, y;
    scanf("%d %d", &x, &y);
    q[x].push_back(make_pair(y, i));
    answer[i] = Get(1, 1, n + 1, x, y + 1) - L[x - 1];
    answer[i] = max(answer[i], 0);
  }

  for(int i = n; i >= 0; -- i)
  {
    D[i] = F[L[i] + 1];
    F[L[i]] = i;
    if(D[i] == 0) D[i] = n + 1;
  }
  Build(1, 1, n + 1);
  int now = D[0];
  while(now != n + 1)
  {
    update(1, 1, n + 1, now + 1, 1);
    now = D[now];
  }
  now = 1;
  for(int l = 1; l <= n; ++ l)
  {
    for(int i = 0; i < q[l].size(); ++ i)
    {
      int FT = get(1, 1, n + 1, l, q[l][i].fr + 1);
      answer[q[l][i].sc] = max(answer[q[l][i].sc], FT + R[q[l][i].fr + 1]);
    }
    if(l == n) break;
    if(ch[l - 1] == 'T')
      update(1, 1, n + 1, l + 1, -1);
    else
      update(1, 1, n + 1, D[l] + 1, 1);
  }
  for(int i = 1; i <= m; ++ i)
    printf("%d\n", answer[i]);
}

Compilation message (stderr)

election.cpp: In function 'void Build(int, int, int)':
election.cpp:46:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   Build(v + v, tl, tl + tr >> 1);
                    ~~~^~~~
election.cpp:47:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   Build(v + v + 1, tl + tr >> 1, tr);
                    ~~~^~~~
election.cpp: In function 'void update(int, int, int, int, int)':
election.cpp:61:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   update(v + v, tl, tl + tr >> 1, l, val);
                     ~~~^~~~
election.cpp:62:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   update(v + v + 1, tl + tr >> 1, tr, l, val);
                     ~~~^~~~
election.cpp: In function 'int get(int, int, int, int, int)':
election.cpp:74:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   x = get(v + v, tl, tl + tr >> 1, l, r);
                      ~~~^~~~
election.cpp:75:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   y = get(v + v + 1, tl + tr >> 1, tr, l, r);
                      ~~~^~~~
election.cpp: In function 'void build(int, int, int)':
election.cpp:86:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   build(v + v, tl, tl + tr >> 1);
                    ~~~^~~~
election.cpp:87:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   build(v + v + 1, tl + tr >> 1, tr);
                    ~~~^~~~
election.cpp: In function 'int Get(int, int, int, int, int)':
election.cpp:98:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   x = Get(v + v, tl, tl + tr >> 1, l, r);
                      ~~~^~~~
election.cpp:99:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   y = Get(v + v + 1, tl + tr >> 1, tr, l, r);
                      ~~~^~~~
election.cpp: In function 'int main()':
election.cpp:106:18: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[500020]' [-Wformat=]
   scanf("%s", &ch);
               ~~~^
election.cpp:147:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < q[l].size(); ++ i)
                    ~~^~~~~~~~~~~~~
election.cpp:105:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d\n", &n);
   ~~~~~^~~~~~~~~~~~
election.cpp:106:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", &ch);
   ~~~~~^~~~~~~~~~~
election.cpp:121:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &m);
   ~~~~~^~~~~~~~~~
election.cpp:125:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &x, &y);
     ~~~~~^~~~~~~~~~~~~~~~~

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