Submission #1057045

#	Time	Username	Problem	Language	Result	Execution time	Memory
1057045		slivajan	Trains (BOI24_trains)	C++17	71 / 100	2083 ms	202100 KiB

Main

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

typedef long long un;
typedef vector<un> vuc;

#define REP(i, a, b) for (un i = (un)a; i < (un)b; i++)
#define FEAC(i, a) for (auto&& i : a)
#define vec vector
#define ALL(x) (x).begin(), (x).end()

constexpr un M = 1e9 + 7;

#define DIRECT 0
#define CACHE 1

vuc create_iv(un N){
    
    un vel = 2;

    while(vel < N) vel *= 2;

    vuc iv(2*vel, 0);
    iv[0] = vel;

    return iv;
}

un get_iv(vuc& iv, un index){
    un ret = 0;

    index += iv[0];

    while(index > 0){
        ret += iv[index];
        ret %= M;
        index /= 2;
    }

    return ret;
}

void set_iv(vuc& iv, un L, un R, un val){
    R = min(R, iv[0]-1);

    L += iv[0];
    R += iv[0];

    while (L <= R)
    {
        if (L % 2 == 1){
            iv[L] += val;
            iv[L] %= M;
            L++;
        }

        if (R % 2 == 0){
            iv[R] += val;
            iv[R] %= M;
            R--;
        }

        L /= 2;
        R /= 2;
    }
    
}


int main(){

    un N;
    cin >> N;

    vuc D(N);
    vuc X(N);

    REP(i, 0, N){
        cin >> D[i] >> X[i];
    }

    un bound = (un)pow((double)N, 0.6666666);

    map<pair<un, un>, un> vyskyty;

    REP(i, 0, N){
        if (D[i] == 0) continue;
        if (vyskyty.find({D[i], i % D[i]}) == vyskyty.end()){
            vyskyty[{D[i], i % D[i]}] = min(X[i], (N-i) / D[i]);
        }
        else{
            vyskyty[{D[i], i % D[i]}] += min(X[i], (N-i) / D[i]);
        }
    }

    map<pair<un, un>, un> volba;
    FEAC(kv, vyskyty){
        pair<un, un> key;
        un val;

        tie(key, val) = kv;

        if (val < bound){
            volba[key] = DIRECT;
        }
        else{
            volba[key] = CACHE;
        }
    }

    vuc DP(N, 0);
    DP[0] = 1;

    map<un, map<un, vuc>> cache;

    REP(i, 0, N){
        FEAC(kv, cache){
            un key;
            tie(key, ignore) = kv;

            if (cache[key].find(i % key) != cache[key].end()){
                DP[i] = (DP[i] + get_iv(cache[key][i % key], i/key)) % M;
            }
        }

        if (D[i] == 0) continue;


        if (volba[{D[i], i%D[i]}] == DIRECT){
            for (un j = i + D[i]; (j < N) and (((j-i) / D[i]) <= X[i]); j += D[i]){
                DP[j] = (DP[j] + DP[i]) % M;
            }
        }
        else{
            if (cache.find(D[i]) == cache.end()) {
                cache[D[i]] = {{i % D[i], create_iv((N/D[i]) + 1)}};
            }
            else if (cache[D[i]].find(i % D[i]) == cache[D[i]].end()){
                cache[D[i]][i % D[i]] = create_iv((N/D[i]) + 1);
            }
            set_iv(cache[D[i]][i % D[i]], (i/D[i]) + 1, (i/D[i]) + X[i], DP[i]);
        }

    }

    un res = 0;

    REP(i, 0, N){
        res = (res + DP[i]) % M;
    }

    cout << res;

}

• Subtask 1: 8 / 8
• Subtask 2: 13 / 13
• Subtask 3: 16 / 16
• Subtask 4: 34 / 34
• Subtask 5: 0 / 29