提出 #70627913

---

ソースコード 拡げる

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <tuple>
#include <typeinfo>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

// using ll = long long;
// using ld = long double;
// using namespace std;
// #define endl "\n";
#define ff first
#define ss second

using namespace std;

#define forn(i,n) for(int i=0;i<n;i++)



#define MAX 400005

// Ideally, we should not use global variables and large
// constant-sized arrays, we have done it here for simplicity.
int tree[MAX] = {0};  // To store segment tree
int lazy[MAX] = {0};  // To store pending updates

/*  si -> index of current node in segment tree
    ss and se -> Starting and ending indexes of elements for
                 which current nodes stores sum.
    us and ue -> starting and ending indexes of update query
    diff -> which we need to add in the range us to ue */
void updateRangeUtil(int si, int x, int se, int us,
                     int ue, int dif)
{
    // If lazy value is non-zero for current node of segment
    // tree, then there are some pending updates. So we need
    // to make sure that the pending updates are done before
    // making new updates. Because this value may be used by
    // parent after recursive calls (See last line of this
    // function)
    if (lazy[si] != 0)
    {
        // Make pending updates using value stored in lazy
        // nodes
        tree[si] += (se-x+1)*lazy[si];

        // checking if it is not leaf node because if
        // it is leaf node then we cannot go further
        if (x != se)
        {
            // We can postpone updating children we don't
            // need their new values now.
            // Since we are not yet updating children of si,
            // we need to set lazy flags for the children
            lazy[si*2 + 1]   += lazy[si];
            lazy[si*2 + 2]   += lazy[si];
        }

        // Set the lazy value for current node as 0 as it
        // has been updated
        lazy[si] = 0;
    }

    // out of range
    if (x>se || x>ue || se<us)
        return ;

    // Current segment is fully in range
    if (x>=us && se<=ue)
    {
        // Add the difference to current node
        tree[si] += (se-x+1)*dif;

        // same logic for checking leaf node or not
        if (x != se)
        {
            // This is where we store values in lazy nodes,
            // rather than updating the segment tree itself
            // Since we don't need these updated values now
            // we postpone updates by storing values in lazy[]
            lazy[si*2 + 1]   += dif;
            lazy[si*2 + 2]   += dif;
        }
        return;
    }

    // If not completely in rang, but overlaps, recur for
    // children,
    int mid = (x+se)/2;
    updateRangeUtil(si*2+1, x, mid, us, ue, dif);
    updateRangeUtil(si*2+2, mid+1, se, us, ue, dif);

    // And use the result of children calls to update this
    // node
    tree[si] = tree[si*2+1] + tree[si*2+2];
}

// Function to update a range of values in segment
// tree
/*  us and eu -> starting and ending indexes of update query
    ue  -> ending index of update query
    diff -> which we need to add in the range us to ue */
void updateRange(int n, int us, int ue, int dif)
{
   updateRangeUtil(0, 0, n-1, us, ue, dif);
}


/*  A recursive function to get the sum of values in given
    range of the array. The following are parameters for
    this function.
    si --> Index of current node in the segment tree.
           Initially 0 is passed as root is always at'
           index 0
    ss & se  --> Starting and ending indexes of the
                 segment represented by current node,
                 i.e., tree[si]
    qs & qe  --> Starting and ending indexes of query
                 range */
int getSumUtil(int x, int se, int qs, int qe, int si)
{
    // If lazy flag is set for current node of segment tree,
    // then there are some pending updates. So we need to
    // make sure that the pending updates are done before
    // processing the sub sum query
    if (lazy[si] != 0)
    {
        // Make pending updates to this node. Note that this
        // node represents sum of elements in arr[ss..se] and
        // all these elements must be increased by lazy[si]
        tree[si] += (se-x+1)*lazy[si];

        // checking if it is not leaf node because if
        // it is leaf node then we cannot go further
        if (x != se)
        {
            // Since we are not yet updating children os si,
            // we need to set lazy values for the children
            lazy[si*2+1] += lazy[si];
            lazy[si*2+2] += lazy[si];
        }

        // unset the lazy value for current node as it has
        // been updated
        lazy[si] = 0;
    }

    // Out of range
    if (x>se || x>qe || se<qs)
        return 0;

    // At this point we are sure that pending lazy updates
    // are done for current node. So we can return value 
    // (same as it was for query in our previous post)

    // If this segment lies in range
    if (x>=qs && se<=qe)
        return tree[si];

    // If a part of this segment overlaps with the given
    // range
    int mid = (x + se)/2;
    return getSumUtil(x, mid, qs, qe, 2*si+1) +
           getSumUtil(mid+1, se, qs, qe, 2*si+2);
}

// Return sum of elements in range from index qs (query
// start) to qe (query end).  It mainly uses getSumUtil()
int getSum(int n, int qs, int qe)
{
    // Check for erroneous input values
    if (qs < 0 || qe > n-1 || qs > qe)
    {
        cout <<"Invalid Input";
        return -1;
    }

    return getSumUtil(0, n-1, qs, qe, 0);
}

// A recursive function that constructs Segment Tree for
//  array[ss..se]. si is index of current node in segment
// tree st.
void constructSTUtil(int arr[], int x, int se, int si)
{
    // out of range as ss can never be greater than se
    if (x > se)
        return ;

    // If there is one element in array, store it in
    // current node of segment tree and return
    if (x == se)
    {
        tree[si] = arr[x];
        return;
    }

    // If there are more than one elements, then recur
    // for left and right subtrees and store the sum
    // of values in this node
    int mid = (x + se)/2;
    constructSTUtil(arr, x, mid, si*2+1);
    constructSTUtil(arr, mid+1, se, si*2+2);

    tree[si] = tree[si*2 + 1] + tree[si*2 + 2];
}

/* Function to construct segment tree from given array.
   This function allocates memory for segment tree and
   calls constructSTUtil() to fill the allocated memory */
void constructST(int arr[], int n)
{
    // Fill the allocated memory st
    constructSTUtil(arr, 0, n-1, 0);
}



void solve(){
    int n;
    cin>>n;
    string s;
    cin>>s;
    vector<pair<char,int>> vs;
    forn(i,n-1){
        if(vs.empty()){
            vs.push_back({s[i],1});
        } else {
            if(s[i]==vs.back().ff){
                vs.back().ss++;
            } else{
                vs.push_back({s[i],1});
            }
        }
    }
    vector<pair<int,int>> vv(n,{0,0});
    int c=0;
    // dbgv(vs.size());
    for(int i=0;i<vs.size();i++){
        // dbgv(c);
        // cout<<vv[c].ff<<' '<<vv[c].ss<<endl; 
        for(int x=c+vs[i].ss,j=0;c<=x;c++,j++){
            if(vs[i].ff=='L'){
                vv[c].ff+=vs[i].ss-j;
                vv[c].ss+=max(0,j);
            } else {
                vv[c].ss+=vs[i].ss-j;
                vv[c].ff+=max(0,j);
            }
        }
        c--;
    }
    // forn(i,n){
    //     cout<<vv[i].ff<<' '<<vv[i].ss<<endl;
    // }

    int arr[n];
    memset(arr,0,sizeof(arr));
    // int n = sizeof(arr)/sizeof(arr[0]);

    // Build segment tree from given array
    constructST(arr, n);

    // Print sum of values in array from index 1 to 3
    // cout <<"Sum of values in given range = "<<
    //        getSum(n, 1, 3);

    // Add 10 to all nodes at indexes from 1 to 5.
    // updateRange(n, 1, 5, 10);
    forn(i,n){ 
        updateRange(n,vv[i].ff,n-(vv[i].ss)-1,1);
    }

    // Find sum after the value is updated
    forn(i,n){
        cout<<getSum(n,i,i)<<' ';
    }
    cout<<endl;
}

int main() {
    // ios_base::sync_with_stdio(false);
    // cin.tie(0);

    int T = 1;
    cin >> T;
    while(T--){
        solve();
    }
    return 0;
}

提出情報

コンパイルエラー

./Main.cpp: In function 'void solve()':
./Main.cpp:271:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<char, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  271 |     for(int i=0;i<vs.size();i++){
      |                 ~^~~~~~~~~~

ジャッジ結果