oj.uz

Submission #83239

# Submission time Handle Problem Language Result Execution time Memory
83239 2018-11-06T10:02:24 Z polyfish Election (BOI18_election) C++14
100 / 100
 1326 ms 135256 KB 
//Pantyhose(black) + glasses = infinity

#include <bits/stdc++.h>
using namespace std;

#define debug(x) cerr << #x << " = " << x << '\n';
#define BP() cerr << "OK!\n";
#define PR(A, n) {cerr << #A << " = "; for (int _=1; _<=n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define PR0(A, n) {cerr << #A << " = "; for (int _=0; _<n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define FILE_NAME "data"

const int INF = 1e9;
const int MAX_N = 500002;

class segment_tree {
public:
    vector<pair<int, int> > st;
    int n;

    segment_tree(int _n) {
        n = _n;
        st.resize(4*n, make_pair(0, 0));
    }

    void down(int id) {
        int tmp = st[id].second;
        st[id].second = 0;
        st[id*2].first += tmp;
        st[id*2].second += tmp;
        st[id*2+1].first += tmp;
        st[id*2+1].second += tmp;
    }

    void upd(int u, int v, int val, int l, int r, int id) {
        if (v<l || u>r)
            return;
        if (u<=l && r<=v) {
            st[id].first += val;
            st[id].second += val;
            return;
        }
        int mid = (l + r) / 2;
        down(id);
        upd(u, v, val, l, mid, id*2);
        upd(u, v, val, mid+1, r, id*2+1);
        st[id].first = min(st[id*2].first, st[id*2+1].first);
    }

    int get(int u, int v, int l, int r, int id) {
        if (v<l || u>r)
            return INF;
        if (u<=l && r<=v)
            return st[id].first;
        int mid = (l + r) / 2;
        down(id);
        return min(get(u, v, l, mid, id*2),
                   get(u, v, mid+1, r, id*2+1));
    }
    void upd(int u, int v, int val) {
        upd(u, v, val, 1, n, 1);
    }

    int get(int u, int v) {
        return get(u, v, 1, n, 1);
    }
};

int n, nQueries, a[MAX_N], suff_sum[MAX_N], pref_sum[MAX_N], res[MAX_N];
vector<pair<int, int> > q[MAX_N];
string S;

void enter() {
    cin >> n >> S >> nQueries;
    S = '@' + S;
    for (int i=1; i<=nQueries; ++i) {
        int l, r;
        cin >> l >> r;
        q[l].push_back(make_pair(r, i));
    }
}

void init() {
}

void solve() {
    segment_tree tr(n);
    for (int i=1; i<=n; ++i)
        a[i] = S[i]=='T' ? -1 : 1;
    for (int i=1; i<=n; ++i)
        suff_sum[i] = suff_sum[i-1] + a[i];
    for (int i=n; i>=1; --i) {
        pref_sum[i] = pref_sum[i+1] + a[i];
        tr.upd(i, i, pref_sum[i]);
    }
    vector<int> p;
    for (int l=n; l>=1; --l) {
        if (a[l]==-1) {
            p.push_back(l);
            tr.upd(1, l, 1);
            //debug(tr.get(3, 8));
        }
        else {
            while (p.size() && suff_sum[p.back()] - suff_sum[l-1] >= 0) {
                tr.upd(1, p.back(), -1);
                //debug(tr.get(3, 8));
                p.pop_back();
            }
        }
        for (int j=0; j<q[l].size(); ++j) {
            int r = q[l][j].first;
            //debug(tr.get(r+1, r+1));
            if (r<n)
                res[q[l][j].second] = max(0, -(tr.get(l, r) - tr.get(r+1, r+1)))
                                    + upper_bound(p.rbegin(), p.rend(), r) - p.rbegin();
            else
                res[q[l][j].second] = max(0, -tr.get(l, r)) +
                                    upper_bound(p.rbegin(), p.rend(), r) - p.rbegin();
        }
    }
    for (int i=1; i<=nQueries; ++i)
        cout << res[i] << '\n';
}

int main() {
	#ifdef GLASSES_GIRL
		freopen(FILE_NAME".inp", "r", stdin);
		freopen(FILE_NAME".out", "w", stdout);
	#endif
	ios::sync_with_stdio(0); cin.tie(0);
    enter();
    solve();
}

Compilation message

election.cpp: In function 'void solve()':
election.cpp:109:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j=0; j<q[l].size(); ++j) {
                       ~^~~~~~~~~~~~

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 12280 KB Output is correct
2 Correct 19 ms 12572 KB Output is correct
3 Correct 15 ms 12592 KB Output is correct
4 Correct 15 ms 12612 KB Output is correct
5 Correct 15 ms 12636 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 12280 KB Output is correct
2 Correct 19 ms 12572 KB Output is correct
3 Correct 15 ms 12592 KB Output is correct
4 Correct 15 ms 12612 KB Output is correct
5 Correct 15 ms 12636 KB Output is correct
6 Correct 132 ms 18564 KB Output is correct
7 Correct 110 ms 19000 KB Output is correct
8 Correct 142 ms 20136 KB Output is correct
9 Correct 144 ms 21240 KB Output is correct
10 Correct 136 ms 22284 KB Output is correct
11 Correct 144 ms 23532 KB Output is correct
12 Correct 135 ms 24412 KB Output is correct
13 Correct 141 ms 25488 KB Output is correct
14 Correct 133 ms 26284 KB Output is correct
15 Correct 126 ms 27264 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 12280 KB Output is correct
2 Correct 19 ms 12572 KB Output is correct
3 Correct 15 ms 12592 KB Output is correct
4 Correct 15 ms 12612 KB Output is correct
5 Correct 15 ms 12636 KB Output is correct
6 Correct 132 ms 18564 KB Output is correct
7 Correct 110 ms 19000 KB Output is correct
8 Correct 142 ms 20136 KB Output is correct
9 Correct 144 ms 21240 KB Output is correct
10 Correct 136 ms 22284 KB Output is correct
11 Correct 144 ms 23532 KB Output is correct
12 Correct 135 ms 24412 KB Output is correct
13 Correct 141 ms 25488 KB Output is correct
14 Correct 133 ms 26284 KB Output is correct
15 Correct 126 ms 27264 KB Output is correct
16 Correct 1161 ms 66384 KB Output is correct
17 Correct 968 ms 69944 KB Output is correct
18 Correct 1123 ms 78344 KB Output is correct
19 Correct 1044 ms 87448 KB Output is correct
20 Correct 1100 ms 95296 KB Output is correct
21 Correct 1326 ms 105708 KB Output is correct
22 Correct 1143 ms 112688 KB Output is correct
23 Correct 1256 ms 121468 KB Output is correct
24 Correct 1260 ms 128532 KB Output is correct
25 Correct 1133 ms 135256 KB Output is correct