oj.uz

답안 #1062024

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1062024 2024-08-16T17:16:04 Z steveonalex 은하철도 (APIO24_train) C++17
10 / 100
 1000 ms 822092 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;

struct FenwickTree{
    int n;
    vector<int> a;

    FenwickTree(int _n){
        n = _n;
        a.resize(n+1);
    }

    void update(int i, int v){
        i = n - i + 1;
        while(i <= n){
            a[i] += v;
            i += LASTBIT(i);
        }
    }

    int get(int i){
        i = n - i + 1;
        int ans = 0;
        while(i > 0){
            ans += a[i];
            i -= LASTBIT(i);
        }
        return ans;
    }
};

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

    SegmentTree(int _n, int _t){
        n = _n, t = _t;
        for(int i = 0; i < MASK(19); ++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);
    }
}; 

const int N = 1e5 + 65;
const int BLOCK = 500;
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:203: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]
  203 |     for(int i = 0; i < relevant_pair.size(); ++i){
      |                    ~~^~~~~~~~~~~~~~~~~~~~~~
train.cpp:208:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  208 |             for(int j = 0; j < big_boys.size(); ++j){
      |                            ~~^~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 13660 KB Correct.
2 Correct 5 ms 13660 KB Correct.
3 Correct 5 ms 13660 KB Correct.
4 Correct 5 ms 13660 KB Correct.
5 Correct 4 ms 13404 KB Correct.
6 Correct 4 ms 13400 KB Correct.
7 Correct 4 ms 13404 KB Correct.

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 131 ms 30756 KB Correct.
2 Correct 125 ms 32088 KB Correct.
3 Correct 5 ms 13404 KB Correct.
4 Correct 11 ms 15264 KB Correct.
5 Correct 5 ms 13560 KB Correct.
6 Correct 360 ms 31784 KB Correct.
7 Correct 4 ms 13400 KB Correct.
8 Correct 80 ms 42180 KB Correct.
9 Correct 140 ms 33384 KB Correct.

Subtask #3
0.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 131 ms 30756 KB Correct.
2 Correct 125 ms 32088 KB Correct.
3 Correct 5 ms 13404 KB Correct.
4 Correct 11 ms 15264 KB Correct.
5 Correct 5 ms 13560 KB Correct.
6 Correct 360 ms 31784 KB Correct.
7 Correct 4 ms 13400 KB Correct.
8 Correct 80 ms 42180 KB Correct.
9 Correct 140 ms 33384 KB Correct.
10 Correct 185 ms 34908 KB Correct.
11 Correct 146 ms 35008 KB Correct.
12 Correct 13 ms 15192 KB Correct.
13 Correct 5 ms 13404 KB Correct.
14 Correct 255 ms 80196 KB Correct.
15 Correct 188 ms 35008 KB Correct.
16 Execution timed out 1088 ms 822092 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 13660 KB Correct.
2 Correct 5 ms 13660 KB Correct.
3 Correct 5 ms 13660 KB Correct.
4 Correct 5 ms 13660 KB Correct.
5 Correct 4 ms 13404 KB Correct.
6 Correct 4 ms 13400 KB Correct.
7 Correct 4 ms 13404 KB Correct.
8 Correct 131 ms 30756 KB Correct.
9 Correct 125 ms 32088 KB Correct.
10 Correct 5 ms 13404 KB Correct.
11 Correct 11 ms 15264 KB Correct.
12 Correct 5 ms 13560 KB Correct.
13 Correct 360 ms 31784 KB Correct.
14 Correct 4 ms 13400 KB Correct.
15 Correct 80 ms 42180 KB Correct.
16 Correct 140 ms 33384 KB Correct.
17 Correct 185 ms 34908 KB Correct.
18 Correct 146 ms 35008 KB Correct.
19 Correct 13 ms 15192 KB Correct.
20 Correct 5 ms 13404 KB Correct.
21 Correct 255 ms 80196 KB Correct.
22 Correct 188 ms 35008 KB Correct.
23 Execution timed out 1088 ms 822092 KB Time limit exceeded
24 Halted 0 ms 0 KB -