Submission #433745

#	Time	Username	Problem	Language	Result	Execution time	Memory
433745		someone	Bridges (APIO19_bridges)	C++14	16 / 100	1164 ms	25244 KiB

bridges

#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
• Subtask 2: 16 / 16
• Subtask 3: 0 / 17
• Subtask 4: 0 / 14
• Subtask 5: 0 / 13
• Subtask 6: 0 / 27