Submission #636531

#	Time	Username	Problem	Language	Result	Execution time	Memory
636531		MohamedFaresNebili	Bridges (APIO19_bridges)	C++14	16 / 100	574 ms	6932 KiB

bridges

#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")

            using namespace std;

            const int INF = INT32_MAX;

            int N, M, Q, ST[200005];
            vector<array<int, 2>> E;
            vector<pair<int, int>> adj[50005];

            void update(int v, int l, int r, int p, int val) {
                if(l == r) {
                    ST[v] = val;
                    return;
                }
                int md = (l + r) / 2;
                if(p <= md) update(v * 2, l, (l + r) / 2, p, val);
                else update(v * 2 + 1, (l + r) / 2 + 1, r, p, val);
                ST[v] = min(ST[v * 2], ST[v * 2 + 1]);
            }
            int query(int v, int l, int r, int lo, int hi) {
                if(l > hi || r < lo) return INF;
                if(l >= lo && r <= hi) return ST[v];
                return min(query(v * 2, l, (l + r) / 2, lo, hi),
                           query(v * 2 + 1, (l + r) / 2 + 1, r, lo, hi));
            }

            int32_t main() {
                ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
                cin >> N >> M;
                for(int l = 0; l < M; l++) {
                    int U, V, D; cin >> U >> V >> D;
                    if(U > V) swap(U, V);
                    update(1, 1, N, U, D);
                    E.push_back({U, V});
                }
                cin >> Q;
                while(Q--) {
                    int t; cin >> t;
                    if(t == 1) {
                        int B, R; cin >> B >> R; --B;
                        int U = E[B][0], V = E[B][1];
                        update(1, 1, N, U, R);
                    }
                    if(t == 2) {
                        int S, W; cin >> S >> W;
                        int lo = S, hi = N, l = S, r = S;
                        while(lo <= hi) {
                            int md = (lo + hi) / 2;
                            int K = query(1, 1, N, S, md - 1);
                            if(K >= W) r = md, lo = md + 1;
                            else hi = md - 1;
                        }
                        lo = 1, hi = S;
                        while(lo <= hi) {
                            int md = (lo + hi) / 2;
                            int K = query(1, 1, N, md, S - 1);
                            if(K >= W) l = md, hi = md - 1;
                            else lo = md + 1;
                        }
                        cout << r - l + 1 << "\n";
                    }
                }
                return 0;
            }

Compilation message (stderr)

bridges.cpp: In function 'int32_t main()':
bridges.cpp:44:42: warning: unused variable 'V' [-Wunused-variable]
   44 |                         int U = E[B][0], V = E[B][1];
      |                                          ^

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