Submission #233360

#	Time	Username	Problem	Language	Result	Execution time	Memory
233360		VEGAnn	Segway (COI19_segway)	C++14	100 / 100	648 ms	61664 KiB

segway

#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define PB push_back
using namespace std;
const int N = 20100;
const int M = 310;
const int md = int(1e9) + 7;
const int TIM = 20000;
vector<array<int, 2> > events[TIM];
int a[N][3], n, tim[N], m, ans[N], mem[N], fast[N], OST[N], OSS[TIM], pos[N];
int fen[M];
bool loc[M];

bool cmp(int _x, int _y){
    return tim[_x] < tim[_y];
}

void update(int x, int vl){
    for (; x < M; x = (x | (x + 1)))
        fen[x] += vl;
}

int sum(int x){
    int res = 0;
    for (; x >= 0; x = (x & (x + 1)) - 1)
        res += fen[x];
    return res;
}

int sum(int l, int r){
    return sum(r) - sum(l - 1);
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> a[i][0] >> a[i][1] >> a[i][2];
        events[0].PB({0, i});
        pos[i] = -1;
    }

    for (int i = 0; i < TIM; i++)
        OSS[i] = i % 100;

    OST[0] = 0;

    for (int i = 1; i <= n; i++)
        OST[i] = i % 20;

    cin >> m;

    for (int i = 0; i < m; i++){
        int x; cin >> x;
        loc[x] = 1;
    }

    for (int tim = 0; tim < TIM; tim++){
        if (sz(events[tim]) == 0) continue;

        sort(all(events[tim]));

//        if (tim == 600) {
//            cerr << "ok\n";
//            for (auto c : events[tim])
//                cerr << c[0] << " " << c[1] << '\n';
//        }

        for (array<int, 2> cr : events[tim])
            if (pos[cr[1]] >= 0)
                update(pos[cr[1]], -1);

        int kol = n;

        for (int it = sz(events[tim]) - 1; it >= 0; ){

            int jt = it;

            while (jt >= 0 && events[tim][it][0] == events[tim][jt][0])
                jt--;

            int i = events[tim][it][0];

            if (i < 300) {
                int kol = sum(i, 300);
                int ost = min(300 - i, OST[kol]);

                if (loc[i] && ost > 0){
                    for (int I = it; I > jt; I--){
                        int cr = events[tim][I][1];
                        pos[cr]++;

                        int speed = a[cr][0];

                        if (i > 99)
                            speed = a[cr][1];
                        if (i > 199)
                            speed = a[cr][2];

                        if (fast[cr] > 0){
                            events[tim + 1].PB({i + 1, cr});
                            mem[cr] = tim + 1;
                            fast[cr]--;
                        } else {
                            fast[cr] = ost - 1;
                            mem[cr] = tim + 1;

                            events[tim + 1].PB({i + 1, cr});

                            if (OSS[(i + 1)] == 0)
                                mem[cr] = tim + 1;
                        }
                    }
                } else {
                    for (int I = it; I > jt; I--){
                        int cr = events[tim][I][1];
                        pos[cr]++;

                        int speed = a[cr][0];

                        if (i > 99)
                            speed = a[cr][1];
                        if (i > 199)
                            speed = a[cr][2];

                        if (fast[cr] > 0){
                            events[tim + 1].PB({i + 1, cr});
                            mem[cr] = tim + 1;
                            fast[cr]--;
                        } else {
                            events[tim + speed].PB({i + 1, cr});

                            if (OSS[(i + 1)] == 0)
                                mem[cr] = tim + speed;
                        }
                    }
                }

                update(i, it - jt);

            } else {
                for (int I = it; I > jt; I--)
                    ans[events[tim][I][1]] = tim;
                update(300, it - jt);
            }

            it = jt;
        }
    }

    for (int i = 0; i < n; i++)
        cout << ans[i] << '\n';

    return 0;
}

Compilation message (stderr)

segway.cpp: In function 'int main()':
segway.cpp:100:29: warning: variable 'speed' set but not used [-Wunused-but-set-variable]
                         int speed = a[cr][0];
                             ^~~~~
segway.cpp:80:13: warning: unused variable 'kol' [-Wunused-variable]
         int kol = n;
             ^~~

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