Submission #1143460

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143460		byunjaewoo	Train (APIO24_train)	C++20	100 / 100	731 ms	222336 KiB

train

#include "train.h"
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
using ll=long long;

const int N=200010, S=1<<18;
const ll INF=1e18;
int n, m, k;
vector<int> t, x, y, a, b, c, l, r;
vector<pair<int, int>> vec;
deque<pair<int, ll>> val[N];
set<pair<int, ll>> cand[N];
vector<array<int, 5>> vec2;
vector<int> com;

class PST {
public:
    PST() {root.push_back(new Node());}
    void update(int v) {root.push_back(update(root.back(), 1, S, v));}
    ll query(int p, int k) {return query(root.back(), 1, S, 1, k)-(p?query(root[p-1], 1, S, 1, k):0);}
    int query2(int p, int q, ll v) {
        int ret=S;
        for(int s=1, e=S; s<=e; ) {
            int m=(s+e)/2;
            if(query(p, m)-query(q, m)>=v) ret=m, e=m-1;
            else s=m+1;
        }
        return ret;
        //return query2((p<root.size())?root[p]:NULL, (q<root.size())?root[q]:NULL, 1, S, v);
    }
private:
    struct Node { int v; Node *l, *r; };
    vector<Node*> root;
    Node* update(Node *prev, int s, int e, int k) {
        Node *node=new Node();
        if(prev) node->v=prev->v, node->l=prev->l, node->r=prev->r;
        node->v++;
        if(s==e) return node;
        int m=(s+e)/2;
        if(k<=m) {
            if(prev) node->l=update(prev->l, s, m, k);
            else node->l=update(NULL, s, m, k);
        }
        else {
            if(prev) node->r=update(prev->r, m+1, e, k);
            else node->r=update(NULL, m+1, e, k);
        }
        return node;
    }
    int query(Node *node, int s, int e, int l, int r) {
        if(s>r || l>e || !node) return 0;
        if(l<=s && e<=r) return node->v;
        int m=(s+e)/2;
        return query(node->l, s, m, l, r)+query(node->r, m+1, e, l, r);
    }
    int query2(Node *node1, Node *node2, int s, int e, ll v) {
        if(s==e) return s;
        int m=(s+e)/2;
        if(((node2&&node2->l)?node2->l->v:0)-((node1&&node1->l)?node1->l->v:0)>=v)
            return query2(node1?node1->l:NULL, node2?node2->l:NULL, s, m, v);
        return query2(node1?node1->r:NULL, node2?node2->r:NULL, m+1, e, v);
    }
}P;

void update(int i, pair<int, ll> v) {
    while(val[i].size()>=2) {
        pair<int, ll> tmp=val[i].back();
        int k1=P.query2(lower_bound(all(vec), make_pair(tmp.first+1, 0))-vec.begin()+1, lower_bound(all(vec), make_pair(v.first+1, 0))-vec.begin()+1, (v.second-tmp.second+t[i]-1)/t[i]);
        val[i].pop_back();
        pair<int, ll> tmp2=val[i].back();
        int k2=P.query2(lower_bound(all(vec), make_pair(tmp2.first+1, 0))-vec.begin()+1, lower_bound(all(vec), make_pair(tmp.first+1, 0))-vec.begin()+1, (tmp.second-tmp2.second+t[i]-1)/t[i]);
        if(k1>=k2) {
            val[i].push_back(tmp); break;
        }
    }
    val[i].push_back(v);
}

ll query(int i, int x) {
    int x_=x;
    x=lower_bound(all(com), x)-com.begin();
    while(val[i].size()>=2) {
        ll v1=val[i].front().second+(ll)t[i]*P.query(lower_bound(all(vec), make_pair(val[i].front().first+1, 0))-vec.begin()+1, x);
        pair<int, ll> tmp=val[i].front(); val[i].pop_front();
        ll v2=val[i].front().second+(ll)t[i]*P.query(lower_bound(all(vec), make_pair(val[i].front().first+1, 0))-vec.begin()+1, x);
        if(v1<v2) {
            val[i].push_front(tmp); break;
        }
    }
    if(val[i].empty()) return INF;
    return val[i].front().second+(ll)t[i]*P.query(lower_bound(all(vec), make_pair(val[i].front().first+1, 0))-vec.begin()+1, x);
}

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, k=W;
    t=T, x=X, y=Y, a=A, b=B, c=C, l=L, r=R;
    if(!k) ++k, l.push_back(1e9+1), r.push_back(1e9+1);

    for(int i=0; i<k; i++) com.push_back(l[i]), com.push_back(r[i]), vec.emplace_back(l[i], r[i]);
    sort(com.begin(), com.end());
    sort(vec.begin(), vec.end());
    for(int i=0; i<vec.size(); i++) P.update(lower_bound(all(com), vec[i].second)-com.begin()+1);
    
    val[0].push_back({0, 0});
    for(int i=0; i<m; i++) vec2.push_back({a[i], b[i], c[i], x[i], y[i]});
    sort(vec2.begin(), vec2.end());
    for(int i=0; i<vec2.size(); i++) {
        while(!cand[vec2[i][3]].empty() && (*cand[vec2[i][3]].begin()).first<=vec2[i][0]) {
            update(vec2[i][3], *cand[vec2[i][3]].begin());
            cand[vec2[i][3]].erase(cand[vec2[i][3]].begin());
        }
        cand[vec2[i][4]].insert({vec2[i][1], query(vec2[i][3], vec2[i][0])+vec2[i][2]});
    }

    for(auto t:cand[n-1]) update(n-1, t);
    ll ans=query(n-1, com.back()+1);
    if(l.back()==1e9+1) ans-=t[n-1];
    if(ans>=INF/2) ans=-1;
    return ans;
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 30 / 30
• Subtask 4: 60 / 60