Submission #952611

#	Time	Username	Problem	Language	Result	Execution time	Memory
952611		Danet	Election (BOI18_election)	C++14	0 / 100	100 ms	219560 KiB

election

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

#define Tof_Io  	ios_base::sync_with_stdio(false);cin.tie(0) , cout.tie(0);
#define kill(x)     cout << x << endl, exit(0)
#define all(x) 		x.begin(),x.end()
#define int 		long long int
#define pb			push_back
#define endl 		'\n'
const int N = 4e6 + 23;
const int mod = 998244353; //998244353
const int inf = 1e9 + 2;
vector<int> adj[N];
string str;
priority_queue<pair<int,int> ,vector<pair<int,int>>,greater<pair<int,int>>> pq;
int ans = 0;
vector<int> vc;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};
int p[4] = {'^', '<', 'v', '>'};
/*************************************BUILD*************************************/
/***********************************FcolNCTION***********************************/
int n , q;
string s;
struct node{
    pair<int,int> ty;
    int sum;
    int ans;
};
node seg[N];
void update(int v, int tl, int tr, int pos, int val)
{
    if (tl == tr)
    {
        seg[v].ty.first =  max(seg[v].ty.first, val);
        seg[v].ty.second = max(seg[v].ty.second, val);
        seg[v].sum = seg[v].sum + val;
        seg[v].ans = 1;
        if(val == -1) 
        {
            seg[v].ans = 0;
        }
        return;
    }
    int tm = (tl + tr) / 2;

    if (pos <= tm) update(2 * v, tl, tm, pos, val);
    else update(2 * v + 1, tm + 1, tr, pos, val);
    //
    seg[v].ty.first =  max (seg[2*v].ty.first , seg[2*v+1].ty.first);
    seg[v].ty.second = max (seg[2*v].ty.second , seg[2*v+1].ty.second);

    seg[v].sum = seg[2*v].sum + seg[2*v+1].sum;

    seg[v].ans = max(seg[2*v].ans + seg[2*v+1].sum , seg[2*v].sum + seg[2*v+1].ans);
    seg[v].ans = max(seg[v].ans , seg[2*v].ty.first + seg[2*v+1].ty.second);
}
node query(int v, int tl, int tr, int l, int r)
{
    if (tl > r or tr < l) return {make_pair(0ll,0ll), 0 , 0};
    if (tl >= l and tr <= r) return seg[v];

    int tm = (tl + tr) / 2;
    node L = query(2*v, tl, tm, l, r);
    node R = query(2*v+1, tm + 1, tr, l, r);
    node ret;
    ret.ty.first = max(L.ty.first , R.ty.first); ret.ty.second = max(L.ty.second , R.ty.second);
    ret.sum = L.sum + R.sum;
    ret.ans = max(L.ans + R.sum , L.sum + R.ans);
    ret.ans = max(ret.ans , L.ty.first + R.ty.second);
    return ret;
}
int32_t main()
{
    cin >> n >> s >> q;

    for(int i = 0; i < s.length(); i++)
    {
        if(s[i] == 'C')
        {
            update(1, 1, n, i + 1, -1);
        }
        else
        {
            update(1, 1, n, i + 1, 1);
        }
    }
    while(q--)
    {
        int l, r; 
        cin >> l >> r;
        cout << query(1, 1, n, l, r).ans;
        cout << endl;
    }
}

Compilation message (stderr)

election.cpp: In function 'int32_t main()':
election.cpp:77:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     for(int i = 0; i < s.length(); i++)
      |                    ~~^~~~~~~~~~~~

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