HackerEarth Segments maybe Super segments problem solution YASH PAL, 31 July 2024 In this HackerEarth Segments maybe Super segments problem solution You have an array a of integers between 0 and 10^6. Initially, you do not know exactly the value of any element of the array, but you know that the length of the array is n. Also, you are given m segments of the array l r x, where l is the left bound of the segment, r is the right bound of the segment, x is the sum of the segment. Then You are given q queries ql qr. For every query, you need to print the sum of elements of the array a on [ql,qr] interval, if it is impossible to print -1. HackerEarth Segments maybe Super segments problem solution. # include <bits/stdc++.h># include <ext/pb_ds/assoc_container.hpp># include <ext/pb_ds/tree_policy.hpp>using namespace __gnu_pbds;using namespace std; template<typename T> using ordered_set = tree <T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;#define _USE_MATH_DEFINES_#define ll long long#define ld long double#define Accepted 0#define pb push_back#define mp make_pair#define sz(x) (int)(x.size())#define every(x) x.begin(),x.end()#define F first#define S second#define lb lower_bound#define ub upper_bound#define For(i,x,y) for (ll i = x; i <= y; i ++) #define FOr(i,x,y) for (ll i = x; i >= y; i --)#define SpeedForce ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)// ROAD to... Redvoid setIn(string s) { freopen(s.c_str(),"r",stdin); }void setOut(string s) { freopen(s.c_str(),"w",stdout); }void setIO(string s = "") { // cin.exceptions(cin.failbit); // throws exception when do smth illegal // ex. try to read letter into int if (sz(s)) { setIn(s+".in"), setOut(s+".out"); }}const double eps = 0.000001;const ld pi = acos(-1);const int maxn = 1e7 + 9;const int mod = 1e9 + 7;const ll MOD = 1e18 + 9;const ll INF = 1e18 + 123;const int inf = 2e9 + 11;const int mxn = 1e6 + 9; const int N = 2e5+5; const int M = 22;const int pri = 997;const int Magic = 2101;const int dx[] = {-1, 0, 1, 0};const int dy[] = {0, -1, 0, 1};mt19937 gen(chrono::steady_clock::now().time_since_epoch().count()); int rnd (int l, int r) { return uniform_int_distribution<int> (l, r)(gen);}int n, m, q;vector < pair<int, ll> > g[N];ll f[N];int col[N];void dfs (int v, int cc) { col[v] = cc; for (auto e : g[v]) { int to = e.first; ll sum = e.second; if(to < v) sum *= -1; if(col[to] != -1) { assert(f[to] - f[v] == sum); continue; } f[to] = f[v] + sum; dfs(to, cc); }} void solve() { cin >> n >> m >> q; assert(1 <= n && n <= 200000); assert(1 <= m && m <= 200000); assert(1 <= q && q <= 200000); for (int i = 0; i <= n; ++i) { g[i].clear(); col[i] = -1; } for (int i = 1; i <= m; ++i) { int l, r, x; cin >> l >> r >> x; --l; g[l].pb({r, x}); g[r].pb({l, x}); } int cur = 0; for (int i = 0; i <= n; ++i) if(col[i] == -1) { f[i] = 0; dfs(i, ++cur); } for (int i = 1; i <= q; ++i) { int ql, qr; cin >> ql >> qr; --ql; if(col[ql] != col[qr]) { cout << "-1n"; continue; } cout << f[qr] - f[ql] << 'n'; }}int main () { SpeedForce; //setIO("test1"); int T = 1; cin >> T; while(T--) solve(); return Accepted;} coding problems