Submission #1011044

#	Time	Username	Problem	Language	Result	Execution time	Memory
1011044		ksu2009en	Segway (COI19_segway)	C++14	100 / 100	519 ms	2120 KiB

segway

#include <iostream>
#include <vector>
#include <string>
#include <math.h>
#include <cmath>
#include <iomanip>
#include <cstdio>
#include <algorithm>
#include <numeric>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <bitset>
#include <cstring>
#include <unordered_map>

using namespace std;
typedef int ll;

#define endl '\n'

ll t[307];

void add(ll pos, ll val){
    pos++;
    
    for(int i = pos; i < 307; i += (i & -i))
        t[i] += val;
}

ll get(ll pos){
    pos++;
    
    ll ans = 0;
    for(int i = pos; i > 0; i -= (i & -i))
        ans += t[i];
    
    return ans;
}

ll get(ll l, ll r){
    return get(r) - (l != 0 ? get(l - 1) : 0);
}

ll a[20007], b[20007], c[20007];

struct one{
    ll time, ind, pos, left0; // pos - segment of end
};

bool const operator < (one const &p1, one const &p2){
    return p1.time < p2.time;
}
bool const operator > (one const &p1, one const &p2){
    return p1.time > p2.time;
}
bool const operator == (one const &p1, one const &p2){
    return p1.time == p2.time;
}

int main(){
    ll n;
    cin >> n;
    
    for(int i = 1; i <= n; i++)
        cin >> a[i] >> b[i] >> c[i];
    
    vector<bool> d(307);
    ll m;
    cin >> m;
    
    while(m--){
        ll c;
        cin >> c;
        
        d[c] = true;
    }
    
    priority_queue<one, vector<one>, greater<one>> q;
    vector<ll> ans(n + 1);
    
    for(int i = 1; i <= n; i++){
        q.push({0, i, 0, 0});
        add(0, 1);
    }
    
    while(!q.empty()){
        auto v = q.top();
        vector<one> quer;
        
        while(!q.empty() && q.top().time == v.time){
            quer.push_back(q.top());
            q.pop();
        }
        
        for(auto i: quer){
            if(i.pos == 300){
                ans[i.ind] = i.time;
                continue;
            }
            
            if(i.left0 > 0){
                q.push({i.time + 1, i.ind, i.pos + 1, i.left0 - 1});
                continue;
            }
            ll time0 = 0;
            if(i.pos + 1 <= 100)
                time0 = a[i.ind];
            else if(i.pos + 1 <= 200)
                time0 = b[i.ind];
            else
                time0 = c[i.ind];
            
            if(d[i.pos]){
                ll ahead = get(i.pos + 1, 301);
                ahead %= 20;
                
                if(ahead == 0){
                    q.push({i.time + time0, i.ind, i.pos + 1, 0});
                }
                else{
                    q.push({i.time + 1, i.ind, i.pos + 1, ahead - 1});
                }
            }
            else{
                q.push({i.time + time0, i.ind, i.pos + 1, 0});
            }
        }
        
        for(auto i: quer){
            add(i.pos, -1);
            add(i.pos + 1, 1);
        }
    }
    
    for(int i = 1; i <= n; i++)
        cout << ans[i] << endl;
    
    return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 40 / 40
• Subtask 3: 45 / 45