codeFlyer (bitFlyer Programming Contest)

Submission #2603263

Source codeソースコード

#include <bits/stdc++.h>
using namespace std;

#define NDEBUG
#ifdef DEBUG
#include "cout11.h"
#undef NDEBUG
#endif
#include <cassert>

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> ii;
typedef pair<ll,ll> llll;
typedef pair<double,double> dd;

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<ll> vll;

#define sz(a)  int((a).size())
#define pb  push_back
#define FOR(var,from,to) for(int var=(from);var<=(to);++var)
#define rep(var,n)  for(int var=0;var<(n);++var)
#define rep1(var,n)  for(int var=1;var<=(n);++var)
#define repC2(vari,varj,n)  for(int vari=0;vari<(n)-1;++vari)for(int varj=vari+1;varj<(n);++varj)
#define ALL(c)  (c).begin(),(c).end()
#define RALL(c)  (c).rbegin(),(c).rend()
#define tr(i,c)  for(auto i=(c).begin(); i!=(c).end(); ++i)
#define found(s,e)  ((s).find(e)!=(s).end())
#define mset(arr,val)  memset(arr,val,sizeof(arr))
#define mid(x,y) ((x)+((y)-(x))/2)
#define IN(x,a,b) ((a)<=(x)&&(x)<=(b))

#define INTSPACE 12
char _buf[INTSPACE*1000000 + 3];

int loadint() {
    if (fgets(_buf, INTSPACE+3, stdin)==NULL) return 0;
    return atoi(_buf);
}
int loadvec(vector<int>& v, int N=-1) {
    if (N == -1) {
        N = loadint();
        if (N==0) return 0;
    }
    int bufsize = INTSPACE*N + 3;
    if (fgets(_buf, bufsize, stdin)==NULL) return 0;
    v.resize(N);

    int i=0;
    bool last = false;
    for (char *p=&_buf[0]; ;) {
        char *q = p;
        while (*q > ' ') ++q;
        if (*q == 0x0D || *q == 0x0A) last = true;
        *q = 0;
        v[i++] = atoi(p);
        if (last || i == N) break;
        p = q+1;
    }
    // assert(i <= N);
    return i;
}

ll solve(int N, int D, vi& x) {
    vector<ll> before(N,0), after(N,0);
    rep(i,N){
        //after
        int ax = upper_bound(ALL(x), x[i]+D) - x.begin();
        after[i] = ax - i - 1;
        // printf("  after: %d\n", ax);
        //before
        int bx = lower_bound(ALL(x), x[i]-D) - x.begin();
        before[i] = i - bx;
        // printf("  before: %d\n", bx);
    }
#ifdef DEBUG
    cerr << before << endl;
    cerr << after << endl;
#endif

    ll ans = 0;
    rep(i, N-2) {
        ll a = after[i];
        if (a < 2) continue;
        // Xi .. Xk <= D
        // i, ..., i+d としたら
        // 2..after のdでそれぞれ d-1 // 2なら1 3なら2
        // のΣ
        //  = Σ_2^a (d-1) = a(a-1)/2
        ans -= a*(a-1) / 2;
    }

    // vector<ll> ac(N+1, 0);
    // rep(i, N) ac[i+1] = ac[i] + imos[i];
    // cerr << ac << endl;

    for (int i=1; i<N-1; ++i) {
        ans += before[i] * after[i];//  - ac[1+i];
    }
    return ans;
}

int main() {
    vi x(2);
    loadvec(x, 2);
    int n=x[0], d=x[1];
    loadvec(x, n);
    cout << solve(n,d,x) << endl;
    return 0;
}

Submission

Task問題 C - 徒歩圏内
User nameユーザ名 naoya_t
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 400
Source lengthソースコード長 2941 Byte
File nameファイル名
Exec time実行時間 16 ms
Memory usageメモリ使用量 3200 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - sample-01.txt,sample-02.txt,sample-03.txt,sample-04.txt
All 400 / 400 01.txt,02.txt,03.txt,04.txt,05.txt,06.txt,07.txt,08.txt,09.txt,10.txt,11.txt,12.txt,sample-01.txt,sample-02.txt,sample-03.txt,sample-04.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
01.txt AC 15 ms 3200 KB
02.txt AC 16 ms 3200 KB
03.txt AC 11 ms 3200 KB
04.txt AC 15 ms 3200 KB
05.txt AC 15 ms 3200 KB
06.txt AC 13 ms 3200 KB
07.txt AC 13 ms 2688 KB
08.txt AC 13 ms 2688 KB
09.txt AC 1 ms 256 KB
10.txt AC 13 ms 3200 KB
11.txt AC 15 ms 3200 KB
12.txt AC 12 ms 3200 KB
sample-01.txt AC 1 ms 256 KB
sample-02.txt AC 1 ms 256 KB
sample-03.txt AC 1 ms 256 KB
sample-04.txt AC 1 ms 256 KB