Submission #3655162


Source Code Expand

Copy
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <complex>
using namespace std;
 
#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()
 
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

int in() { int x; scanf("%d", &x); return x; }
ll lin() { ll x; scanf("%lld", &x); return x; }

struct BIT{
    int n;
    VL bit;

    BIT(){}
    BIT(int x){
        n = x;
        bit.assign(n+1, 0);
    }

    void init(int x){
        n = x;
        bit.assign(n+1, 0);
    }

    void add(int i, ll x){
        i++;
        while (i <= n){
            bit[i] += x;
            i += i & -i;
        }
    }

    // [0, i]
    ll sum(int i){
        i++;
        ll ret = 0;
        while (i > 0){
            ret += bit[i];
            i -= i & -i;
        }
        return ret;
    }

    // [l, r)
    ll sum(int l, int r){
        if (l >= r) return 0;
        return sum(r-1) - sum(l-1);
    }
};

int main() {
    int n;
    string s;
    cin >> n >> s;
    VI d, c(n);
    REP(i,n) if (s[i] == 'D') d.push_back(i);
    int cnt = 0;
    REP(i,n){
        if (s[i] == 'D') cnt++;
        c[i] = cnt;
    }
    int m = d.size();
    int q;
    cin >> q;
    while (q--){
        int k = in();
        ll ans = 0, sum = 0;
        BIT bit(m);
        int j = 0;
        REP(i,n){
            if (s[i] == 'M'){
                bit.add(0, 1);
                bit.add(c[i], -1);
                sum += c[i] - j;
            }else if (s[i] == 'C'){
                while (i - d[j] >= k){
                    sum -= bit.sum(j);
                    j++;
                }
                ans += sum;
            }
        }
        cout << ans << endl;
    }
    return 0;
}

Submission Info

Submission Time
Task C - k-DMC
User TangentDay
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2212 Byte
Status

Compile Error

./Main.cpp: In function ‘int in()’:
./Main.cpp:31:34: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
 int in() { int x; scanf("%d", &x); return x; }
                                  ^
./Main.cpp: In function ‘ll lin()’:
./Main.cpp:32:35: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
 ll lin() { ll x; scanf("%lld", &x); return x; }
                                   ^

Test Cases

Set Name Score / Max Score Test Cases
All 0 / 600 dmc-dmc-00, dmc-dmc-01, dmc-dmc-02, dmc-dmc-03, dmc-dmc-04, dmc-large-00, dmc-large-01, dmc-large-02, dmc-large-03, dmc-large-04, dmc-random-00, dmc-random-01, dmc-random-02, dmc-random-03, dmc-random-04, dmc-special-00, dmc-special-01, dmc-special-02, dmc-special-03, sample_01, sample_02, sample_03, sample_04
Case Name Status Exec Time Memory
dmc-dmc-00 2299 ms 9596 KB
dmc-dmc-01 2320 ms 9596 KB
dmc-dmc-02 2288 ms 9596 KB
dmc-dmc-03 2315 ms 9596 KB
dmc-dmc-04 2362 ms 9596 KB
dmc-large-00 335 ms 5892 KB
dmc-large-01 335 ms 5892 KB
dmc-large-02 336 ms 5892 KB
dmc-large-03 332 ms 5892 KB
dmc-large-04 333 ms 5892 KB
dmc-random-00 292 ms 5252 KB
dmc-random-01 222 ms 4100 KB
dmc-random-02 199 ms 5252 KB
dmc-random-03 153 ms 4740 KB
dmc-random-04 118 ms 3716 KB
dmc-special-00
dmc-special-01 2107 ms 9596 KB
dmc-special-02 473 ms 17400 KB
dmc-special-03 207 ms 5252 KB
sample_01 1 ms 256 KB
sample_02 1 ms 256 KB
sample_03 1 ms 256 KB
sample_04 1 ms 256 KB