Submission #433893

#	Time	Username	Problem	Language	Result	Execution time	Memory
433893		Mounir	Bridges (APIO19_bridges)	C++14	0 / 100	428 ms	5336 KiB

bridges

    #include <bits/stdc++.h>
    #define chmax(x, v) x = max(x, v)
    #define pii pair<int, int>
    #define pb push_back
    #define all(x) x.begin(), x.end()
    #define chmin(x, v) x = min(x, v)
    #define sz(x) (int)x.size()
    #define int long long
    using namespace std;
     
    const int N = (1 << 18), OO = 1e10;
    int maxi[N * 2];
     
    int getMax(int gauche, int droite){
        if (droite < gauche)
            return 0;
        if (gauche%2 == 1)
            return max(maxi[gauche], getMax(gauche + 1, droite));
        if (droite%2 == 0)
            return max(maxi[droite], getMax(gauche, droite - 1));
        return getMax(gauche/2, droite/2);
    }
     
    vector<int> getDecomposition(int gauche, int droite){
        vector<int> g, d;
        while (droite >= gauche){
            if (droite%2 == 0)
                d.pb(droite--);
            if (gauche%2 == 1)
                g.pb(gauche++);
            gauche /= 2;
            droite /= 2;
        }

        vector<int> res;
        for (int e : g)
            res.pb(e);
        reverse(all(d));
        for (int e : d)
            res.pb(e);
        return res;
    }
     
    int plusLoin(int noeud, int borne){
        if (noeud >= N)
            return noeud - N;
        if (maxi[noeud * 2 + 1] > borne)
            return plusLoin(noeud * 2 + 1, borne);
        return plusLoin(noeud * 2, borne);
    }
     
    int plusPres(int noeud, int borne){
        if (noeud >= N)
            return noeud - N;
        if (maxi[noeud * 2] > borne)
            return plusPres(noeud * 2, borne);
        return plusPres(noeud * 2 + 1, borne);
    }
     
    void upd(int noeud, int val){
        maxi[N + noeud] = val;
        for (int n = (N + noeud)/2; n > 0; n /= 2)
            maxi[n] = max(maxi[n * 2], maxi[n * 2 + 1]);
    }
     
    int noeudArete[N];
     
    signed main(){
        for (int noeud = 1; noeud < 2 * N; ++noeud)
            maxi[noeud] = OO;
     
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        cout.tie(nullptr);
     
        int nNoeuds, nAretes; cin >> nNoeuds >> nAretes;
        for (int iArete = 0; iArete < nAretes; ++iArete){
            int noeud, voisin, poids; cin >> noeud >> voisin >> poids;
            noeudArete[iArete] = noeud - 1;
            upd(noeud - 1, poids);
        }
     
        int nReqs; cin >> nReqs;
        for (int iReq = 0; iReq < nReqs; ++iReq){
            int typeReq; cin >> typeReq;
            if (typeReq == 1){
                int iArete, poids; cin >> iArete >> poids;
                --iArete;
     
                upd(iArete, poids);
            }
            else {
                int depart, poids; cin >> depart >> poids;
                --depart;
     
                vector<int> coteGauche = getDecomposition(N, N + depart - 1), coteDroit = getDecomposition(N + depart, N + nNoeuds - 2);
                reverse(all(coteGauche));
                int exGauche = -1, exDroite = nNoeuds - 1;
                for (int e : coteGauche){
                    if (maxi[e] > poids){
                        //cout << "g " << e << endl;
                        exGauche = plusLoin(e, poids);
                        break;
                    }
                }
                for (int e : coteDroit){
                    if (maxi[e] > poids){
                        //cout << "d " << e << endl;
                        exDroite = plusPres(e, poids);
                        break;
                    }
                }
     
                cout << exDroite - exGauche << endl;
            }
        }
        return 0;
    }

• Subtask 1: 0 / 13
• Subtask 2: 0 / 16
• Subtask 3: 0 / 17
• Subtask 4: 0 / 14
• Subtask 5: 0 / 13
• Subtask 6: 0 / 27