Submission #697058

#	Time	Username	Problem	Language	Result	Execution time	Memory
697058		Cross_Ratio	Treatment Project (JOI20_treatment)	C++14	100 / 100	517 ms	152144 KiB

treatment

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
ll T[100005];
ll L[100005];
ll R[100005];
ll C[100005];
vector<array<ll, 2>> adj[800005];
ll dis[200005];
bool vis[200005];
typedef pair<ll, ll> P;
struct SegTree {
    struct Node {
        vector<array<ll, 2>> S1, S2;
        int p1, p2;
        Node() : p1(0), p2(0) {}
    };
    vector<Node> seg;
    int MAX;
    SegTree(int N) {
        int i;
        for(i=1;i<2*N;i*=2) {}
        seg.resize(i);
        MAX = i;
    }
    void Edit(int n, int a) {
        n += MAX/2;
        seg[n].S1.push_back({L[a] + T[a], 2*a});
        seg[n].S2.push_back({L[a] - T[a], 2*a});
    }
    void cons() {
        for(int i=MAX/2;i<MAX;i++) {
            sort(seg[i].S1.begin(), seg[i].S1.end());
            sort(seg[i].S2.begin(), seg[i].S2.end());
        }
        for(int i = MAX/2-1;i>=1;i--) {
            seg[i].S1.resize(seg[2*i].S1.size() + seg[2*i+1].S1.size());
            merge(seg[2*i].S1.begin(),seg[2*i].S1.end(),seg[2*i+1].S1.begin(),seg[2*i+1].S1.end(),seg[i].S1.begin());
            seg[i].S2.resize(seg[2*i].S2.size() + seg[2*i+1].S2.size());
            merge(seg[2*i].S2.begin(),seg[2*i].S2.end(),seg[2*i+1].S2.begin(),seg[2*i+1].S2.end(),seg[i].S2.begin());
        }
    }
    void make_edge(int s, int e, int k, int n, int ns, int ne, bool type) {
        if(e<=ns||ne<=s) return;
        if(s<=ns&&ne<=e) {
            if(type) {
                while(seg[n].p2 < seg[n].S2.size()) {
                    auto m = seg[n].S2[seg[n].p2];
                    if(m[0]>R[k]-T[k]+1) break;
                    adj[2*k+1].push_back({m[1], 0});
                    seg[n].p2++;
                }
            }
            else {
                while(seg[n].p1 < seg[n].S1.size()) {
                    auto m = seg[n].S1[seg[n].p1];
                    if(m[0]>R[k]+T[k]+1) break;
                    adj[2*k+1].push_back({m[1], 0});
                    seg[n].p1++;
                }
            }
            return;
        }
        int mid = ns + ne >> 1;
        make_edge(s, e, k, 2*n, ns, mid, type);
        make_edge(s, e, k, 2*n+1, mid, ne, type);
    }
};
vector<ll> idt;
int it(int n) {
    return lower_bound(idt.begin(),idt.end(),n) - idt.begin();
}
signed main() {
    cin.sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int N, M;
    cin >> N >> M;
    int i, j;
    for(i=1;i<=M;i++) {
        cin >> T[i] >> L[i] >> R[i] >> C[i];
        idt.push_back(T[i]);
    }
    sort(idt.begin(),idt.end());
    idt.erase(unique(idt.begin(),idt.end()),idt.end());

    //0 is left, 1 is right
    //2i is input, 2i+1 is output

    for(i=1;i<=M;i++) {
        adj[2*i].push_back({2*i+1, C[i]});
        if(L[i]==1) adj[0].push_back({2*i, 0});
        if(R[i]==N) adj[2*i+1].push_back({1, 0});
    }
    /*for(i=1;i<=M;i++) {
        for(j=1;j<=M;j++) {
            if(i==j) continue;
            if(T[i] >= T[j]) {
                int t = T[i] - T[j];
                if(R[j] == N || L[i] <= R[j] - t + 1) {
                    adj[2*j+1].push_back({2*i, 0});
                }
            }
            if(T[i] <= T[j]) {
                int t = T[j] - T[i];
                if(L[i] == 1 || L[i] - 1 + t <= R[j]) {
                    adj[2*j+1].push_back({2*i, 0});
                }
            }
        }
    }*/
    /*for(i=0;i<=2*M+1;i++) {
        cout << i << " : ";
        for(auto n2 : adj[i]) {
            cout << "(" << n2[0] << ", " << n2[1] << ") ";
        }
        cout << '\n';
    }*/
    SegTree tree(idt.size() + 3);
    int MAX = tree.MAX;
    for(i=1;i<=M;i++) {
        tree.Edit(it(T[i]), i);
    }
    tree.cons();
    for(i=0;i<=2*M+1;i++) dis[i] = INF;
    dis[0] = 0;
    priority_queue<P, vector<P>, greater<P>> PQ;
    PQ.push(P(0, 0));
    while(!PQ.empty()) {
        auto k = PQ.top();
        PQ.pop();
        int id = k.second;
        if(vis[id]) continue;
        vis[id] = true;
        if(id != 0 && id != 1 && id % 2 == 1) {
            int x = id / 2;
            tree.make_edge(0, it(T[x])+1, x, 1, 0, MAX/2, true);
            tree.make_edge(it(T[x]), idt.size(), x, 1, 0, MAX/2, false);
        }
        for(auto n : adj[id]) {
            if(dis[n[0]] > dis[id] + n[1]) {
                dis[n[0]] = dis[id] + n[1];
                PQ.push(P(dis[n[0]], n[0]));
            }
        }
    }
    cout << (dis[1]==INF?-1:dis[1]);
}

Compilation message (stderr)

treatment.cpp: In member function 'void SegTree::make_edge(int, int, int, int, int, int, bool)':
treatment.cpp:48:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |                 while(seg[n].p2 < seg[n].S2.size()) {
treatment.cpp:56:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |                 while(seg[n].p1 < seg[n].S1.size()) {
treatment.cpp:65:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |         int mid = ns + ne >> 1;
      |                   ~~~^~~~
treatment.cpp: In function 'int main()':
treatment.cpp:80:12: warning: unused variable 'j' [-Wunused-variable]
   80 |     int i, j;
      |            ^

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