oj.uz

Submission #202226

# Submission time Handle Problem Language Result Execution time Memory
202226 2020-02-14T09:19:27 Z stefdasca Election (BOI18_election) C++14
100 / 100
 1016 ms 44064 KB 
#include<bits/stdc++.h>
#define god dimasi5eks
#pragma GCC optimize("O3")
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define mod 1000000007
#define dancila 3.14159265359
#define eps 1e-9

using namespace std;

typedef long long ll;

int n, q;

string s;

int aint[2000002], lazy[2000002], ans[500002];

vector<pair<int, int> >qu[500002];
void lz(int nod, int st, int dr)
{
    aint[nod] += lazy[nod];
    if(st != dr)
    {
        lazy[nod << 1] += lazy[nod];
        lazy[nod << 1|1] += lazy[nod];
    }
    lazy[nod] = 0;
}
void upd(int nod, int st, int dr, int L, int R, int val)
{
    lz(nod, st, dr);
    if(dr < L || st > R)
        return;
    if(L <= st && dr <= R)
    {
        lazy[nod] += val;
        lz(nod, st, dr);
        return;
    }
    int mid = (st + dr) / 2;
    upd(nod << 1, st, mid, L, R, val);
    upd(nod << 1|1, mid+1, dr, L, R, val);
    aint[nod] = min(aint[nod << 1], aint[nod << 1|1]);
}

int query(int nod, int st, int dr, int L, int R)
{
    lz(nod, st, dr);
    if(dr < L || st > R)
        return 100000001;
    if(L <= st && dr <= R)
        return aint[nod];
    int mid = (st + dr) / 2;
    return min(query(nod << 1, st, mid, L, R), query(nod << 1|1, mid+1, dr, L, R));
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    cin >> s;
    s = ' ' + s;
    cin >> q;
    for(int i = 1; i <= q; ++i)
    {
        int a, b;
        cin >> a >> b;
        qu[b].pb({a, i});
    }
    vector<int> d;
    for(int i = 1; i <= n; ++i)
    {
        if(s[i] == 'T')
            d.pb(i);
        else
        {
            if(!d.empty())
            {
                upd(1, 1, n, (int) d.back(), n, -1);
                d.pop_back();
            }
            upd(1, 1, n, i, n, 1);
        }
        for(int j = 0; j < qu[i].size(); ++j)
        {
            int cs = qu[i][j].fi;
            int pz = qu[i][j].se;
            int sol = query(1, 1, n, cs, i);
            if(cs > 1)
                sol -= query(1, 1, n, cs-1, cs-1);
            auto it = lower_bound(d.begin(), d.end(), cs);
            int cnt = (int) d.size() - (it - d.begin());
            ans[pz] = cnt - min(0, sol);
        }
    }
    for(int i = 1; i <= q; ++i)
        cout << ans[i] << '\n';
    return 0;
}

Compilation message

election.cpp: In function 'int main()':
election.cpp:88:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < qu[i].size(); ++j)
                        ~~^~~~~~~~~~~~~~

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12152 KB Output is correct
2 Correct 14 ms 12280 KB Output is correct
3 Correct 14 ms 12156 KB Output is correct
4 Correct 14 ms 12280 KB Output is correct
5 Correct 14 ms 12280 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12152 KB Output is correct
2 Correct 14 ms 12280 KB Output is correct
3 Correct 14 ms 12156 KB Output is correct
4 Correct 14 ms 12280 KB Output is correct
5 Correct 14 ms 12280 KB Output is correct
6 Correct 114 ms 17012 KB Output is correct
7 Correct 100 ms 16628 KB Output is correct
8 Correct 105 ms 16756 KB Output is correct
9 Correct 102 ms 17012 KB Output is correct
10 Correct 120 ms 16884 KB Output is correct
11 Correct 114 ms 17268 KB Output is correct
12 Correct 116 ms 17396 KB Output is correct
13 Correct 115 ms 17396 KB Output is correct
14 Correct 123 ms 17140 KB Output is correct
15 Correct 112 ms 17008 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12152 KB Output is correct
2 Correct 14 ms 12280 KB Output is correct
3 Correct 14 ms 12156 KB Output is correct
4 Correct 14 ms 12280 KB Output is correct
5 Correct 14 ms 12280 KB Output is correct
6 Correct 114 ms 17012 KB Output is correct
7 Correct 100 ms 16628 KB Output is correct
8 Correct 105 ms 16756 KB Output is correct
9 Correct 102 ms 17012 KB Output is correct
10 Correct 120 ms 16884 KB Output is correct
11 Correct 114 ms 17268 KB Output is correct
12 Correct 116 ms 17396 KB Output is correct
13 Correct 115 ms 17396 KB Output is correct
14 Correct 123 ms 17140 KB Output is correct
15 Correct 112 ms 17008 KB Output is correct
16 Correct 1012 ms 41876 KB Output is correct
17 Correct 742 ms 39072 KB Output is correct
18 Correct 871 ms 40204 KB Output is correct
19 Correct 834 ms 41628 KB Output is correct
20 Correct 971 ms 40992 KB Output is correct
21 Correct 1016 ms 43676 KB Output is correct
22 Correct 970 ms 42912 KB Output is correct
23 Correct 987 ms 44064 KB Output is correct
24 Correct 991 ms 43296 KB Output is correct
25 Correct 982 ms 42084 KB Output is correct