Submission #586921

#	Time	Username	Problem	Language	Result	Execution time	Memory
586921		eecs	Segway (COI19_segway)	C++17	100 / 100	235 ms	32968 KiB

segway

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

const int maxn = 20010;
int n, m, cur[maxn], res[maxn], rem[maxn];
bool mark[maxn];
array<int, 3> speed[maxn];
vector<int> ev[maxn];

namespace BIT {
int c[310];

void add(int p, int v) {
    for (p++; p <= 300; p += p & -p) c[p] += v;
}

int sum(int p) {
    int s = 0;
    for (p++; p; p -= p & -p) s += c[p];
    return s;
}
} // namespace BIT

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int &x : speed[i]) cin >> x;
        ev[0].push_back(i);
    }
    cin >> m;
    while (m--) {
        int x;
        cin >> x, mark[x] = 1;
    }
    BIT::add(0, n);
    for (int i = 0; i < maxn; i++) {
        for (int j : ev[i]) {
            if (cur[j] == 300) { res[j] = i; continue; }
            if (!rem[j] && mark[cur[j]]) {
                rem[j] = (n - BIT::sum(cur[j])) % 20;
            }
            if (rem[j]) {
                ev[i + 1].push_back(j), rem[j]--;
            } else {
                ev[i + speed[j][cur[j] / 100]].push_back(j);
            }
        }
        for (int j : ev[i]) if (cur[j] < 300) {
            BIT::add(cur[j], -1), BIT::add(++cur[j], 1);
        }
    }
    for (int i = 1; i <= n; i++) {
        cout << res[i] << "\n";
    }
    return 0;
}

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