Submission #261404

#	Time	Username	Problem	Language	Result	Execution time	Memory
261404		Falcon	Election (BOI18_election)	C++14	100 / 100	618 ms	45168 KiB

election

#pragma GCC optimize("O2")

#include <bits/stdc++.h>
#ifdef DEBUG
    #include "debug.hpp"
#endif

using namespace std;

#define all(c) (c).begin(), (c).end()
#define traverse(c, it) for(auto it = (c).begin(); it != (c).end(); it++)
#define rep(i, N) for(int i = 0; i < (N); i++)
#define rep1(i, N) for(int i = 1; i <= (N); i++)
#define rep2(i, s, e) for(int i = (s); i <= (e); i++)
#define rep3(i, s, e, d) for(int i = (s); (d) >= 0 ? i <= (e) : i >= (e); i += (d))
#define pb push_back


#ifdef DEBUG
    #define debug(x...) {dbg::depth++; string dbg_vals = dbg::to_string(x); dbg::depth--; dbg::fprint(__func__, __LINE__, #x, dbg_vals);}
    #define light_debug(x) {dbg::light = 1; dbg::dout << __func__ << ":" << __LINE__ << "  " << #x << " = " << x << endl; dbg::light = 0;}
#else
    #define debug(x...)
    #define light_debug(x) 
#endif

template<typename T>
T& ckmin(T& a, T b){ return a = a > b ? b : a; }

template<typename T>
T& ckmax(T& a, T b){ return a = a < b ? b : a; }

using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;

namespace ioUtils {

    char vector_delimiter = ' ';

    template<typename T>
    istream& operator >>(istream&, vector<T>&);

    template<typename... Ts>
    istream& operator >>(istream& is, pair<Ts...>& p){
        is >> p.first >> p.second;
        return is;
    }

    template<typename T> 
    istream& operator >>(istream& is, vector<T>& v){
        for(auto& e : v) is >> e;
	       return is;
    }

    template<typename T>
    ostream& operator <<(ostream&, vector<T>&);

    template<typename... Ts>
    ostream& operator <<(ostream& os, pair<Ts...>& p){
        os << p.first << " " << p.second;
        return os;
    }

    template<typename T>
    ostream& operator <<(ostream& os, vector<T>& v){
        for(auto&& e : v) os << e << vector_delimiter;
        return os;   
    }   
}

using namespace ioUtils;


template<int n>
class segtree{
	struct node{
		int sum, max_suff;

		node(int v = 0){
			max_suff = max(0, sum = v);
		}

		node operator +(node x){
			ckmax(x.max_suff, max_suff + x.sum), x.sum += sum;
			return x;
		}
	};

	array<node, n << 1> seg;

public:
	void update(int i, int v){
		for(seg[i += n] = v, i >>= 1; i; i >>= 1)
			seg[i] = seg[i << 1] + seg[i << 1 | 1];
	}

	int query(int s, int e){
		node l, r;
		for(s += n, e += n; s < e; s >>= 1, e >>= 1){
			if(s & 1) l = l + seg[s++];
			if(e & 1) r = seg[--e] + r;
		}
		return (l + r).max_suff;
	}
};


struct query{
	int l, r, i;
};

const int MAX_N = 500000;

int N, Q;
vector<query> queries[MAX_N];
segtree<MAX_N> seg;
string s;

signed main(){

    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    #ifdef DEBUG
        freopen("debug", "w", stderr);
    #endif
    
    cin >> N >> s >> Q;
    rep(i, Q){
    	int l, r;
    	cin >> l >> r;
    	--l;
    	queries[l].pb({l, r, i});
    }

    vi Ts, ans(Q);
    rep3(i, N - 1, 0, -1){
    	if(s[i] == 'C'){
    		seg.update(i, -1);
    		if(!Ts.empty()) 
    			seg.update(Ts.back(), 1), Ts.pop_back();
    	} else 
    		Ts.pb(i);
    	for(auto&& q : queries[i])
    		ans[q.i] = Ts.size() - (upper_bound(all(Ts), q.r, greater<int>()) - Ts.begin()) + seg.query(i, q.r);
    }

    vector_delimiter = '\n';
    cout << ans;

    #ifdef DEBUG
        dbg::dout << "\nExecution time: " << clock() << "ms\n";
    #endif

    return 0;
}

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