oj.uz

답안 #63583

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
63583 2018-08-02T08:31:41 Z antimirage Election (BOI18_election) C++17
0 / 100
 207 ms 200056 KB 
#include <algorithm>
#include <iostream>
#include <assert.h>
#include <memory.h>
#include <stdio.h>
#include <iomanip>
#include <utility>
#include <math.h>
#include <time.h>
#include <vector>
#include <set>
#include <map>

#define fr first
#define sc second
#define mk make_pair
#define pb push_back
#define sz(s) (int)s.size()
#define all(s) s.begin(), s.end()

using namespace std;

const int N = 5e5 + 5;

int n, q, pref[N], mp[N], root[N], suf[N], sz, mn[N * 4], L, R, Mp[N], up[20][N];

char s[N];

vector <vector <int> > g;

struct node
{
    int l, r, val, must;

    node(){
        val = -1e9;
        l = r = must = 0;
    }
};

node t[N * 20];

void build (int v, int tl = 1, int tr = n)
{
    if (tl == tr)
        t[v].val = -suf[tl];
    else
    {
        int tm = (tl + tr) >> 1;
        t[v].l = ++sz;
        t[v].r = ++sz;
        build( t[v].l, tl, tm );
        build( t[v].r, tm + 1, tr );

        t[v].val = max(t[ t[v].l ].val, t[ t[v].r ].val);
    }
}
void update (int ov, int nv, int l, int r, int tl = 1, int tr = n)
{
    if (l <= tl && tr <= r)
    {
        t[nv].must = t[ov].must - 1;
        t[nv].val = t[ov].val - 1;
        t[nv].l = t[ov].l;
        t[nv].r = t[ov].r;
        return;
    }
    int tm = (tl + tr) >> 1;

    if (l > tm)
        t[nv].l = t[ov].l;
    else
    {
        if (!t[nv].l) t[nv].l = ++sz;
        update( t[ov].l, t[nv].l, l, r, tl, tm );
    }
    if(r < tm + 1)
        t[nv].r = t[ov].r;
    else
    {
        if (!t[nv].r) t[nv].r = ++sz;
        update( t[ov].r, t[nv].r, l, r, tm + 1, tr );
    }
    t[nv].val = max( t[ t[nv].l ].val, t[ t[nv].r ].val );
}

void dfs (int v, int p = -1)
{
    up[0][v] = p;

    for (int i = 1; i < 20; i++)
        up[i][v] = up[i - 1][ up[i - 1][v] ];

    root[v] = ++sz;

    if (p == -1)
        build( root[v] );
    else
        update( root[p], root[v], 1, v );

    for (auto to : g[v])
        dfs(to, v);
}
int get (int v, int l, int r, int tl = 1, int tr = n, int sup = 0)
{
    if (l > tr || tl > r || v == 0)
        return -1e9;

    if (l <= tl && tr <= r)
        return t[v].val + sup;

    int tm = (tl + tr) >> 1;

    return max( get(t[v].l, l, r, tl, tm, sup + t[v].must), get(t[v].r, l, r, tm + 1, tr, sup + t[v].must) );
}
void Build (int v = 1, int tl = 1, int tr = n)
{
    if (tl == tr)
        mn[v] = tl;
    else
    {
        int tm = (tl + tr) >> 1;
        Build(v + v, tl, tm);
        Build(v + v + 1, tm + 1, tr);

        if ( pref[ mn[v + v] ] < pref[ mn[v + v + 1] ] )
            mn[v] = mn[v + v];
        else
            mn[v] = mn[v + v + 1];
    }
}
int Get (int l, int r, int v = 1, int tl = 1, int tr = n)
{
    if (l > tr || tl > r)
        return n + 1;

    if (l <= tl && tr <= r)
        return mn[v];

    int tm = (tl + tr) >> 1;

    int ind1 = Get(l, r, v + v, tl, tm);
    int ind2 = Get(l, r, v + v + 1, tm + 1, tr);

    if ( pref[ind1] < pref[ind2] )
        return ind1;

    return ind2;
}
int Cnt (int v, int L)
{
    int cn = 0;
    for (int i = 19; i >= 0; i--)
    {
        if ( up[i][v] > -1 && up[i][v] >= L )
            v = up[i][v], cn += (1 << i);
    }
    return cn + 1;
}
main()
{
    cin >> n;

    g.resize(n + 1);

    scanf("%s", s + 1);
    cin >> q;

    memset(mp, -1, sizeof(mp));
    memset(Mp, -1, sizeof(Mp));
    memset(up, -1, sizeof(up));

    mp[0] = 0;
    Mp[0] = 0;

    for (int i = 1; i <= n; i++)
    {
        pref[i] = pref[i - 1] + (s[i] == 'C' ? 1 : -1);

        if (s[i] == 'T')
        {
            if (pref[i] < 0)
            {
                g[ mp[ abs(pref[i]) - 1 ] ].pb(i);

                if (mp[ abs(pref[i]) ] == -1) mp[ abs(pref[i]) ] = i;
            }
            else
            {
                if ( s[ Mp[ pref[i] + 1 ] ] == 'C' )
                    g[0].pb(i);
                else
                    g[ Mp[ pref[i] + 1 ] ].pb(i);

            }
        }
        if (Mp[ pref[i] ] == -1 || s[ Mp[ pref[i] ] ] == 'C') Mp[ pref[i] ] = i;
    }
    pref[n + 1] = 1e9 + 7;
    Build();
    for (int i = n; i >= 1; i--)
        suf[i] = suf[i + 1] + (s[i] == 'C' ? 1 : -1);

    dfs(0);

    while (q--)
    {
        scanf("%d%d", &L, &R);
        int ind = Get( L, R ), ans = 0;

        ans = pref[ind] - pref[L - 1];

        if (ans >= 0)
            printf("%d\n", -(-get(root[0], L, R) - suf[R + 1]) );
        else
            printf("%d\n", Cnt(ind, L) - (-get(root[ind], L, R) - suf[R + 1]) );
    }
}

Compilation message

election.cpp:160:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
election.cpp: In function 'int main()':
election.cpp:166:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s", s + 1);
     ~~~~~^~~~~~~~~~~~~
election.cpp:208: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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 207 ms 200056 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 54.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 207 ms 200056 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 207 ms 200056 KB Output isn't correct
2 Halted 0 ms 0 KB -