Submission #1061527

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061527		dozer	Overtaking (IOI23_overtaking)	C++17	0 / 100	3 ms	14940 KiB

overtaking

#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
#define sp " "
#define endl "\n"
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define LL node * 2
#define RR node * 2 + 1
#define ll long long
#define MAXN 300005
#define LOGN 20


const int modulo = 1e9 + 7;
const ll INF = 2e18 + 7;



struct SegTree{
    vector<vector<int>> tree;
    vector<int> compress;
    int n;

    void add(int node, int l, int r, int sl, int val){
        tree[node].pb(-val);
        if (l == r) return;
        int mid = (l + r) / 2;
        if (sl <= mid) add(LL, l, mid, sl, val);
        else add(RR, mid + 1, r, sl, val);
    }

    SegTree(vector<pii> arr){
        n = arr.size();
        sort(arr.begin(), arr.end());
        for (auto i : arr) compress.pb(i.st);
        unique(compress.begin(), compress.end());

        sort(arr.begin(), arr.end(), [&](pii a, pii b){
            return make_pair(-a.nd, a.st) < make_pair(-b.nd, b.st);
        });

        n = compress.size();
        tree.resize(4 * n + 5);

        for (auto i : arr){
            int pos = upper_bound(compress.begin(), compress.end(), i.st) - compress.begin();
            pos--;
            add(1, 0, n - 1, pos, i.nd);
        }
    }

    int query(int node, int l, int r, int sl, int sr, int val){
        if (l > sr || r < sl) return 0;
        if (l >= sl && r <= sr) {
            return lower_bound(tree[node].begin(), tree[node].end(), -val) - tree[node].begin();
        }

        int mid = (l + r) / 2;
        return query(LL, l, mid, sl, sr, val) + query(RR, mid + 1, r, sl, sr, val);
    }

    int query_good(int pos, int val){

        int l = 0, r = lower_bound(compress.begin(), compress.end(), pos) - compress.begin();
        if (r == 0) return 0;
        r--;
        int res = query(1, 0, n - 1, 0, r, val);
        return res;
    }
};

vector<SegTree*> trees;
vector<ll> ANS;
vector<vector<array<int, 3>>> CURR;
vector<vector<ll>> TO;
int s[MAXN], m;


map<int, int> dp[MAXN];
int x;


ll compute(int ind, int pos){
    if (ind == m - 1) return pos;
    if (dp[ind].count(pos)) return dp[ind][pos];
    int ans = ind;

    int curr_cnt = trees[ind]->query_good(pos, x);

    for (int i = LOGN; i >= 0; i--){
        int to = ans + (1<<i);
        if (to >= m) continue;
        ll dist = s[to] - s[ind];
        ll tmp_pos = pos + dist * x;
        int cnt = trees[to]->query_good(tmp_pos, x);

        if (cnt == curr_cnt) ans = to;
    }

    int dist = s[ans] - s[ind];
    int new_pos = pos + dist * x;
    if (ans == m - 1) {
        return dp[ind][pos] = new_pos;
    }
    int poss = upper_bound(CURR[ans].begin(), CURR[ans].end(), array<int, 3>({pos, x, 0})) - CURR[ans].begin();
    poss--;
    ll to = TO[ans][CURR[ans][poss][2]];
    int val = compute(ans + 1, to);
    return dp[ind][pos] = val;
}

void init(int L, int N, vector<long long> T, vector<int> W, int X, int M, vector<int> S)
{   
    x = X;

    vector<int> curr(N, 0);
    int n = N;
    m = M;
    for (int i = 0; i < M; i++) s[i] = S[i];

    for (int i = 0; i < n; i++) curr[i] = T[i];
    

    vector<pii> arr;
    for (int j = 0; j < N; j++) arr.pb({curr[j], W[j]});

    vector<array<int, 3>> tmp;
    for (int i = 0; i < n; i++) tmp.pb({curr[i], W[i], i});
    sort(tmp.begin(), tmp.end());
    CURR.pb(tmp);

    SegTree *x = new SegTree(arr);
    trees.pb(x);

    for (int i = 1; i < M; i++){
        vector<int> todo(n);
        iota(todo.begin(), todo.end(), 0);
        sort(todo.begin(), todo.end(), [&](int a, int b){
            return make_pair(curr[a], W[a]) < make_pair(curr[b], W[b]);
        }); 

        ll dist = S[i] - S[i - 1];
        ll mini = 0;
        for (auto j : todo){
            ll to = curr[j] + dist * W[j];
            curr[j] = max(mini, to);
            mini = max(mini, to);
        }

        vector<pii> arr;
        for (int j = 0; j < N; j++) arr.pb({curr[j], W[j]});
       
        SegTree *x = new SegTree(arr);
        trees.pb(x);
        vector<array<int, 3>> tmp;

        for (int i = 0; i < n; i++) tmp.pb({curr[i], W[i], i});
        sort(tmp.begin(), tmp.end());
        CURR.pb(tmp);

        vector<ll> too;
        for (int i = 0; i < n; i++) too.pb(curr[i]);
        TO.pb(too);
    }

}

long long arrival_time(long long Y)
{
    return compute(0, Y);
}

/*
int main()
{
    fileio();
    int L, N, X, M, Q;
    assert(5 == scanf("%d %d %d %d %d", &L, &N, &X, &M, &Q));
    std::vector<long long> T(N);
    for (int i = 0; i < N; i++)
        assert(1 == scanf("%lld", &T[i]));
    std::vector<int> W(N);
    for (int i = 0; i < N; i++)
        assert(1 == scanf("%d", &W[i]));
    std::vector<int> S(M);
    for (int i = 0; i < M; i++)
        assert(1 == scanf("%d", &S[i]));
    std::vector<long long> Y(Q);
    for (int i = 0; i < Q; i++)
        assert(1 == scanf("%lld", &Y[i]));

    fclose(stdin);

    init(L, N, T, W, X, M, S);
    std::vector<long long> res(Q);
    for (int i = 0; i < Q; i++)
        res[i] = arrival_time(Y[i]);

    for (int i = 0; i < Q; i++)
        printf("%lld\n", res[i]);
    fclose(stdout);
    return 0;
}*/

Compilation message (stderr)

overtaking.cpp: In member function 'int SegTree::query_good(int, int)':
overtaking.cpp:69:13: warning: unused variable 'l' [-Wunused-variable]
   69 |         int l = 0, r = lower_bound(compress.begin(), compress.end(), pos) - compress.begin();
      |             ^

• Subtask 0: 0 / 0
• Subtask 1: 0 / 9
• Subtask 2: 0 / 10
• Subtask 3: 0 / 20
• Subtask 4: 0 / 26
• Subtask 5: 0 / 35