oj.uz

Submission #69593

# Submission time Handle Problem Language Result Execution time Memory
69593 2018-08-21T09:28:22 Z octopuses Election (BOI18_election) C++17
100 / 100
 1525 ms 83376 KB 
//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

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.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 18168 KB Output is correct
2 Correct 18 ms 18268 KB Output is correct
3 Correct 20 ms 18464 KB Output is correct
4 Correct 22 ms 18464 KB Output is correct
5 Correct 23 ms 18464 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 18168 KB Output is correct
2 Correct 18 ms 18268 KB Output is correct
3 Correct 20 ms 18464 KB Output is correct
4 Correct 22 ms 18464 KB Output is correct
5 Correct 23 ms 18464 KB Output is correct
6 Correct 152 ms 23164 KB Output is correct
7 Correct 157 ms 23164 KB Output is correct
8 Correct 144 ms 23740 KB Output is correct
9 Correct 153 ms 24972 KB Output is correct
10 Correct 145 ms 26044 KB Output is correct
11 Correct 156 ms 27120 KB Output is correct
12 Correct 169 ms 28068 KB Output is correct
13 Correct 158 ms 29016 KB Output is correct
14 Correct 151 ms 29912 KB Output is correct
15 Correct 138 ms 30912 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 18168 KB Output is correct
2 Correct 18 ms 18268 KB Output is correct
3 Correct 20 ms 18464 KB Output is correct
4 Correct 22 ms 18464 KB Output is correct
5 Correct 23 ms 18464 KB Output is correct
6 Correct 152 ms 23164 KB Output is correct
7 Correct 157 ms 23164 KB Output is correct
8 Correct 144 ms 23740 KB Output is correct
9 Correct 153 ms 24972 KB Output is correct
10 Correct 145 ms 26044 KB Output is correct
11 Correct 156 ms 27120 KB Output is correct
12 Correct 169 ms 28068 KB Output is correct
13 Correct 158 ms 29016 KB Output is correct
14 Correct 151 ms 29912 KB Output is correct
15 Correct 138 ms 30912 KB Output is correct
16 Correct 1417 ms 62536 KB Output is correct
17 Correct 1250 ms 66312 KB Output is correct
18 Correct 1255 ms 74544 KB Output is correct
19 Correct 1012 ms 80556 KB Output is correct
20 Correct 1443 ms 81192 KB Output is correct
21 Correct 1390 ms 83084 KB Output is correct
22 Correct 1425 ms 83084 KB Output is correct
23 Correct 1525 ms 83376 KB Output is correct
24 Correct 1387 ms 83376 KB Output is correct
25 Correct 1444 ms 83376 KB Output is correct