oj.uz

Submission #433745

# Submission time Handle Problem Language Result Execution time Memory
433745 2021-06-20T10:15:33 Z someone Bridges (APIO19_bridges) C++14
16 / 100
 1164 ms 25244 KB 
#include <iostream>
#include <vector>
//#include <bits/stdc++.h>
using namespace std;

struct Req {
    bool isQ;
    int id, w;
};

struct Arc {
    int sum, w;
};

struct Node {
    int deb, fin, mini;
};

const int M = 1 << 18, N = 2*M, INF = 1e9 + 42;

Node node[N];
vector<Req> req;
vector<Arc> arc;
vector<int> adj[N];
int n, m, q;

void setMin(int i, int newMin) {
    if(i == 0)
        return;
    if(i >= M) {
        node[i].mini = newMin;
    } else {
        node[i].mini = min(node[i*2].mini, node[i*2+1].mini);
    }
    setMin(i/2, newMin);
}

int getMin(int i, int deb, int fin) {
    if(fin <= node[i].deb || node[i].fin <= deb)
        return INF;
    if(deb <= node[i].deb && node[i].fin <= fin) {
        return node[i].mini;
    }
    return min(getMin(i*2, deb, fin), getMin(i*2+1, deb, fin));
}

bool way(int deb, int fin, int w) {
    return getMin(1, deb, fin) >= w;
}

int possibleL(int deb, int fin, int w, int obj) {
    if(deb + 1 == fin)
        return deb;
    if(deb + 2 == fin) {
        if(way(deb, obj, w))
            return deb;
        return deb+1;
    }
    int med = (deb + fin) / 2;
    if(way(med-1, obj, w))
        return possibleL(deb, med, w, obj);
    return possibleL(med, fin, w, obj);
}

int possibleR(int deb, int fin, int w, int obj) {
    if(deb + 1 == fin)
        return deb;
    if(deb + 2 == fin) {
        if(way(obj, deb+1, w))
            return deb+1;
        return deb;
    }

    int med = (deb + fin) / 2;
    if(way(obj, med, w))
        return possibleR(med, fin, w, obj);
    return possibleR(deb, med, w, obj);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    for(int i = 0; i < m; i++) {
        int e1, e2, w;
        cin >> e1 >> e2 >> w;
        e1--, e2--;
        adj[e1].push_back(i);
        adj[e2].push_back(i);
        arc.push_back({e1 + e2, w});
    }
    cin >> q;
    for(int i = 0; i < q; i++) {
        int type, id, w;
        cin >> type >> id >> w;
        id--;
        if(type == 2)
            req.push_back({true, id, w});
        else
            req.push_back({false, id, w});
    }

    for(int i = M; i < N; i++) {
        node[i].deb = i - M;
        node[i].fin = i - M + 1;
        if(i >= n + M) {
            node[i].mini = INF;
        } else {
            if(i - M < m)
                node[i].mini = arc[i - M].w;
            else
                node[i].mini = INF;
        }
    }
    for(int i = M-1; i > 0; i--) {
        node[i].deb = node[i*2].deb;
        node[i].fin = node[i*2+1].fin;
        node[i].mini = min(node[i*2].mini, node[i*2+1].mini);
    }

    for(int i = 0; i < q; i++) {
        if(req[i].isQ) {
            int left = possibleL(0, req[i].id+1, req[i].w, req[i].id),
                right = possibleR(req[i].id, n, req[i].w, req[i].id);
            cout << right - left + 1 << '\n';
        } else {
            setMin(req[i].id + M, req[i].w);
        }
    }
    return 0;
}

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 18764 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 570 ms 22312 KB Output is correct
2 Correct 577 ms 22376 KB Output is correct
3 Correct 604 ms 22364 KB Output is correct
4 Correct 577 ms 22412 KB Output is correct
5 Correct 585 ms 22572 KB Output is correct
6 Correct 678 ms 22672 KB Output is correct
7 Correct 638 ms 22524 KB Output is correct
8 Correct 636 ms 22492 KB Output is correct
9 Correct 47 ms 20168 KB Output is correct
10 Correct 594 ms 24048 KB Output is correct
11 Correct 594 ms 24036 KB Output is correct
12 Correct 1061 ms 25244 KB Output is correct
13 Correct 187 ms 24968 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 539 ms 21440 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1164 ms 23936 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 570 ms 22312 KB Output is correct
2 Correct 577 ms 22376 KB Output is correct
3 Correct 604 ms 22364 KB Output is correct
4 Correct 577 ms 22412 KB Output is correct
5 Correct 585 ms 22572 KB Output is correct
6 Correct 678 ms 22672 KB Output is correct
7 Correct 638 ms 22524 KB Output is correct
8 Correct 636 ms 22492 KB Output is correct
9 Correct 47 ms 20168 KB Output is correct
10 Correct 594 ms 24048 KB Output is correct
11 Correct 594 ms 24036 KB Output is correct
12 Correct 1061 ms 25244 KB Output is correct
13 Correct 187 ms 24968 KB Output is correct
14 Incorrect 539 ms 21440 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 18764 KB Output isn't correct
2 Halted 0 ms 0 KB -