Submission #166431

#	Time	Username	Problem	Language	Result	Execution time	Memory
166431		egekabas	Election (BOI18_election)	C++14	0 / 100	4 ms	504 KiB

election

#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long   ll;
typedef unsigned long long   ull;
typedef long double ld;
typedef pair<ll, ll>    pll;
typedef pair<ull, ull>    pull;
typedef pair<int, int>  pii;
typedef pair<ld, ld>  pld;
int input(){
    char c;
    cin >> c;
    if(c == 'T')
        return -1;
    else
        return 1;
}
int n;
int a[500009];
struct node{
    int minl, minli, minr, minri, rid, sum, tl, tr;
};
void print(node a){
    cout << a.minl << " " << a.minli << " " << a.minr << " " << a.minri << "\n";
}
node tree[2000009];
node merge(node a, node b){
    //print(a);print(b);
    if(b.minl == 1e9)
        return a;
    if(a.minl == 1e9)
        return b;
    
    node ret;
    a.minr += b.sum;
    b.minl += a.sum;
    if(b.minli == b.tl)
        b.minli = a.rid;
    ret.sum = a.sum+b.sum;
    if(b.rid == b.tl)
        ret.rid = a.rid;
    else
        ret.rid = b.rid;
    ret.tl = a.tl;
    if(a.minl < b.minl){
        ret.minl = a.minl;
        ret.minli = a.minli;
    }
    else if(a.minl > b.minl){
        ret.minl = b.minl;
        ret.minli = b.minli;
    }
    else{
        ret.minl = a.minl;
        ret.minli = min(a.minli, b.minli);
    }
    
    if(a.minr < b.minr){
        ret.minr = a.minr;
        ret.minri = a.minri;
    }
    else if(a.minr > b.minr){
        ret.minr = b.minr;
        ret.minri = b.minri;
    }
    else{
        ret.minr = a.minr;
        ret.minri = max(a.minri, b.minri);
    }
    //print(ret); cout << "-----------------\n";
    return ret;
}
void build(int v, int tl, int tr){
    if(tl > tr)
        return;
    if(tl == tr){
        tree[v].minl = tree[v].minr = a[tl];
        tree[v].minli = tree[v].minri = tl;
        if(a[tl] < 0)
            tree[v].rid = tl;
        else
            tree[v].rid = tl+1;
        tree[v].sum = a[tl];
        tree[v].tl = tl;
        //cout << tl <<  "\n";
        //print(tree[v]);
    }
    else{
        int tm = (tl+tr)/2;
        build(2*v, tl, tm);
        build(2*v+1, tm+1, tr);
        tree[v] = merge(tree[2*v], tree[2*v+1]);
        //cout << tl << " " << tr << "\n";
        //print(tree[v]);
    }
}
node get(int v, int tl, int tr, int l, int r){
    if(tl > r || tr < l)
        return {(int)1e9};
    else if(tl >= l && tr <= r)
        return tree[v];
    else{
        int tm = (tl+tr)/2;
        node node1 = get(2*v, tl, tm, l, r);
        node node2 = get(2*v+1, tm+1, tr, l, r);
        return merge(node1, node2);        
    }
}
int gor[500009];
int gol[500009];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    
    cin >> n;
    for(int i = 0; i < n; ++i)
        a[i] = input();
    for(int i = 1; i < n; ++i){
        if(a[i] > 0)
            gol[i] = i;
        else
            gol[i] = gol[i-1];
    }
    gor[n-1] = n-1;
    for(int i = n-2; i >= 0; --i){
        if(a[i] > 0)
            gor[i] = i;
        else
            gor[i] = gor[i+1];
    }
    build(1, 0, n-1);
    //print(tree[1]);
    int q;
    cin >> q;
    while(q--){
        int l, r;
        cin >> l >> r;
        --l, --r;
        int l1 = gor[l];
        int r1 = gol[r];
        if(l1 > r1)
            cout << (l-r+1) << "\n";
        int add = l1-l + r-r1;
        node cur = get(1, 0, n-1, l1, r1);
        if(cur.minli == cur.minri)
            cout << add+max(0, max(-cur.minl, -cur.minr)) << "\n";
        else
            cout << add+max(0, -cur.minl)+max(0, -cur.minr) << "\n";
    }
}

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