SHARE
TWEET

Untitled

a guest May 21st, 2017 270 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5. typedef vector <int> vi;
  6. typedef vector<vi> vvi;
  7. typedef pair<int,int> ii;
  8. #define pb push_back
  9. #define INF 1000000000
  10. #define mp make_pair
  11. #define MOD 1000000007
  12. #define F first
  13. #define S second
  14.  
  15. ll power[100005];
  16.  
  17. int main() {
  18.    
  19.     ios::sync_with_stdio(false);
  20.    
  21.     power[0] = 1;
  22.     for (int i = 1; i < 100005; i++) power[i] = (power[i-1]*2)%MOD;
  23.    
  24.     int n,m,q;
  25.     cin >> n >> m;
  26.     ii edges[m];
  27.     for (int i = 0; i < m; i++){
  28.         cin >> edges[i].F >> edges[i].S;
  29.     }
  30.    
  31.     ll pref[m+5];
  32.     pref[0] = 0;
  33.    
  34.     ll deg[n+5];
  35.     for (int i = 0; i < n+5; i++) deg[i] = 0;
  36.     ll cur = 0;
  37.    
  38.     for (int i = 0; i < m; i ++){
  39.         int a = edges[i].F;
  40.         int b = edges[i].S;
  41.         if (deg[a]%2 == 0){
  42.             cur += power[a];
  43.             cur %= MOD;
  44.         }
  45.         else{
  46.             cur -= power[a];
  47.             if (cur < 0) cur += MOD;
  48.         }
  49.         if (deg[b]%2 == 0){
  50.             cur += power[b];
  51.             cur %= MOD;
  52.         }
  53.         else{
  54.             cur -= power[b];
  55.             if (cur < 0) cur += MOD;
  56.         }
  57.         deg[a] ++;
  58.         deg[b] ++;
  59.         pref[i+1] = cur;
  60.        // cout << i+1 << " " << pref[i+1] << endl;
  61.     }
  62.     cin >> q;
  63.     while (q --){
  64.         int l,r;
  65.         cin >> l >> r;
  66.         if (pref[r] == pref[l-1]) cout << "Yes\n";
  67.         else cout << "No\n";
  68.     }
  69. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top