oj.uz

Submission #233638

# Submission time Handle Problem Language Result Execution time Memory
233638 2020-05-21T08:01:45 Z Vimmer Segway (COI19_segway) C++14
100 / 100
 264 ms 37780 KB 
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")

#define sz(x) ll(x.size())
#define base 1000000
#define M ll(1e9+7)
#define F first
#define S second
#define pb push_back
#define in insert
#define eb emplace_back
#define ed "\n"

using namespace std;
//using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef short int si;

//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
//


int t[305], pos[20005], dob[20005], been[20005];

bool booster[305];

void upd(int v, int val) {for (; v < 305; v = (v | (v + 1))) t[v] += val;}

int get(int v) {int res = 0; for (; v >= 0; v = (v & (v + 1)) - 1) res += t[v]; return res;}

unordered_map <int, int> koler;

vector <int> g[15005];

int main()
{
//    freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);

    ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n;

    cin >> n;

    int a[n], b[n], c[n];

    int mx = 0;

    for (int i = 0; i < n; i++) {cin >> a[i] >> b[i] >> c[i]; mx = max(mx, (a[i] + b[i] + c[i]) * 100);}

    int m;

    cin >> m;

    for (; m > 0; m--) {int t; cin >> t; booster[t] = 1;}

    int ans[n];

    for (int i = 0; i < n; i++) {g[a[i]].pb(i); upd(0, 1);}

    for (int i = 1; i <= mx; i++)
    {
        vector <pair <int, int> > check; check.clear();

        koler.clear();

        for (auto j : g[i])
        {
            int lst = pos[j];

            if (lst == 300) continue;

            int spd = 0;

            if (dob[j] != 0) {spd = 1; dob[j]--;}
              else if (lst < 100) spd = a[j];
                else if (lst < 200) spd = b[j];
                  else spd = c[j];

            if (i - been[j] >= spd)
            {
                been[j] = i;

                pos[j] = lst + 1;

                koler[lst + 1]++;

                upd(lst, -1);

                upd(lst + 1, 1);

                if (dob[j] != 0) spd = 1;
                  else if (lst + 1 < 100) spd = a[j];
                    else if (lst + 1 < 200) spd = b[j];
                      else spd = c[j];

                if (booster[pos[j]]) check.pb({j, spd});
                 else g[i + spd].pb(j);

                if (lst + 1 == 300) ans[j] = i;
            } else pos[j] = lst;
        }

        for (auto it : check)
        {
            if (dob[it.F] != 0) {g[i + it.S].pb(it.F); continue;}

            int kol = n - get(pos[it.F] - 1) - koler[pos[it.F]];

            dob[it.F] = kol % 20;

            if (dob[it.F] != 0) g[i + 1].pb(it.F); else g[i + it.S].pb(it.F);
        }
    }

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

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 768 KB Output is correct
2 Correct 11 ms 1152 KB Output is correct
3 Correct 25 ms 2176 KB Output is correct
4 Correct 65 ms 6008 KB Output is correct
5 Correct 264 ms 32888 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 768 KB Output is correct
2 Correct 6 ms 768 KB Output is correct
3 Correct 5 ms 768 KB Output is correct
4 Correct 5 ms 768 KB Output is correct
5 Correct 6 ms 896 KB Output is correct
6 Correct 7 ms 768 KB Output is correct
7 Correct 8 ms 896 KB Output is correct
8 Correct 11 ms 1024 KB Output is correct
9 Correct 12 ms 1152 KB Output is correct
10 Correct 14 ms 1280 KB Output is correct
11 Correct 12 ms 1152 KB Output is correct

Subtask #3
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 768 KB Output is correct
2 Correct 11 ms 1152 KB Output is correct
3 Correct 25 ms 2176 KB Output is correct
4 Correct 65 ms 6008 KB Output is correct
5 Correct 264 ms 32888 KB Output is correct
6 Correct 5 ms 768 KB Output is correct
7 Correct 6 ms 768 KB Output is correct
8 Correct 5 ms 768 KB Output is correct
9 Correct 5 ms 768 KB Output is correct
10 Correct 6 ms 896 KB Output is correct
11 Correct 7 ms 768 KB Output is correct
12 Correct 8 ms 896 KB Output is correct
13 Correct 11 ms 1024 KB Output is correct
14 Correct 12 ms 1152 KB Output is correct
15 Correct 14 ms 1280 KB Output is correct
16 Correct 12 ms 1152 KB Output is correct
17 Correct 29 ms 2552 KB Output is correct
18 Correct 37 ms 4216 KB Output is correct
19 Correct 125 ms 14840 KB Output is correct
20 Correct 170 ms 19732 KB Output is correct
21 Correct 207 ms 23496 KB Output is correct
22 Correct 242 ms 28704 KB Output is correct
23 Correct 234 ms 37780 KB Output is correct