제출 #1315117

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1315117		opeleklanos	던전 (IOI21_dungeons)	C++20	26 / 100	233 ms	97492 KiB

dungeons

#include <iostream>
#include <vector>
#include "dungeons"
using namespace std;

#define ll long long

vector<int> w, l, s, p;

vector<vector<pair<ll, pair<int, ll>>>> nextLoss;
int n;

void init(int n1, vector<int> s1, vector<int> p1, vector<int> w1, vector<int> l1){
    n = n1;
    s = s1;
    p = p1;
    w = w1;
    l = l1;

    nextLoss.assign(n+1, {});
    nextLoss[n].push_back({20000000000000000, {n, 0}});
    for(int i = n-1; i>=0; i--){
        nextLoss[i].push_back({(ll)s[i]-1, {l[i], (ll)s[i]}});
        int stIndx = lower_bound(nextLoss[w[i]].begin(), nextLoss[w[i]].end(), make_pair((ll)2*s[i], make_pair((int)0, (ll)0))) - nextLoss[w[i]].begin();
        while(stIndx < nextLoss[w[i]].size()){
            nextLoss[i].push_back({
                ((nextLoss[w[i]][stIndx].first != 20000000000000000) ? ((ll)nextLoss[w[i]][stIndx].first - (ll)s[i]):20000000000000000),
                {nextLoss[w[i]][stIndx].second.first, (ll)s[i]+nextLoss[w[i]][stIndx].second.second}});
            stIndx++;
        }
    }

}

ll simulate(int x, int z1){
    ll z = (ll)z1;
    while(x<n){
        pair<ll, pair<int, ll>> ind = nextLoss[x][lower_bound(nextLoss[x].begin(), nextLoss[x].end(), make_pair(z, make_pair((int)0, (ll)0))) - nextLoss[x].begin()];
        x = ind.second.first;
        z += ind.second.second;
    }
    return z;
}



// int main(void){
//     freopen("input.txt", "r", stdin);
//     int n1;
//     vector<int> s1; vector<int> p1; vector<int> w1; vector<int> l1;
//     cin>>n1;
//     s1.assign(n1, 0);
//     l1.assign(n1, 0);
//     w1.assign(n1, 0);
//     p1.assign(n1, 0);

//     for(int i = 0; i<n1; i++) cin>>s1[i];
//     for(int i = 0; i<n1; i++) cin>>p1[i];
//     for(int i = 0; i<n1; i++) cin>>w1[i];
//     for(int i = 0; i<n1; i++) cin>>l1[i];

//     init(n1, s1, p1, w1, l1);

//     int q; cin>>q;
//     for(int i = 0; i<q; i++){
//         int x2, z2;
//         cin>>x2>>z2;
//         cout<<simulate(x2, z2)<<endl;
//     }
// }

• Subtask 1: 0 / 11
• Subtask 2: 26 / 26
• Subtask 3: 0 / 13
• Subtask 4: 0 / 12
• Subtask 5: 0 / 27
• Subtask 6: 0 / 11