oj.uz

Submission #1062310

# Submission time Handle Problem Language Result Execution time Memory
1062310 2024-08-17T02:58:46 Z steveonalex Train (APIO24_train) C++17
40 / 100
 560 ms 83920 KB 
#include <bits/stdc++.h>
#include "train.h" 


using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
#define MASK(i) (1LL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
#define ALL(v) (v).begin(), (v).end()
#define block_of_code if(true)
 
ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
ll gcd(ll a, ll b){return __gcd(a, b);}
ll lcm(ll a, ll b){return a / gcd(a, b) * b;}
 
ll LASTBIT(ll mask){return (mask) & (-mask);}
int pop_cnt(ll mask){return __builtin_popcountll(mask);}
int ctz(ull mask){return __builtin_ctzll(mask);}
int logOf(ull mask){return 63 - __builtin_clzll(mask);}
 
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll rngesus(ll l, ll r){return l + (ull) rng() % (r - l + 1);}
 
template <class T1, class T2>
    bool maximize(T1 &a, T2 b){
        if (a < b) {a = b; return true;}
        return false;
    }
 
template <class T1, class T2>
    bool minimize(T1 &a, T2 b){
        if (a > b) {a = b; return true;}
        return false;
    }
 
template <class T>
    void printArr(T container, string separator = " ", string finish = "\n", ostream &out = cout){
        for(auto item: container) out << item << separator;
        out << finish;
    }
 
template <class T>
    void remove_dup(vector<T> &a){
        sort(ALL(a));
        a.resize(unique(ALL(a)) - a.begin());
    }


const ll INF = 1e18 + 69;
const int INF_T = 1e9 + 69;
const int N = 1e5 + 65;
const int BLOCK = 2000;

struct FenwickTree{
    const int BLOCK = 500;
    int n;
    vector<int> a, b_sum;

    FenwickTree(int _n){
        n = _n;
        a.resize(n+1);
        b_sum.resize(n / BLOCK + 2);
    }

    void update(int i, int v){
        int m = i % BLOCK;
        while(m--)
            a[i--] += v;
        i /= BLOCK;
        while(i) b_sum[i--] += v;
    }

    int get(int i){
        int ans = a[i] + b_sum[(i-1) / BLOCK + 1];
        return ans;
    }
};

struct SegmentTree{
    #define SZ MASK(19)
    int n, t;
    array<ll, SZ> a;
    array<int, SZ> lazy;

    SegmentTree(int _n, int _t){
        n = _n, t = _t;
        for(int i = 0; i < SZ; ++i) {
            a[i] = INF;
            lazy[i] = 0;
        }
    }

    void down(int id){
        #define cuhh(i) {lazy[i] += lazy[id]; a[i] += lazy[id];}
        cuhh(id * 2); cuhh(id * 2 + 1);
        lazy[id] = 0;
    }

    void add(int u, int v, int l, int r, int id){
        if (u <= l && r <= v){
            a[id] += t;
            lazy[id] += t;
            return;
        }
        if (lazy[id]) down(id);
        int mid = (l + r) >> 1;
        if (u <= mid) add(u, v, l, mid, id * 2);
        if (v > mid) add(u, v, mid + 1, r, id * 2 + 1);
        a[id] = min(a[id * 2], a[id * 2 + 1]);
    }

    void add(int u, int v){
        if (u <= v) add(u, v, 1, n, 1);
    }


    ll get(){return a[1];}

    void update(int i, ll val){
        int l = 1, r = n, id = 1;
        while(l < r){
            minimize(a[id], val);
            if (lazy[id]) down(id);
            int mid = (l + r) >> 1;
            if (i <= mid){
                r = mid;
                id = id * 2;
            }
            else{
                l = mid + 1;
                id = id * 2 + 1;
            }
        }
        minimize(a[id], val);
    }
}; 

vector<pair<int,ll>> relevant_time[N];
vector<pair<int, int>> graph[N * 2];

ll solve(int n, int m, int w, vector<int> t, 
                vector<int> x, vector<int> y, vector<int> a, vector<int> b, vector<int> c, 
                vector<int> l, vector<int> r) {

    vector<int> timeline = {-1, 0, INF_T};
    for(int i = 0; i<m; ++i){
        timeline.push_back(a[i]);
        timeline.push_back(b[i]);
    }
    remove_dup(timeline);

    for(int i= 0; i<m; ++i){
        a[i] = lower_bound(ALL(timeline), a[i]) - timeline.begin();
        b[i] = lower_bound(ALL(timeline), b[i]) - timeline.begin();
    }

    vector<pair<int, int>> relevant_pair;
    for(int i = 0; i<m; ++i){
        relevant_pair.push_back({a[i], x[i]});
        relevant_pair.push_back({b[i], y[i]});
    }
    relevant_pair.push_back({1, 0});
    relevant_pair.push_back({timeline.size() - 1, n-1});
    remove_dup(relevant_pair);

    vector<int> des_cnt(n);
    for(int i = 0; i<m; ++i) des_cnt[y[i]]++;

    vector<int> big_boys;
    vector<SegmentTree> st;
    for(int i = 0; i<n; ++i) if (des_cnt[i] > BLOCK){
        big_boys.push_back(i);
        st.push_back(SegmentTree(timeline.size() - 1, t[i]));
    }

    for(int i = 0; i<m; ++i){
        pair<int, int> u = {a[i], x[i]}, v = {b[i], y[i]};
        int idx1 = lower_bound(ALL(relevant_pair), u) - relevant_pair.begin();
        int idx2 = lower_bound(ALL(relevant_pair), v) - relevant_pair.begin();
        graph[idx2].push_back({idx1, c[i]});
    }

    vector<pair<int, int>> range;
    for(int i = 0; i<w; ++i) {
        r[i] = upper_bound(ALL(timeline), r[i]) - timeline.begin() - 1;
        l[i] = lower_bound(ALL(timeline), l[i]) - timeline.begin() - 1;
        range.push_back({l[i], r[i]});
    }
    sort(ALL(range), [](pair<int,int> x, pair<int, int> y){
        return x.second > y.second;
    });

    FenwickTree bit(timeline.size() - 1);

    vector<ll> dis(relevant_pair.size(), INF), dp = dis;
    dis[0] = dp[0] = 0;
    for(int i = 0; i < relevant_pair.size(); ++i){
        pair<int, int> u = relevant_pair[i];
        while(range.size() && u.first > range.back().second){
            pair<int, int> cur = range.back(); range.pop_back();
            bit.update(cur.first, 1);
            for(int j = 0; j < big_boys.size(); ++j){
                st[j].add(1, cur.first);
            }
        }
        for(pair<int, int> j: graph[i]) {
            minimize(dis[i], dis[j.first] + j.second);
            minimize(dp[i], dis[j.first] + j.second);
        }
        if (des_cnt[u.second] <= BLOCK){
            for(pair<int, ll> j: relevant_time[u.second]){
                ll cur = j.second;
                cur += 1LL * bit.get(j.first) * t[u.second];
                minimize(dis[i], cur);
            }
            if (dp[i] < INF) {
                relevant_time[u.second].push_back({u.first, dp[i]});
            }
        }
        else{
            int idx = lower_bound(ALL(big_boys), u.second) - big_boys.begin();
            minimize(dis[i], st[idx].get());
            if (dp[i] < INF) {
                st[idx].update(u.first, dp[i]);
            }
        }
    }

    if (dis.back() == INF) return -1;
    return dis.back();
}


// int main(void){
//     ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

//     clock_t start = clock();

//     int n, m, w; cin >> n >> m >> w;
//     vector<int> t(n), x(m), y(m), a(m), b(m), c(m), l(w), r(w);
//     for(int &i: t) cin >> i;

//     for(int i = 0; i<m; ++i){
//         cin >> x[i] >> y[i] >> a[i] >> b[i] >> c[i];
//     }

//     for(int i = 0; i < w; ++i) cin >> l[i] >> r[i];

//     cout << solve(n, m, w, t, x, y, a, b, c, l, r) << "\n";


//     cerr << "Time elapsed: " << clock() - start << " ms\n";

//     return 0;
// }

/*
input 1:

3 3 1
20 30 40
0 1 1 15 10
1 2 20 30 5
0 2 18 40 40
16 19

input 2:
3 5 6
30 38 33
0 2 12 16 38
1 0 48 50 6
0 1 26 28 23
0 2 6 7 94
1 2 49 54 50
32 36
14 14
42 45
37 40
2 5
4 5


*/

Compilation message

train.cpp: In function 'll solve(int, int, int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
train.cpp:201:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  201 |     for(int i = 0; i < relevant_pair.size(); ++i){
      |                    ~~^~~~~~~~~~~~~~~~~~~~~~
train.cpp:206:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  206 |             for(int j = 0; j < big_boys.size(); ++j){
      |                            ~~^~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 13656 KB Correct.
2 Correct 5 ms 13660 KB Correct.
3 Correct 9 ms 13648 KB Correct.
4 Correct 5 ms 13656 KB Correct.
5 Correct 4 ms 13404 KB Correct.
6 Correct 4 ms 13404 KB Correct.
7 Correct 5 ms 13400 KB Correct.

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 29632 KB Correct.
2 Correct 109 ms 30616 KB Correct.
3 Correct 5 ms 13404 KB Correct.
4 Correct 15 ms 14804 KB Correct.
5 Correct 5 ms 13400 KB Correct.
6 Correct 140 ms 29744 KB Correct.
7 Correct 5 ms 13400 KB Correct.
8 Correct 78 ms 40132 KB Correct.
9 Correct 136 ms 30576 KB Correct.

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 29632 KB Correct.
2 Correct 109 ms 30616 KB Correct.
3 Correct 5 ms 13404 KB Correct.
4 Correct 15 ms 14804 KB Correct.
5 Correct 5 ms 13400 KB Correct.
6 Correct 140 ms 29744 KB Correct.
7 Correct 5 ms 13400 KB Correct.
8 Correct 78 ms 40132 KB Correct.
9 Correct 136 ms 30576 KB Correct.
10 Correct 167 ms 31940 KB Correct.
11 Correct 165 ms 39876 KB Correct.
12 Correct 14 ms 15196 KB Correct.
13 Correct 4 ms 13404 KB Correct.
14 Correct 321 ms 83920 KB Correct.
15 Correct 177 ms 39876 KB Correct.
16 Correct 560 ms 37056 KB Correct.
17 Correct 161 ms 48576 KB Correct.

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 13656 KB Correct.
2 Correct 5 ms 13660 KB Correct.
3 Correct 9 ms 13648 KB Correct.
4 Correct 5 ms 13656 KB Correct.
5 Correct 4 ms 13404 KB Correct.
6 Correct 4 ms 13404 KB Correct.
7 Correct 5 ms 13400 KB Correct.
8 Correct 108 ms 29632 KB Correct.
9 Correct 109 ms 30616 KB Correct.
10 Correct 5 ms 13404 KB Correct.
11 Correct 15 ms 14804 KB Correct.
12 Correct 5 ms 13400 KB Correct.
13 Correct 140 ms 29744 KB Correct.
14 Correct 5 ms 13400 KB Correct.
15 Correct 78 ms 40132 KB Correct.
16 Correct 136 ms 30576 KB Correct.
17 Correct 167 ms 31940 KB Correct.
18 Correct 165 ms 39876 KB Correct.
19 Correct 14 ms 15196 KB Correct.
20 Correct 4 ms 13404 KB Correct.
21 Correct 321 ms 83920 KB Correct.
22 Correct 177 ms 39876 KB Correct.
23 Correct 560 ms 37056 KB Correct.
24 Correct 161 ms 48576 KB Correct.
25 Correct 182 ms 40040 KB Correct.
26 Correct 172 ms 39876 KB Correct.
27 Correct 190 ms 39872 KB Correct.
28 Correct 205 ms 39876 KB Correct.
29 Correct 172 ms 37828 KB Correct.
30 Correct 187 ms 37060 KB Correct.
31 Correct 185 ms 36964 KB Correct.
32 Correct 183 ms 37060 KB Correct.
33 Incorrect 306 ms 83884 KB Integer -318184804855 violates the range [-1, 10^18]
34 Halted 0 ms 0 KB -