Submission #1081055

#	Time	Username	Problem	Language	Result	Execution time	Memory
1081055		Ausp3x	Overtaking (IOI23_overtaking)	C++17	0 / 100	1 ms	348 KiB

overtaking

// 人外有人，天外有天
// author: Ausp3x

#pragma GCC optimize("O1, O2, O3, Ofast, unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include "overtaking.h"
using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define pb push_back
// #define DEBUG
typedef long long    lng;
typedef __int128     lli;
template<class T> 
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

int const INF32 = 0x3f3f3f3f;
lng const INF64 = 0x3f3f3f3f3f3f3f3f;

struct SegTree {    
    lng yl, yr;
    SegTree *l_child, *r_child;

    lng zl, zr, upd = 0;
 
    SegTree(lng yl, lng yr, lng zl, lng zr): yl(yl), yr(yr), zl(zl), zr(zr) {};

    void push() {
        if (l_child != nullptr && r_child != nullptr) {
            l_child->zl += upd;
            l_child->zr += upd;
            l_child->upd += upd;
            r_child->zl += upd;
            r_child->zr += upd;
            r_child->upd += upd;
        }
        upd = 0;

        return;
    }

    void pull() {
        assert(upd == 0);
        if (l_child != nullptr && r_child != nullptr) {
            zl = l_child->zl;
            zr = r_child->zr;
        }

        return;
    }

    void createChildren() {
        if (yr - yl != zr - zl) {
            return;
        }

        lng ym = (yl + yr) / 2;
        l_child = new SegTree(yl, ym, zl, zl + ym - yl);
        r_child = new SegTree(ym + 1, yr, zl + ym - yl + 1, zr);

        return;
    }

    void deleteChildren() {
        delete l_child;
        delete r_child;

        return;
    }

    void rangeAdd(lng cur_zl, lng cur_zr, lng t) {
        if (cur_zl > cur_zr || (zr < cur_zl || cur_zr < zl)) {
            return;
        }

        if (cur_zl <= zl && zr <= cur_zr) {
            zl += t;
            zr += t;
            upd += t;
            return;
        }
        
        push();
        createChildren();
        l_child->rangeAdd(cur_zl, cur_zr, t);
        r_child->rangeAdd(cur_zl, cur_zr, t);
        pull();

        return;
    }

    // for this function to work
    // 1) ranges must NOT overlap
    // 2) ranges must be done last to first
    void rangeFix(lng cur_zl, lng cur_zr, lng z) {
        if (cur_zl > cur_zr || (zr < cur_zl || cur_zr < zl)) {
            return;
        }

        if (cur_zl <= zl && zr <= cur_zr) {
            zl = z;
            zr = z;
            deleteChildren();
            return;
        }
        
        push();
        createChildren();
        l_child->rangeFix(cur_zl, cur_zr, z);
        r_child->rangeFix(cur_zl, cur_zr, z);
        pull();

        return;
    }

    lng singleQuery(lng y) {
        assert(yl <= y && y <= yr);
        if (l_child == nullptr && r_child == nullptr) {
            if (zl == zr) {
                return zl;
            } else if (yr - yl == zr - zl) {
                return zl + y - yl;
            }
            return -1;
        }

        push();
        if (l_child->yl <= y && y <= l_child->yr) {
            return l_child->singleQuery(y);
        } else if (r_child->yl <= y && y <= r_child->yr) {
            return r_child->singleQuery(y);
        }

        return -1;
    }

    void debugPrint(int depth = 0) {
        for (int t = 0; t < depth; t++) {
            cout << '\t';
        }
        cout << "[" << yl << ", " << yr << "] has [" << zl << ", " << zr << "] and upd " << upd << endl;
        if (l_child != nullptr && r_child != nullptr) {
            l_child->debugPrint(depth + 1);
            r_child->debugPrint(depth + 1);
        }

        return;
    }
};


lng Y_MAX = 2'000;
SegTree *segt = new SegTree(0, Y_MAX, 0, Y_MAX);

void init(int L, int N, vector<lng> T, vector<int> W, int X, int M, vector<int> S) {
    vector<int> buses_slower_than_reserve;
    // time bus i arrives at station j
    vector<vector<lng>> arrival_times(N, vector<lng>(M));
    for (int i = 0; i < N; i++) {
        if (W[i] > X)
            buses_slower_than_reserve.pb(i);
        arrival_times[i][0] = T[i];
    } 
    for (int j = 1; j < M; j++) {
        priority_queue<pair<lng, int>, vector<pair<lng, int>>, greater<pair<lng, int>>> pq;
        for (int i = 0; i < N; i++) 
            pq.push({arrival_times[i][j - 1], i});
    
        lng t = 0;
        while (!pq.empty()) {
            auto [t_prv, i] = pq.top();
            pq.pop();

            lng e = t_prv + 1ll * W[i] * (S[j] - S[j - 1]);
            t = max(t, e);
            arrival_times[i][j] = t;
        }
    }

    // for (int i : buses_slower_than_reserve)
    //     cout << i << ' ';
    // cout << endl;

    // for (int i = 0; i < N; i++) {
    //     for (int j = 0; j < M; j++)
    //         cout << arrival_times[i][j] << ' ';
    //     cout << endl;
    // }

    lng offset = 0;
    for (int j = 1; j < M; j++) {
        segt->rangeAdd(offset, Y_MAX + offset, 1ll * X * (S[j] - S[j - 1]));
        // segt->debugPrint();
        // cout << endl;

        vector<tuple<lng, lng, lng>> V;
        for (int i : buses_slower_than_reserve)
            V.pb({arrival_times[i][j] + 1ll * (X - W[i]) * (S[j] - S[j - 1]) + 1, arrival_times[i][j], arrival_times[i][j]});

        sort(V.begin(), V.end());

        for (int i = 1; i < V.size(); i++)
            get<1>(V[i - 1]) = min(get<1>(V[i - 1]), get<0>(V[i]) - 1);

        reverse(V.begin(), V.end());

        for (auto [cur_zl, cur_zr, z] : V) {
            if (cur_zl > cur_zr)
                continue;

            // cout << cur_zl << ' ' << cur_zr << ' ' << z << endl;
            
            segt->rangeFix(cur_zl, cur_zr, z);
            // segt->debugPrint();
            // cout << endl;
        }
        
        offset += 1ll * X * (S[j] - S[j - 1]);
    }

    return;
}

lng arrival_time(lng Y) {
    return segt->singleQuery(Y);
}

#ifdef DEBUG
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t = 1;
    // cin >> t;
    while (t--) {
        int L, N, X, M, Q;
        cin >> L >> N >> X >> M >> Q;
        vector<lng> T(N);
        for (lng &t : T)
            cin >> t;
        vector<int> W(N);
        for (int &w : W)
            cin >> w;
        vector<int> S(M);
        for (int &s : S)
            cin >> s;

        init(L, N, T, W, X, M, S);

        segt->debugPrint();

        while (Q--) {
            int Y;
            cin >> Y;
            
            cout << arrival_time(Y) << endl;
        }
    }

    return 0;
}
#endif

Compilation message (stderr)

overtaking.cpp:4:55: warning: bad option '-f O2' to pragma 'optimize' [-Wpragmas]
    4 | #pragma GCC optimize("O1, O2, O3, Ofast, unroll-loops")
      |                                                       ^
overtaking.cpp:4:55: warning: bad option '-f O3' to pragma 'optimize' [-Wpragmas]
overtaking.cpp:4:55: warning: bad option '-f Ofast' to pragma 'optimize' [-Wpragmas]
overtaking.cpp:4:55: warning: bad option '-f unroll-loops' to pragma 'optimize' [-Wpragmas]
In file included from overtaking.cpp:7:
overtaking.h:3:103: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
    3 | void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S);
      |                                                                                                       ^
overtaking.h:3:103: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
overtaking.h:3:103: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
overtaking.h:3:103: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
overtaking.h:3:103: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
overtaking.h:3:103: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
overtaking.h:3:103: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
overtaking.h:3:103: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
overtaking.h:5:35: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
    5 | long long arrival_time(long long Y);
      |                                   ^
overtaking.h:5:35: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
overtaking.h:5:35: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
overtaking.h:5:35: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
overtaking.h:5:35: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
overtaking.h:5:35: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
overtaking.h:5:35: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
overtaking.h:5:35: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
overtaking.cpp:29:43: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
   29 |     SegTree(lng yl, lng yr, lng zl, lng zr): yl(yl), yr(yr), zl(zl), zr(zr) {};
      |                                           ^
overtaking.cpp:29:43: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
overtaking.cpp:29:43: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
overtaking.cpp:29:43: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
overtaking.cpp:31:15: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
   31 |     void push() {
      |               ^
overtaking.cpp:31:15: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
overtaking.cpp:31:15: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
overtaking.cpp:31:15: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
overtaking.cpp:45:15: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
   45 |     void pull() {
      |               ^
overtaking.cpp:45:15: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
overtaking.cpp:45:15: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
overtaking.cpp:45:15: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
overtaking.cpp:55:25: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
   55 |     void createChildren() {
      |                         ^
overtaking.cpp:55:25: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
overtaking.cpp:55:25: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
overtaking.cpp:55:25: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
overtaking.cpp:67:25: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
   67 |     void deleteChildren() {
      |                         ^
overtaking.cpp:67:25: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
overtaking.cpp:67:25: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
overtaking.cpp:67:25: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
overtaking.cpp:74:48: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
   74 |     void rangeAdd(lng cur_zl, lng cur_zr, lng t) {
      |                                                ^
overtaking.cpp:74:48: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
overtaking.cpp:74:48: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
overtaking.cpp:74:48: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
overtaking.cpp:98:48: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
   98 |     void rangeFix(lng cur_zl, lng cur_zr, lng z) {
      |                                                ^
overtaking.cpp:98:48: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
overtaking.cpp:98:48: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
overtaking.cpp:98:48: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
overtaking.cpp:119:26: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
  119 |     lng singleQuery(lng y) {
      |                          ^
overtaking.cpp:119:26: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
overtaking.cpp:119:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
overtaking.cpp:119:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
overtaking.cpp:140:34: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
  140 |     void debugPrint(int depth = 0) {
      |                                  ^
overtaking.cpp:140:34: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
overtaking.cpp:140:34: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
overtaking.cpp:140:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
overtaking.cpp:158:82: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
  158 | void init(int L, int N, vector<lng> T, vector<int> W, int X, int M, vector<int> S) {
      |                                                                                  ^
overtaking.cpp:158:82: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
overtaking.cpp:158:82: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
overtaking.cpp:158:82: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
overtaking.cpp: In function 'void init(int, int, std::vector<long long int>, std::vector<int>, int, int, std::vector<int>)':
overtaking.cpp:205:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<long long int, long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  205 |         for (int i = 1; i < V.size(); i++)
      |                         ~~^~~~~~~~~~
overtaking.cpp: At global scope:
overtaking.cpp:227:23: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
  227 | lng arrival_time(lng Y) {
      |                       ^
overtaking.cpp:227:23: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
overtaking.cpp:227:23: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
overtaking.cpp:227:23: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]

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