Submission #106750

#	Time	Username	Problem	Language	Result	Execution time	Memory
106750		Hideo	Election (BOI18_election)	C++14	0 / 100	31 ms	31736 KiB

election

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

#define ll long long
#define pb push_back
#define mk make_pair
#define fr first
#define sc second
#define vi vector < int >
#define vl vector < ll >
#define pi pair < int, int >
#define pii pair < int, pi >
#define vii vector < pi >

const int N = 5e5 + 7;
const int INF = 1e9 + 7;

int pr[2][N];
int n, q;
string s;

pi temp;

struct T{
    pair < int, int > t[4 * N];
    T(){
        memset(t, 0, sizeof t);
    }
    void build (int v, int l, int r, int id){
        if (l == r)
            t[v] = {pr[id][l], l};
        else {
            int mid = (l + r) >> 1;
            build(v + v, l, mid, id);
            build(v + v + 1, mid + 1, r, id);
            t[v] = min(t[v + v], t[v + v + 1]);
        }
    }
    pi get (int v, int l, int r, int ql, int qr){
        if (ql <= l && r <= qr)
            return t[v];
        if (r < ql || l > qr)
            return {INF, INF};
        int mid = (l + r) >> 1;
        return min(get(v + v, l, mid, ql, qr), get(v + v + 1, mid + 1, r, ql, qr));
    }
};

T tree[2];

main(){
    cin >> n >> s;
    s = ' ' + s;
    for (int i = 1; i <= n; i++){
        pr[0][i] = pr[0][i - 1];
        if (s[i] == 'C')
            pr[0][i]++;
        else
            pr[0][i]--;
    }
    tree[0].build(1, 1, n, 0);
    for (int i = n; i >= 1; i--){
        pr[1][i] = pr[1][i + 1];
        if (s[i] == 'C')
            pr[1][i]++;
        else
            pr[1][i]--;
    }
    tree[1].build(1, 1, n, 1);
    cin >> q;
    for (int i = 1; i <= q; i++){
        int l1, r1, l2, r2;
        int v1, v2 = 0, v3;
        int y = 0;
        scanf("%d%d", &l1, &r2);
        temp = tree[0].get(1, 1, n, l1, r2);
        temp.fr -= pr[0][l1 - 1];
        r1 = temp.sc;
        l2 = r1 + 1;
        v1 = abs(min(0, temp.fr));
        if (l2 <= r2){
            temp = tree[1].get(1, 1, n, l2, r2);
            temp.fr -= pr[1][r2 + 1];
            v2 = abs(min(0, temp.fr));
            y = pr[1][l2] - pr[1][r2 + 1] + v2;
        }
        temp = tree[1].get(1, 1, n, l1, r1);
        temp.fr -= pr[1][r1 + 1];
        v3 = abs(min(0, temp.fr));
        printf("%d\n", v1 + v2 + max(0, v3 - v1 - y));
    }
}

Compilation message (stderr)

election.cpp:51:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
election.cpp: In function 'int main()':
election.cpp:75:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &l1, &r2);
         ~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 28
• Subtask 2: 0 / 54
• Subtask 3: 0 / 18