Submission #69539

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
69539	2018-08-21T08:25:27 Z	octopuses	Election (BOI18_election)	C++17	0 / 100	15 ms	12152 KB

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;
vector < pair < int, int > > q[N];
int T[3 * N], t[3 * N];

void Build(int v, int tl, int tr)
{
  if(tl == tr - 1)
  {
    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;
    return;
  }
  t[v + v] += t[v];
  t[v + v + 1] += t[v]; t[v] = 0;
  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], T[v + v + 1] + t[v + v + 1]);
}

int get(int v, int tl, int tr, int l, int r)
{
  if(tr <= l || r <= tl) return 0;
  if(l <= tl && tr <= r)
    return T[v] + t[v];
  t[v + v] += t[v];
  t[v + v + 1] += t[v]; t[v] = 0;
  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 = 1; i <= n; ++ i)
  {
    int x = (ch[i - 1] == 'C')?-1:1;
    L[i] = L[i - 1] + x;
  }
  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));
    for(int j = x; j <= y; ++ j)
      answer[i] = max(answer[i], L[j] - L[x - 1]);
  }

  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);
    //cout << "add " << " " << now << endl;
    now = D[now];
  }
  now = 1;
  for(int l = 1; l <= n; ++ l)
  {
    for(int i = 0; i < q[l].size(); ++ i)
      answer[q[l][i].sc] = max(R[q[l][i].fr + 1] + get(1, 1, n + 1, l, q[l][i].fr + 1), answer[q[l][i].sc]);
    if(l == n) break;
    if(ch[l - 1] == 'T')
    {
      update(1, 1, n + 1, l + 1, -1);
      //cout << "rem " << " " << l << endl;
    }
    else
    {
      update(1, 1, n + 1, D[l] + 1, 1);
      //cout << "add " << " " << D[l] << endl;
    }
  }
  for(int i = 1; i <= m; ++ i)
    printf("%d\n", answer[i]);
}

Compilation message

election.cpp: In function 'void Build(int, int, int)':
election.cpp:30:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   Build(v + v, tl, tl + tr >> 1);
                    ~~~^~~~
election.cpp:31: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:45:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   update(v + v, tl, tl + tr >> 1, l, val);
                     ~~~^~~~
election.cpp:46: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:58:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   x = get(v + v, tl, tl + tr >> 1, l, r);
                      ~~~^~~~
election.cpp:59: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:66:18: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[500020]' [-Wformat=]
   scanf("%s", &ch);
               ~~~^
election.cpp:105:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < q[l].size(); ++ i)
                    ~~^~~~~~~~~~~~~
election.cpp:65:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d\n", &n);
   ~~~~~^~~~~~~~~~~~
election.cpp:66:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", &ch);
   ~~~~~^~~~~~~~~~~
election.cpp:78:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &m);
   ~~~~~^~~~~~~~~~
election.cpp:82: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

0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	15 ms	12152 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2

0 / 54.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	15 ms	12152 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3

0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	15 ms	12152 KB	Output isn't correct
2	Halted	0 ms	0 KB	-