Submission #235172

#TimeUsernameProblemLanguageResultExecution timeMemory
235172kartelUsmjeri (COCI17_usmjeri)C++14
0 / 140
479 ms20288 KiB
#include <bits/stdc++.h> //#include <ext/pb_ds/assoc_container.hpp> //#include <ext/pb_ds/tree_policy.hpp> #define in(x) freopen(x, "r", stdin) #define out(x) freopen(x, "w", stdout) #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #pragma GCC optimize("-O3") #define F first #define S second #define pb push_back #define N +500500 #define M ll(1e9 + 7) #define sz(x) (int)x.size() #define re return #define oo ll(1e18) #define el '\n' #define pii pair <int, int> using namespace std; //using namespace __gnu_pbds; //typedef tree <int, null_type, less_equal <int> , rb_tree_tag, tree_order_statistics_node_update> ordered_set; typedef long long ll; typedef long double ld; int t[4 * N], D[4 * N], i, n, l, r, x, y, m; ll ans; void push(int v) { if (D[v]) { D[v * 2] += D[v]; D[v * 2 + 1] += D[v]; t[v] += D[v]; D[v] = 0; } } void upd(int v, int l, int r, int tl, int tr) { push(v); if (l == tl && r == tr) {D[v]++;push(v); return;} if (l > r || tl > r || tl > tr || l > tr) return; int md = (l + r) >> 1; upd(v * 2, l, md, tl, min(tr, md)); upd(v * 2 + 1, md + 1, r, max(md + 1, tl), tr); } int fnd(int v, int l, int r, int ps) { push(v); if (l == r) return t[v];else { int md = (l + r) >> 1; if (ps <= md) return fnd(v * 2, l, md, ps); else return fnd(v * 2 + 1, md + 1, r, ps); } } int main() { srand(time(0)); ios_base::sync_with_stdio(0); iostream::sync_with_stdio(0); ios::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); // in("input.txt"); // out("output.txt"); cin >> n >> m; for (i = 1; i < n; i++) { cin >> x >> y; upd(1, 1, n + 1, y, y); } for (i = 1; i <= m; i++) { cin >> l >> r; if (l > r) swap(l, r); upd(1, 1, n + 1, l + 1, r); } ans = 2; for (i = 1; i <= n; i++) if (fnd(1, 1, n + 1, i) > 0 && fnd(1, 1, n + 1, i + 1) == 0) ans *= 2, ans %= M; cout << ans; } // //110000 //110000 //001100 //001100 //000011
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...