fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <stdio.h>
  3.  
  4. #define __Shibae__      signed main()
  5. #define IOS             ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  6. #define fiopen(Path)    freopen(Path".INP", "r", stdin); freopen(Path".OUT", "w", stdout);
  7. #define fipen(Path)     freopen(Path".INP", "r", stdin);
  8. #define sz(s)           (int)s.size()
  9. #define all(x)          x.begin(), x.end()
  10. #define maxHeap         priority_queue<int>
  11. #define minHeap         priority_queue<int, vector<int>, greater<int>>
  12. #define getBit(x, k)    (((x) >> (k)) & 1)
  13. #define MASK(i)         (1LL << (i))
  14. #define SQR(x)          (1LL * ((x) * (x)))
  15. #define db              double
  16. #define ld              long double
  17. #define ui              unsigned int
  18. #define ll              long long
  19. #define ii              pair<int, int>
  20. #define pli             pair<ll, int>
  21. #define pil             pair<int, ll>
  22. #define pll             pair<ll, ll>
  23. #define fi              first
  24. #define se              second
  25.  
  26. #define FOR(i, a, b)    for(int i = a, _b = b; i <= _b; i += 1)
  27. #define FOD(i, a, b)    for(int i = a, _b = b; i >= _b; i -= 1)
  28. #define REP(i, a)       for(int i = 0, _a = a; i < _a; i++)
  29. #define pb              push_back
  30. #define fau(u, a)       for(auto &u : a)
  31. #define debug           return cout << "debug", void();
  32.  
  33. using namespace std;
  34.  
  35. const ll mod = 1e9 + 7;
  36. const int INF = 1e9 + 7;
  37. const ll INFLL = (ll)2e18 + 7LL;
  38. const ld PI = acos(-1);
  39. const int MAX = 5e5+5;
  40.  
  41. const int dx[] = {1, -1, 0, 0, -1, 1, 1, -1};
  42. const int dy[] = {0, 0, 1, -1, -1, -1, 1, 1};
  43.  
  44. mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
  45.  
  46. ll Rand(ll l, ll r) 
  47. {
  48.     return uniform_int_distribution<ll>(l, r)(rd);
  49. }
  50.  
  51. template<class SHIBA, class ENGINE>
  52.     bool minimize(SHIBA &x, const ENGINE y)
  53.     {
  54.         if(x > y)
  55.         {
  56.             x = y;
  57.             return true;
  58.         } 
  59.         else return false;
  60.     }
  61. template<class SHIBA, class ENGINE>
  62.     bool maximize(SHIBA &x, const ENGINE y)
  63.     {
  64.         if(x < y)
  65.         {
  66.             x = y;
  67.             return true;
  68.         }
  69.         else return false;
  70.     }
  71.  
  72.  
  73. /* Template by: Nguyen Nhat Anh from Luong Van Chanh High School for the gifted */
  74. /* From Min Tuoi with love */
  75.         /**       TRY HARD        **/
  76.         /**          ORZ          **/
  77.  
  78. /* -----------------[ MAIN CODE ]----------------- */
  79.  
  80. int n, m, q, T;
  81. int a[MAX];
  82. int st[MAX << 1];           
  83. vector<int> dep[MAX << 1];  
  84. int required[MAX];
  85. int res;
  86.  
  87. int jett(int l, int r, int i)
  88. {
  89.     int cnt = 0;
  90.     for (l = l - 1 + n, r = r + n; l < r; l >>= 1, r >>= 1) 
  91.     {
  92.         if (l & 1) {
  93.             dep[l].pb(i);
  94.             cnt++;
  95.             l++;
  96.         }
  97.         if (r & 1) {
  98.             r--;
  99.             dep[r].pb(i);
  100.             cnt++;
  101.         }
  102.     }
  103.     return cnt;
  104. }
  105.  
  106. void input()
  107. {
  108.     cin >> n >> m >> q >> T;
  109.     FOR(i, 1, n) cin >> a[i];
  110.     FOR(i, 1, m)
  111.     {
  112.         int l, r; cin >> l >> r;
  113.         required[i] = jett(l, r, i);
  114.     }
  115. }
  116.  
  117. void modify(int i)
  118. {
  119.     required[i]--;
  120.     if (!required[i]) res++;
  121. }
  122.  
  123. void build()
  124. {
  125.     for (int i = 0; i < n; i++) 
  126.     {
  127.         st[n + i] = a[i + 1];
  128.     }
  129.  
  130.     for (int i = n - 1; i > 0; i--) 
  131.     {
  132.         st[i] = st[i << 1] + st[i << 1 | 1];
  133.     }
  134.  
  135.     for (int i = 1; i < 2 * n; i++) 
  136.     {
  137.         if (!st[i]) fau(x, dep[i]) modify(x);
  138.     }
  139. }
  140.  
  141. void update(int i)
  142. {
  143.     for (int id = i - 1 + n; id > 0; id >>= 1) 
  144.     {
  145.         st[id]--;
  146.         if (!st[id]) fau(x, dep[id]) modify(x);
  147.     }
  148. }
  149.  
  150. void solve()
  151. {
  152.     build();
  153.     while(q--)
  154.     {
  155.         int y; cin >> y;
  156.         int x;
  157.         if (!T) x = y;
  158.         else x = ((res + y) % n) + 1;
  159.  
  160.         update(x);
  161.  
  162.         cout << res << "\n";
  163.     }
  164. }
  165.  
  166. __Shibae__
  167. {
  168.     IOS
  169.     // fiopen("sanlap")
  170.  
  171.     const bool multitest = 0;
  172.     int tt = 1; if(multitest) cin >> tt;
  173.  
  174.     while( tt-- ){
  175.         input();
  176.         solve();
  177.         if(tt) cout << "\n";
  178.     }
  179.  
  180.     return 0;
  181. }
  182.  
Success #stdin #stdout 0.01s 30068KB
comments (?)
stdin
copy 
6 4 6 0
1 1 1 2 1 1
2 6
3 4
5 5
4 4
4 3 4 2 5 6
stdout
copy 
0
0
2
2
3
4
https://ideone.com/apTAUY
language:
C++ (gcc 8.3)
created:
9 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!