Contest Duration: ~ (local time)

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);
}

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'){
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 2018-11-24 20:28:46+0900 C - k-DMC TangentDay C++14 (GCC 5.4.1) 0 2212 Byte RE

#### 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