oj.uz

Submission #697056

# Submission time Handle Problem Language Result Execution time Memory
697056 2023-02-08T04:49:26 Z Cross_Ratio Treatment Project (JOI20_treatment) C++14
39 / 100
 3000 ms 315876 KB 
#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 {
        set<array<ll, 2>> S1, S2;
    };
    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.insert({L[a] + T[a], 2*a});
        seg[n].S2.insert({L[a] - T[a], 2*a});
        n /= 2;
        while(n) {
            seg[n].S1.insert({L[a] + T[a], 2*a});
            seg[n].S2.insert({L[a] - T[a], 2*a});
            n /= 2;
        }
    }
    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].S2.empty()) {
                    auto m = *seg[n].S2.begin();
                    if(m[0] > R[k] - T[k] + 1) break;
                    adj[2*k+1].push_back({m[1], 0});
                    seg[n].S2.erase(m);
                }
            }
            else {
                while(!seg[n].S1.empty()) {
                    auto m = *seg[n].S1.begin();
                    if(m[0] > R[k] + T[k] + 1) break;
                    adj[2*k+1].push_back({m[1], 0});
                    seg[n].S1.erase(m);
                }
            }
            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);
    }
    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

treatment.cpp: In member function 'void SegTree::make_edge(int, int, int, int, int, int, bool)':
treatment.cpp:57:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   57 |         int mid = ns + ne >> 1;
      |                   ~~~^~~~
treatment.cpp: In function 'int main()':
treatment.cpp:72:12: warning: unused variable 'j' [-Wunused-variable]
   72 |     int i, j;
      |            ^

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 356 ms 65488 KB Output is correct
2 Correct 316 ms 65488 KB Output is correct
3 Correct 388 ms 70280 KB Output is correct
4 Correct 396 ms 69644 KB Output is correct
5 Correct 307 ms 70312 KB Output is correct
6 Correct 264 ms 69520 KB Output is correct
7 Correct 248 ms 70600 KB Output is correct
8 Correct 267 ms 65576 KB Output is correct
9 Correct 201 ms 65476 KB Output is correct
10 Correct 183 ms 65224 KB Output is correct
11 Correct 401 ms 73596 KB Output is correct
12 Correct 419 ms 72160 KB Output is correct
13 Correct 408 ms 71112 KB Output is correct
14 Correct 394 ms 71220 KB Output is correct
15 Correct 370 ms 69956 KB Output is correct
16 Correct 384 ms 70068 KB Output is correct
17 Correct 366 ms 69948 KB Output is correct
18 Correct 390 ms 73660 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19028 KB Output is correct
2 Correct 9 ms 19124 KB Output is correct
3 Correct 9 ms 19028 KB Output is correct
4 Correct 10 ms 19156 KB Output is correct
5 Correct 10 ms 19156 KB Output is correct
6 Correct 10 ms 19156 KB Output is correct
7 Correct 10 ms 19156 KB Output is correct
8 Correct 12 ms 19156 KB Output is correct
9 Correct 10 ms 19156 KB Output is correct
10 Correct 9 ms 19156 KB Output is correct
11 Correct 9 ms 19208 KB Output is correct
12 Correct 9 ms 19156 KB Output is correct
13 Correct 10 ms 19156 KB Output is correct
14 Correct 9 ms 19156 KB Output is correct
15 Correct 9 ms 19156 KB Output is correct
16 Correct 9 ms 19156 KB Output is correct
17 Correct 10 ms 19028 KB Output is correct
18 Correct 10 ms 19156 KB Output is correct
19 Correct 11 ms 19160 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19028 KB Output is correct
2 Correct 9 ms 19124 KB Output is correct
3 Correct 9 ms 19028 KB Output is correct
4 Correct 10 ms 19156 KB Output is correct
5 Correct 10 ms 19156 KB Output is correct
6 Correct 10 ms 19156 KB Output is correct
7 Correct 10 ms 19156 KB Output is correct
8 Correct 12 ms 19156 KB Output is correct
9 Correct 10 ms 19156 KB Output is correct
10 Correct 9 ms 19156 KB Output is correct
11 Correct 9 ms 19208 KB Output is correct
12 Correct 9 ms 19156 KB Output is correct
13 Correct 10 ms 19156 KB Output is correct
14 Correct 9 ms 19156 KB Output is correct
15 Correct 9 ms 19156 KB Output is correct
16 Correct 9 ms 19156 KB Output is correct
17 Correct 10 ms 19028 KB Output is correct
18 Correct 10 ms 19156 KB Output is correct
19 Correct 11 ms 19160 KB Output is correct
20 Correct 53 ms 29920 KB Output is correct
21 Correct 54 ms 30040 KB Output is correct
22 Correct 45 ms 26460 KB Output is correct
23 Correct 43 ms 26196 KB Output is correct
24 Correct 58 ms 31052 KB Output is correct
25 Correct 56 ms 30964 KB Output is correct
26 Correct 51 ms 31048 KB Output is correct
27 Correct 51 ms 31016 KB Output is correct
28 Correct 59 ms 31056 KB Output is correct
29 Correct 61 ms 30840 KB Output is correct
30 Correct 39 ms 29852 KB Output is correct
31 Correct 44 ms 29836 KB Output is correct
32 Correct 70 ms 31180 KB Output is correct
33 Correct 61 ms 31180 KB Output is correct
34 Correct 58 ms 29544 KB Output is correct
35 Correct 60 ms 31148 KB Output is correct
36 Correct 59 ms 31232 KB Output is correct
37 Correct 64 ms 29524 KB Output is correct

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 356 ms 65488 KB Output is correct
2 Correct 316 ms 65488 KB Output is correct
3 Correct 388 ms 70280 KB Output is correct
4 Correct 396 ms 69644 KB Output is correct
5 Correct 307 ms 70312 KB Output is correct
6 Correct 264 ms 69520 KB Output is correct
7 Correct 248 ms 70600 KB Output is correct
8 Correct 267 ms 65576 KB Output is correct
9 Correct 201 ms 65476 KB Output is correct
10 Correct 183 ms 65224 KB Output is correct
11 Correct 401 ms 73596 KB Output is correct
12 Correct 419 ms 72160 KB Output is correct
13 Correct 408 ms 71112 KB Output is correct
14 Correct 394 ms 71220 KB Output is correct
15 Correct 370 ms 69956 KB Output is correct
16 Correct 384 ms 70068 KB Output is correct
17 Correct 366 ms 69948 KB Output is correct
18 Correct 390 ms 73660 KB Output is correct
19 Correct 9 ms 19028 KB Output is correct
20 Correct 9 ms 19124 KB Output is correct
21 Correct 9 ms 19028 KB Output is correct
22 Correct 10 ms 19156 KB Output is correct
23 Correct 10 ms 19156 KB Output is correct
24 Correct 10 ms 19156 KB Output is correct
25 Correct 10 ms 19156 KB Output is correct
26 Correct 12 ms 19156 KB Output is correct
27 Correct 10 ms 19156 KB Output is correct
28 Correct 9 ms 19156 KB Output is correct
29 Correct 9 ms 19208 KB Output is correct
30 Correct 9 ms 19156 KB Output is correct
31 Correct 10 ms 19156 KB Output is correct
32 Correct 9 ms 19156 KB Output is correct
33 Correct 9 ms 19156 KB Output is correct
34 Correct 9 ms 19156 KB Output is correct
35 Correct 10 ms 19028 KB Output is correct
36 Correct 10 ms 19156 KB Output is correct
37 Correct 11 ms 19160 KB Output is correct
38 Correct 53 ms 29920 KB Output is correct
39 Correct 54 ms 30040 KB Output is correct
40 Correct 45 ms 26460 KB Output is correct
41 Correct 43 ms 26196 KB Output is correct
42 Correct 58 ms 31052 KB Output is correct
43 Correct 56 ms 30964 KB Output is correct
44 Correct 51 ms 31048 KB Output is correct
45 Correct 51 ms 31016 KB Output is correct
46 Correct 59 ms 31056 KB Output is correct
47 Correct 61 ms 30840 KB Output is correct
48 Correct 39 ms 29852 KB Output is correct
49 Correct 44 ms 29836 KB Output is correct
50 Correct 70 ms 31180 KB Output is correct
51 Correct 61 ms 31180 KB Output is correct
52 Correct 58 ms 29544 KB Output is correct
53 Correct 60 ms 31148 KB Output is correct
54 Correct 59 ms 31232 KB Output is correct
55 Correct 64 ms 29524 KB Output is correct
56 Correct 2297 ms 292216 KB Output is correct
57 Correct 2344 ms 291232 KB Output is correct
58 Correct 2011 ms 285208 KB Output is correct
59 Correct 2008 ms 286152 KB Output is correct
60 Correct 2123 ms 226600 KB Output is correct
61 Correct 1992 ms 285028 KB Output is correct
62 Correct 2291 ms 292116 KB Output is correct
63 Correct 1492 ms 280288 KB Output is correct
64 Correct 1459 ms 280392 KB Output is correct
65 Correct 491 ms 78028 KB Output is correct
66 Correct 2099 ms 222580 KB Output is correct
67 Correct 2216 ms 310344 KB Output is correct
68 Correct 1849 ms 311808 KB Output is correct
69 Correct 1638 ms 310276 KB Output is correct
70 Correct 2534 ms 310892 KB Output is correct
71 Correct 1939 ms 312468 KB Output is correct
72 Correct 1617 ms 310716 KB Output is correct
73 Correct 2437 ms 310968 KB Output is correct
74 Correct 1177 ms 277884 KB Output is correct
75 Correct 934 ms 277820 KB Output is correct
76 Correct 2429 ms 285544 KB Output is correct
77 Correct 2976 ms 311920 KB Output is correct
78 Correct 2475 ms 287964 KB Output is correct
79 Execution timed out 3073 ms 315876 KB Time limit exceeded
80 Halted 0 ms 0 KB -