oj.uz

Submission #61554

# Submission time Handle Problem Language Result Execution time Memory
61554 2018-07-26T07:32:13 Z 강태규(#1777) Election (BOI18_election) C++11
100 / 100
 875 ms 20804 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>

using namespace std;
typedef long long llong;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;

int n, q;
struct query {
    int l, r, i;
    void scan(int idx) {
        scanf("%d%d", &l, &r);
        i = idx;
    }
    bool operator<(const query &p) const {
        return r < p.r;
    }
} qs[500000];

struct node {
    int sum, pre;
    node() : sum(0), pre(0) {}
    node(int x) : sum(x), pre(min(x, 0)) {}
    node(int x, int y) : sum(x), pre(y) {}
    node operator+(const node &p) const {
        return node(sum + p.sum, min(pre, sum + p.pre));
    }
} seg[1 << 20];

void update(int i, int s, int e, int x, int v) {
    if (s == e) {
        seg[i] = node(v);
        return;
    }
    int m = (s + e) / 2;
    if (x <= m) update(i << 1, s, m, x, v);
    else update(i << 1 | 1, m + 1, e, x, v);
    seg[i] = seg[i << 1] + seg[i << 1 | 1];
}

node query(int i, int s, int e, int x, int y) {
    if (e < x || y < s) return node(0);
    if (x <= s && e <= y) return seg[i];
    int m = (s + e) / 2;
    return query(i << 1, s, m, x, y) + query(i << 1 | 1, m + 1, e, x, y);
}

int countGreater(vector<int> &v, int x) {
    return v.size() - (lower_bound(v.begin(), v.end(), x) - v.begin());
}

char str[500001];
int ans[500000];
int main() {
    scanf("%d%s%d", &n, str, &q);
    for (int i = 0; i < q; ++i) {
        qs[i].scan(i);
    }
    sort(qs, qs + q);
    vector<int> dec;
    for (int i = 0, j = 1; i < q; ++i) {
        while (j <= qs[i].r) {
            if (str[j - 1] == 'C') {
                if (!dec.empty()) {
                    update(1, 1, n, dec.back(), -1);
                    dec.pop_back();
                }
                update(1, 1, n, j, 1);
            }
            else dec.push_back(j);
            ++j;
        }
        ans[qs[i].i] = countGreater(dec, qs[i].l)
                        - query(1, 1, n, qs[i].l, qs[i].r).pre;
    }
    
    for (int i = 0; i < q; ++i) {
        printf("%d\n", ans[i]);
    }
	return 0;
}

Compilation message

election.cpp: In function 'int main()':
election.cpp:68:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%s%d", &n, str, &q);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
election.cpp: In member function 'void query::scan(int)':
election.cpp:25:14: 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 12 ms 8696 KB Output is correct
2 Correct 12 ms 8696 KB Output is correct
3 Correct 11 ms 8728 KB Output is correct
4 Correct 12 ms 8784 KB Output is correct
5 Correct 11 ms 8784 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 8696 KB Output is correct
2 Correct 12 ms 8696 KB Output is correct
3 Correct 11 ms 8728 KB Output is correct
4 Correct 12 ms 8784 KB Output is correct
5 Correct 11 ms 8784 KB Output is correct
6 Correct 108 ms 10244 KB Output is correct
7 Correct 81 ms 10244 KB Output is correct
8 Correct 85 ms 10244 KB Output is correct
9 Correct 85 ms 10244 KB Output is correct
10 Correct 85 ms 10244 KB Output is correct
11 Correct 130 ms 10472 KB Output is correct
12 Correct 104 ms 10472 KB Output is correct
13 Correct 125 ms 10588 KB Output is correct
14 Correct 87 ms 10588 KB Output is correct
15 Correct 99 ms 10588 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 8696 KB Output is correct
2 Correct 12 ms 8696 KB Output is correct
3 Correct 11 ms 8728 KB Output is correct
4 Correct 12 ms 8784 KB Output is correct
5 Correct 11 ms 8784 KB Output is correct
6 Correct 108 ms 10244 KB Output is correct
7 Correct 81 ms 10244 KB Output is correct
8 Correct 85 ms 10244 KB Output is correct
9 Correct 85 ms 10244 KB Output is correct
10 Correct 85 ms 10244 KB Output is correct
11 Correct 130 ms 10472 KB Output is correct
12 Correct 104 ms 10472 KB Output is correct
13 Correct 125 ms 10588 KB Output is correct
14 Correct 87 ms 10588 KB Output is correct
15 Correct 99 ms 10588 KB Output is correct
16 Correct 854 ms 19088 KB Output is correct
17 Correct 662 ms 19228 KB Output is correct
18 Correct 775 ms 19276 KB Output is correct
19 Correct 634 ms 19276 KB Output is correct
20 Correct 814 ms 19276 KB Output is correct
21 Correct 850 ms 20644 KB Output is correct
22 Correct 831 ms 20644 KB Output is correct
23 Correct 875 ms 20804 KB Output is correct
24 Correct 746 ms 20804 KB Output is correct
25 Correct 770 ms 20804 KB Output is correct