oj.uz

Submission #997352

# Submission time Handle Problem Language Result Execution time Memory
997352 2024-06-12T07:33:24 Z saddd Train (APIO24_train) C++17
40 / 100
 1000 ms 214220 KB 
#include<bits/stdc++.h>
#include<fstream>
using namespace std;
#define sz(a) (int)a.size()
#define ALL(v) v.begin(), v.end()
#define ALLR(v) v.rbegin(), v.rend()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
#define mpp make_pair
const ld PI = 3.14159265359, prec = 1e-9;;
//using u128 = __uint128_t;
//const int x[4] = {1, 0, -1, 0};
//const int y[4] = {0, -1, 0, 1};
const ll mod = 1000003, pr = 31;
const int mxn = 2e5 + 5, mxq = 1e5 + 5, sq = 500, mxv = 5e4 + 1;
//const int base = (1 <<18);
const ll inf = 1e17 + 5, neg = -69420, inf2 = 1e14;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
// have fun!
#include "train.h"

#include <vector>
struct CC{
    vt<int>comp;
    void init(bool sign ){
        sort(ALL(comp)); 
        if(sign){
            comp.resize(unique(ALL(comp)) - comp.begin());
        }
    }
    int findl(int x){
        return(lower_bound(ALL(comp), x) - comp.begin() + 1);
    }
    int findr(int x){
        return(upper_bound(ALL(comp), x) - comp.begin() + 1);
    }
    void add(int x){
        comp.pb(x);
    }
};
CC cmpl, cmpr;
struct Node{
    Node *lson, *rson;
    int sm = 0;
};
Node *root[mxn + 1];
struct E{
    ll x, y, a, b, c;
    bool operator <(const E &other){
        return(a < other.a);
    }
};

int n, m, w;
vt<E>edge;
vt<pll>food;
vt<int>comp;
deque<pii>mn[mxn + 1];
bool cmp(int a, int b){
    return(edge[a].b < edge[b].b);
}
ll t[mxn + 1], dp[mxn + 1];
void build(Node *nd, int l, int r){
    if(l == r)return;   
    int mid = (l + r) >> 1;
    nd->lson = new Node(); nd->rson = new Node();
    build(nd->lson, l, mid); build(nd->rson, mid + 1, r);
}
void upd(Node *nd, Node *pre, int l, int r, int id){
    if(l == r){
        nd->sm = pre->sm + 1;
        return;
    }
    
    int mid = (l + r) >> 1;
    if(id <= mid){
        nd->lson =  new Node(); nd->rson = pre->rson;
        upd(nd->lson, pre->lson, l, mid, id);
    }else{
        nd->lson = pre->lson;
        nd->rson = new Node(); upd(nd->rson, pre->rson, mid + 1, r, id);
    }
    nd->sm = nd->lson->sm + nd->rson->sm;
}
int get(Node *nd, Node *pre, int l, int r, int ql, int qr){
    if(ql > r || qr < l)return(0);
    if(ql <= l && qr >= r)return(nd->sm - pre->sm);
    int mid = (l + r) >> 1;
    return(max(0, get(nd->lson, pre->lson, l, mid, ql, qr) + get(nd->rson, pre->rson, mid + 1, r, ql, qr)));
}
ll getval(int ide, int rp){
   
    int lx = cmpl.findr(edge[ide].b) - 1, rx = cmpl.findr(cmpr.comp[rp - 1]) - 1;
    int ly = cmpr.findr(edge[ide].b), ry = rp;
    //cout << lx << " " << rx << " " << ly << " " << ry << "\n";
    if(lx > rx || ly > ry)return(dp[ide]); 
    ll ans = dp[ide] + get(root[rx], root[lx], 1, sz(cmpr.comp), ly, ry) * t[edge[ide].y];
    //cout << ans << " ";
    return(ans);
}

ll solve(){
    sort(ALL(edge));  sort(ALL(comp), cmp); sort(ALL(food));
    cmpr.add(0);
    for(int i = 0; i < sz(food); i++){
        cmpl.add(food[i].fi); cmpr.add(food[i].se);
    }
    cmpl.init(0); cmpr.init(1);
    root[0] = new Node();
    build(root[0], 1, sz(cmpr.comp));
    int rp = 0;
    for(int i = 1; i <= sz(food); i++){
        root[i] = new Node();
        upd(root[i], root[i - 1], 1, sz(cmpr.comp), cmpr.findl(food[i - 1].se));
    }
    rp = 0;
    ll ans = inf;
    mn[0].pb(mpp(m, 1));
    
    for(int i = 0; i < m; i++){
        while(rp < sz(comp) && edge[comp[rp]].b <= edge[i].a){
            if(dp[comp[rp]] == inf){
                rp++; continue;
            }
            auto [x, y, a, b, c] = edge[comp[rp]];
            
            while(sz(mn[y])){
                auto [ide, idr] = mn[y].back();
                if(getval(ide, idr) >= getval(comp[rp], idr)){
                    mn[y].pop_back();
                }else{
                    break;
                }
            }
            if(!sz(mn[y])){
                mn[y].pb(mpp(comp[rp], 1));
            }else{
                auto [ide, idr] = mn[y].back();
                int l = idr + 1, r = sz(cmpr.comp), ans = -1;
                while(l <= r){
                    int mid = (l + r) >> 1;
                    if(getval(comp[rp], mid) <= getval(ide, mid)){
                        ans = mid; r = mid - 1;
                    }else{
                        l = mid + 1;
                    }
                }
                if(ans != -1)mn[y].pb(mpp(comp[rp], ans));
            }
            rp++;
        }
        auto [x, y, a, b, c] = edge[i];
        int id = lower_bound(ALL(food), mpp(a, 1LL * -1)) - food.begin() - 1;
        if(sz(mn[x]) == 0)dp[i] = inf;
        else{
            int idr = cmpr.findl(a) - 1;
            while(sz(mn[x]) >= 2 && mn[x][1].se <= idr)mn[x].pop_front();
            
            dp[i] = getval(mn[x].front().fi, idr) + c;
            //cout << c << " ";
        }
        if(y == n - 1){
            int idl = cmpl.findr(edge[i].b) - 1, idr = cmpr.findr(edge[i].b);
            ll cnt = get(root[sz(cmpl.comp)], root[idl], 1, sz(cmpr.comp), idr, sz(cmpr.comp));
            ans = min(ans, dp[i] + cnt * t[n - 1]);
        }
        //cout << x << " " << y << " " << a << " " << b << " " << c << " " << dp[i] << "\n";
    }
    
    if(ans == inf)ans = -1;
    return(ans);
}
long long solve(int N, int M, int W, std::vector<int> T, std::vector<int> X, std::vector<int> Y,
                std::vector<int> A, std::vector<int> B, std::vector<int> C, std::vector<int> L,
                std::vector<int> R) {
    edge.clear(); food.clear(); comp.clear();
    n = N; m = M; w = W;
    for(int i = 0; i < n; i++)t[i] = T[i];
    for(int i = 0; i < m; i++){
        edge.pb({X[i], Y[i], A[i], B[i], C[i]}); comp.pb(i);
    }
    for(int i = 0; i < w; i++){
        food.pb(mpp(L[i], R[i]));
    }
	return(solve());
}

Compilation message

train.cpp: In function 'long long int solve()':
train.cpp:162:13: warning: unused variable 'id' [-Wunused-variable]
  162 |         int id = lower_bound(ALL(food), mpp(a, 1LL * -1)) - food.begin() - 1;
      |             ^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 138064 KB Correct.
2 Correct 69 ms 138068 KB Correct.
3 Correct 62 ms 138068 KB Correct.
4 Correct 59 ms 138068 KB Correct.
5 Correct 54 ms 137812 KB Correct.
6 Correct 50 ms 137808 KB Correct.
7 Correct 54 ms 137816 KB Correct.

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 147900 KB Correct.
2 Correct 123 ms 149200 KB Correct.
3 Correct 49 ms 137812 KB Correct.
4 Correct 60 ms 138580 KB Correct.
5 Correct 55 ms 138044 KB Correct.
6 Correct 111 ms 148592 KB Correct.
7 Correct 52 ms 137820 KB Correct.
8 Correct 109 ms 149224 KB Correct.
9 Correct 128 ms 149712 KB Correct.

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 147900 KB Correct.
2 Correct 123 ms 149200 KB Correct.
3 Correct 49 ms 137812 KB Correct.
4 Correct 60 ms 138580 KB Correct.
5 Correct 55 ms 138044 KB Correct.
6 Correct 111 ms 148592 KB Correct.
7 Correct 52 ms 137820 KB Correct.
8 Correct 109 ms 149224 KB Correct.
9 Correct 128 ms 149712 KB Correct.
10 Correct 695 ms 212936 KB Correct.
11 Correct 425 ms 214220 KB Correct.
12 Correct 61 ms 138832 KB Correct.
13 Correct 54 ms 137820 KB Correct.
14 Correct 733 ms 212936 KB Correct.
15 Correct 520 ms 213840 KB Correct.
16 Correct 739 ms 213960 KB Correct.
17 Correct 837 ms 213960 KB Correct.

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 138064 KB Correct.
2 Correct 69 ms 138068 KB Correct.
3 Correct 62 ms 138068 KB Correct.
4 Correct 59 ms 138068 KB Correct.
5 Correct 54 ms 137812 KB Correct.
6 Correct 50 ms 137808 KB Correct.
7 Correct 54 ms 137816 KB Correct.
8 Correct 121 ms 147900 KB Correct.
9 Correct 123 ms 149200 KB Correct.
10 Correct 49 ms 137812 KB Correct.
11 Correct 60 ms 138580 KB Correct.
12 Correct 55 ms 138044 KB Correct.
13 Correct 111 ms 148592 KB Correct.
14 Correct 52 ms 137820 KB Correct.
15 Correct 109 ms 149224 KB Correct.
16 Correct 128 ms 149712 KB Correct.
17 Correct 695 ms 212936 KB Correct.
18 Correct 425 ms 214220 KB Correct.
19 Correct 61 ms 138832 KB Correct.
20 Correct 54 ms 137820 KB Correct.
21 Correct 733 ms 212936 KB Correct.
22 Correct 520 ms 213840 KB Correct.
23 Correct 739 ms 213960 KB Correct.
24 Correct 837 ms 213960 KB Correct.
25 Correct 487 ms 213704 KB Correct.
26 Correct 538 ms 213704 KB Correct.
27 Correct 553 ms 213700 KB Correct.
28 Correct 560 ms 213708 KB Correct.
29 Correct 726 ms 213332 KB Correct.
30 Correct 701 ms 213708 KB Correct.
31 Correct 775 ms 213196 KB Correct.
32 Correct 665 ms 213800 KB Correct.
33 Correct 780 ms 212940 KB Correct.
34 Correct 815 ms 213056 KB Correct.
35 Execution timed out 1029 ms 213424 KB Time limit exceeded
36 Halted 0 ms 0 KB -