oj.uz

Submission #254608

# Submission time Handle Problem Language Result Execution time Memory
254608 2020-07-30T10:22:41 Z Kastanda Election (BOI18_election) C++11
0 / 100
 9 ms 12160 KB 
// M
#include<bits/stdc++.h>
#define lc (id << 1)
#define rc (lc ^ 1)
#define md ((l + r) >> 1)
using namespace std;
const int N = 500005, MXS = N * 4;
int n, q, R[N];
char A[N];
int LZ[MXS], MN[MXS];
vector < pair < int , int > > V[N];
inline void Shift(int id)
{
        LZ[lc] += LZ[id];
        MN[lc] += LZ[id];
        LZ[rc] += LZ[id];
        MN[rc] += LZ[id];
        LZ[id] = 0;
}
void Add(int le, int ri, int val, int id = 1, int l = 0, int r = n + 1)
{
        if (ri <= l || r <= le)
                return ;
        if (le <= l && r <= ri)
        {
                LZ[id] += val;
                MN[id] += val;
                return ;
        }
        Shift(id);
        Add(le, ri, val, lc, l, md);;
        Add(le, ri, val, rc, md, r);
        MN[id] = min(MN[lc], MN[rc]);
}
int GetMin(int le, int ri, int id = 1, int l = 0, int r = n + 1)
{
        if (ri <= l || r <= le)
                return MXS;
        if (le <= l && r <= ri)
                return MN[id];
        Shift(id);
        return min(GetMin(le, ri, lc, l, md), GetMin(le, ri, rc, md, r));
}
int main()
{
        scanf("%d%s%d", &n, &A[1], &q);
        for (int i = 1; i <= q; i ++)
        {
                int l, r;
                scanf("%d%d", &l, &r);
                V[r].push_back({i, l});
        }
        vector < int > stk;
        for (int i = 1; i <= n; i ++)
        {
                if (A[i] == 'C')
                {
                        if (stk.size())
                                Add(stk.back(), n + 1, -1), stk.pop_back();
                        Add(i, n + 1, 1);
                }
                else
                        stk.push_back(i);
                for (auto X : V[i])
                        R[X.first] = (int)stk.size() + max(-(GetMin(X.second, i + 1) - GetMin(X.second - 1, X.second)), 0);
        }
        for (int i = 1; i <= q; i ++)
                printf("%d\n", R[i]);
        return 0;
}

Compilation message

election.cpp: In function 'int main()':
election.cpp:46:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%s%d", &n, &A[1], &q);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
election.cpp:50:22: 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

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 12160 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 54.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 12160 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 12160 KB Output isn't correct
2 Halted 0 ms 0 KB -