oj.uz

Submission #1108855

# Submission time Handle Problem Language Result Execution time Memory
1108855 2024-11-05T11:37:46 Z ducanh1234 Train (APIO24_train) C++17
100 / 100
 620 ms 85680 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] += 1LL * t * 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] += 1;
            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();
}

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 8 ms 13648 KB Correct.
2 Correct 8 ms 13648 KB Correct.
3 Correct 8 ms 13648 KB Correct.
4 Correct 8 ms 13648 KB Correct.
5 Correct 7 ms 13648 KB Correct.
6 Correct 7 ms 13508 KB Correct.
7 Correct 7 ms 13648 KB Correct.

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 33976 KB Correct.
2 Correct 124 ms 35924 KB Correct.
3 Correct 8 ms 13648 KB Correct.
4 Correct 14 ms 15364 KB Correct.
5 Correct 7 ms 13648 KB Correct.
6 Correct 171 ms 33744 KB Correct.
7 Correct 8 ms 13648 KB Correct.
8 Correct 102 ms 44168 KB Correct.
9 Correct 184 ms 36156 KB Correct.

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 33976 KB Correct.
2 Correct 124 ms 35924 KB Correct.
3 Correct 8 ms 13648 KB Correct.
4 Correct 14 ms 15364 KB Correct.
5 Correct 7 ms 13648 KB Correct.
6 Correct 171 ms 33744 KB Correct.
7 Correct 8 ms 13648 KB Correct.
8 Correct 102 ms 44168 KB Correct.
9 Correct 184 ms 36156 KB Correct.
10 Correct 203 ms 38344 KB Correct.
11 Correct 200 ms 40376 KB Correct.
12 Correct 16 ms 15184 KB Correct.
13 Correct 8 ms 13648 KB Correct.
14 Correct 298 ms 85676 KB Correct.
15 Correct 202 ms 40440 KB Correct.
16 Correct 620 ms 37752 KB Correct.
17 Correct 175 ms 49120 KB Correct.

Subtask #4
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 13648 KB Correct.
2 Correct 8 ms 13648 KB Correct.
3 Correct 8 ms 13648 KB Correct.
4 Correct 8 ms 13648 KB Correct.
5 Correct 7 ms 13648 KB Correct.
6 Correct 7 ms 13508 KB Correct.
7 Correct 7 ms 13648 KB Correct.
8 Correct 116 ms 33976 KB Correct.
9 Correct 124 ms 35924 KB Correct.
10 Correct 8 ms 13648 KB Correct.
11 Correct 14 ms 15364 KB Correct.
12 Correct 7 ms 13648 KB Correct.
13 Correct 171 ms 33744 KB Correct.
14 Correct 8 ms 13648 KB Correct.
15 Correct 102 ms 44168 KB Correct.
16 Correct 184 ms 36156 KB Correct.
17 Correct 203 ms 38344 KB Correct.
18 Correct 200 ms 40376 KB Correct.
19 Correct 16 ms 15184 KB Correct.
20 Correct 8 ms 13648 KB Correct.
21 Correct 298 ms 85676 KB Correct.
22 Correct 202 ms 40440 KB Correct.
23 Correct 620 ms 37752 KB Correct.
24 Correct 175 ms 49120 KB Correct.
25 Correct 200 ms 40416 KB Correct.
26 Correct 199 ms 40376 KB Correct.
27 Correct 211 ms 40428 KB Correct.
28 Correct 211 ms 40552 KB Correct.
29 Correct 183 ms 38408 KB Correct.
30 Correct 215 ms 37472 KB Correct.
31 Correct 198 ms 37464 KB Correct.
32 Correct 209 ms 37564 KB Correct.
33 Correct 336 ms 85588 KB Correct.
34 Correct 305 ms 85680 KB Correct.
35 Correct 295 ms 85680 KB Correct.
36 Correct 189 ms 37616 KB Correct.
37 Correct 164 ms 40428 KB Correct.
38 Correct 315 ms 37560 KB Correct.
39 Correct 217 ms 47536 KB Correct.
40 Correct 203 ms 40380 KB Correct.
41 Correct 203 ms 35780 KB Correct.
42 Correct 196 ms 33796 KB Correct.
43 Correct 210 ms 34488 KB Correct.
44 Correct 203 ms 40376 KB Correct.
45 Correct 207 ms 40648 KB Correct.
46 Correct 195 ms 40376 KB Correct.
47 Correct 159 ms 49076 KB Correct.
48 Correct 170 ms 49076 KB Correct.
49 Correct 137 ms 48984 KB Correct.
50 Correct 157 ms 49000 KB Correct.
51 Correct 161 ms 49124 KB Correct.
52 Correct 151 ms 48988 KB Correct.