oj.uz

답안 #1104232

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1104232 2024-10-23T09:42:33 Z _8_8_ 은하철도 (APIO24_train) C++17
5 / 100
 1000 ms 82624 KB 
#include "train.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N = 1e5 + 12;

struct bit{
    vector<ll> t;
    int n;
    void init(int s) {
        n = s;
        t.assign(n + 1, 0);
    }
    void upd(int pos, ll val) {
        while(pos <= n) {
            t[pos] += val;
            pos += pos & -pos;    
        }
    }
    ll get(int i) {
        ll res = 0;
        while(i) {
            res += t[i];
            i -= i & -i;
        }
        return res;
    }
    ll get(int l, int r) {
        return get(r) - get(l - 1);
    }
}T;
int n, m, w;
vector<int> t, x, y, a, b, c, vt;
vector<pair<int, int>> f;
struct qwq{ 
    int pos;
    ll d;
};
deque<qwq> d[N];
ll dp[N];

void add(int v, ll dd, int pos) {
    d[v].push_back({pos, dd});
}
int col = 0;
const ll inf = 1e18, mx = (int)1e9;
int find(int pos) {
    int it = lower_bound(vt.begin(), vt.end(), pos) - vt.begin() + 1;
    return it;
}
ll cost(int L, int R) {
    assert(L <= R);
    int ret = 0;
    for(int i = 0; i < w; i++) {
        if(f[i].first > L && f[i].second < R) {
            ret++;
        }
    }
    return ret;
    // return col - T.get(find(L));
}
ll gdp(int v, int pos) {
    if(d[v].empty()) return inf;
    ll ret = inf;
    for(int i = 0; i < (int)d[v].size(); i++) {
        // cout << i << ' ' << d[v][i].d << '\n';   
        ret = min(ret, d[v][i].d + cost(d[v][i].pos, pos) * 1ll * t[v]);
    }
    return ret;
}

ll get() {
    vector<int> e, ej;
    for(int i = 0; i < m; i++) {
        e.push_back(i);
        ej.push_back(i);
    }
    sort(e.begin(), e.end(), [&](int x, int y){
        return a[x] < a[y];
    });
    sort(ej.begin(), ej.end(), [&](int x, int y){
        return b[x] < b[y];
    });
    add(0, 0, 0);
    int it = 0, ti = 0;
    for(int i:e) {
        while(it < m && b[ej[it]] <= a[i]) {
            int j = ej[it];
            add(y[j], dp[j], b[j]);
            it++;
        }
        // while(ti < w && f[ti].second < a[i]) {
        //     col++;
        //     T.upd(find(f[ti].first), 1);
        //     ti++;
        // }
        dp[i] = gdp(x[i], a[i]) + c[i];
    }
    if(dp[m - 1] == inf) dp[m - 1] = -1;
    return dp[m - 1];
}


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) {
    n = N;m = M;w = W;
    t = _T;x = X;y = Y; a = A; b = B; c = C;
    m++;
    x.push_back(n - 1);
    y.push_back(n - 1);
    a.push_back(mx);
    b.push_back(mx + 1);
    c.push_back(0);
    for(int i = 0; i < w; i++) {
        vt.push_back(L[i]);
        vt.push_back(R[i]);
        f.emplace_back(L[i], R[i]);
    }
    for(int i = 0; i < m; i++) {
        vt.push_back(a[i]);
        vt.push_back(b[i]);
    }
    sort(vt.begin(), vt.end());
    vt.resize(unique(vt.begin(), vt.end()) - vt.begin());
    T.init((int)vt.size());
    sort(f.begin(), f.end(), [&](pair<int, int> x, pair<int, int> y){
        return x.second < y.second;
    });
	return get();
}

Compilation message

train.cpp: In function 'll get()':
train.cpp:87:17: warning: unused variable 'ti' [-Wunused-variable]
   87 |     int it = 0, ti = 0;
      |                 ^~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 68432 KB Correct.
2 Correct 41 ms 68424 KB Correct.
3 Correct 42 ms 68440 KB Correct.
4 Correct 42 ms 68428 KB Correct.
5 Correct 42 ms 68320 KB Correct.
6 Correct 45 ms 68176 KB Correct.
7 Correct 43 ms 68280 KB Correct.

Subtask #2
0.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 105 ms 77980 KB Correct.
2 Correct 112 ms 79012 KB Correct.
3 Correct 46 ms 68168 KB Correct.
4 Correct 53 ms 69960 KB Correct.
5 Correct 47 ms 68176 KB Correct.
6 Correct 132 ms 82624 KB Correct.
7 Correct 54 ms 68168 KB Correct.
8 Execution timed out 1054 ms 82456 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #3
0.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 105 ms 77980 KB Correct.
2 Correct 112 ms 79012 KB Correct.
3 Correct 46 ms 68168 KB Correct.
4 Correct 53 ms 69960 KB Correct.
5 Correct 47 ms 68176 KB Correct.
6 Correct 132 ms 82624 KB Correct.
7 Correct 54 ms 68168 KB Correct.
8 Execution timed out 1054 ms 82456 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 68432 KB Correct.
2 Correct 41 ms 68424 KB Correct.
3 Correct 42 ms 68440 KB Correct.
4 Correct 42 ms 68428 KB Correct.
5 Correct 42 ms 68320 KB Correct.
6 Correct 45 ms 68176 KB Correct.
7 Correct 43 ms 68280 KB Correct.
8 Correct 105 ms 77980 KB Correct.
9 Correct 112 ms 79012 KB Correct.
10 Correct 46 ms 68168 KB Correct.
11 Correct 53 ms 69960 KB Correct.
12 Correct 47 ms 68176 KB Correct.
13 Correct 132 ms 82624 KB Correct.
14 Correct 54 ms 68168 KB Correct.
15 Execution timed out 1054 ms 82456 KB Time limit exceeded
16 Halted 0 ms 0 KB -