oj.uz

Submission #233356

# Submission time Handle Problem Language Result Execution time Memory
233356 2020-05-20T10:12:31 Z VEGAnn Segway (COI19_segway) C++14
0 / 100
 12 ms 1664 KB 
#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]));
        reverse(all(events[tim]));

        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];

//            cerr << i << '\n';

            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

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

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 896 KB Output is correct
2 Incorrect 12 ms 1664 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 896 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 896 KB Output is correct
2 Incorrect 12 ms 1664 KB Output isn't correct
3 Halted 0 ms 0 KB -