Submission #106390

#	Time	Username	Problem	Language	Result	Execution time	Memory
106390		Hideo	Election (BOI18_election)	C++14	0 / 100	17 ms	16000 KiB

election

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

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

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

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

struct T{
    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];
        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]);
        }
    }
    int get (int v, int l, int r, int ql, int qr){
        if (l >= ql && r <= qr)
            return t[v];
        if (r < ql || l > qr)
            return 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 l, r;
        scanf("%d%d", &l, &r);
        printf("%d\n", abs(min(0, min(tree[0].get(1, 1, n, l, r) - pr[0][l - 1], tree[1].get(1, 1, n, l, r) - pr[1][r + 1]))));
    }
}

Compilation message (stderr)

election.cpp:46:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
election.cpp: In function 'int main()':
election.cpp:68: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: 0 / 28
• Subtask 2: 0 / 54
• Subtask 3: 0 / 18