oj.uz

Submission #105890

# Submission time Handle Problem Language Result Execution time Memory
105890 2019-04-15T15:07:57 Z IOrtroiii Election (BOI18_election) C++14
100 / 100
 990 ms 46372 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 500500;

int n;
char s[N];

struct Data {
  int sum, suf;
};

Data t[N << 2];

Data mrg(Data l, Data r) {
  Data ans;
  ans.sum = l.sum + r.sum;
  ans.suf = min(r.suf, r.sum + l.suf);
  return ans;
}

void upd(int v,int l,int r,int p,int x) {
  if (l == r) {
    t[v].sum = x;
    t[v].suf = min(x, 0);
    return;
  }
  int md = (l + r) >> 1;
  if (p <= md) upd(v << 1, l, md, p, x);
  else upd(v << 1 | 1, md + 1, r, p, x);
  t[v] = mrg(t[v << 1], t[v << 1 | 1]);
}

Data get(int v,int l,int r,int L,int R) {
  if (L <= l && r <= R) return t[v];
  int md = (l + r) >> 1;
  Data ans = {0, 0};
  if (L <= md) ans = mrg(ans, get(v << 1, l, md, L, R));
  if (R > md) ans = mrg(ans, get(v << 1 | 1, md + 1, r, L, R));
  return ans;
}

int ft[N];

void add(int p,int v) { for (; p <= n; p += p & -p) ft[p] += v; }
int get(int p) { int ans = 0; for (; p > 0; p -= p & -p) ans += ft[p]; return ans; }
int get(int l,int r) { return get(r) - get(l - 1); }

int ans[N];
vector< pair<int, int> > queryAt[N];

int main() {
  scanf("%d %s", &n, s + 1);
  int m;
  scanf("%d", &m);
  for (int i = 1; i <= m; ++i) {
    int l, r;
    scanf("%d %d", &l, &r);
    queryAt[l].push_back(make_pair(r, i));
  }
  vector<int> delt;
  for (int i = n; i > 0; --i) {
    if (s[i] == 'T') {
      add(i, 1);
      delt.push_back(i);
    } else {
      upd(1, 1, n, i, 1);
      if (delt.size()) {
        add(delt.back(), -1);
        upd(1, 1, n, delt.back(), -1);
        delt.pop_back();
      }
    }
    for (auto q : queryAt[i]) {
      ans[q.second] = get(i, q.first) - get(1, 1, n, i, q.first).suf;
    }
  }
  for (int i = 1; i <= m; ++i) {
    printf("%d\n", ans[i]);
  }
}

Compilation message

election.cpp: In function 'int main()':
election.cpp:54:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %s", &n, s + 1);
   ~~~~~^~~~~~~~~~~~~~~~~~~~
election.cpp:56:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &m);
   ~~~~~^~~~~~~~~~
election.cpp:59:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &l, &r);
     ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 12288 KB Output is correct
2 Correct 17 ms 12160 KB Output is correct
3 Correct 20 ms 12160 KB Output is correct
4 Correct 16 ms 12160 KB Output is correct
5 Correct 17 ms 12260 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 12288 KB Output is correct
2 Correct 17 ms 12160 KB Output is correct
3 Correct 20 ms 12160 KB Output is correct
4 Correct 16 ms 12160 KB Output is correct
5 Correct 17 ms 12260 KB Output is correct
6 Correct 119 ms 16540 KB Output is correct
7 Correct 95 ms 16936 KB Output is correct
8 Correct 128 ms 17072 KB Output is correct
9 Correct 126 ms 17352 KB Output is correct
10 Correct 108 ms 17272 KB Output is correct
11 Correct 133 ms 17684 KB Output is correct
12 Correct 104 ms 17588 KB Output is correct
13 Correct 129 ms 17316 KB Output is correct
14 Correct 129 ms 17484 KB Output is correct
15 Correct 106 ms 17400 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 12288 KB Output is correct
2 Correct 17 ms 12160 KB Output is correct
3 Correct 20 ms 12160 KB Output is correct
4 Correct 16 ms 12160 KB Output is correct
5 Correct 17 ms 12260 KB Output is correct
6 Correct 119 ms 16540 KB Output is correct
7 Correct 95 ms 16936 KB Output is correct
8 Correct 128 ms 17072 KB Output is correct
9 Correct 126 ms 17352 KB Output is correct
10 Correct 108 ms 17272 KB Output is correct
11 Correct 133 ms 17684 KB Output is correct
12 Correct 104 ms 17588 KB Output is correct
13 Correct 129 ms 17316 KB Output is correct
14 Correct 129 ms 17484 KB Output is correct
15 Correct 106 ms 17400 KB Output is correct
16 Correct 990 ms 45100 KB Output is correct
17 Correct 750 ms 40980 KB Output is correct
18 Correct 802 ms 42128 KB Output is correct
19 Correct 790 ms 43804 KB Output is correct
20 Correct 933 ms 44180 KB Output is correct
21 Correct 961 ms 46372 KB Output is correct
22 Correct 948 ms 45360 KB Output is correct
23 Correct 910 ms 44568 KB Output is correct
24 Correct 887 ms 44324 KB Output is correct
25 Correct 946 ms 44200 KB Output is correct