fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define debug     cout << "ok\n";
  4. #define SQR(x)    (1LL * ((x) * (x)))
  5. #define MASK(i)   (1LL << (i))
  6. #define BIT(x, i) (((x) >> (i)) & 1)
  7. #define fi        first
  8. #define se        second
  9. #define pb        push_back
  10.  
  11. #define mp make_pair
  12. #define pii pair<int,int>
  13. #define pli pair<ll,int>
  14. #define vi vector<int>
  15.  
  16. #define FAST ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  17.  
  18. typedef long long ll;
  19. typedef unsigned long long ull;
  20. typedef long double ld;
  21. typedef unsigned int ui;
  22.  
  23. using namespace std;
  24.  
  25. const int M = 1e9 + 7;
  26. const int INF = 1e9 + 7;
  27. const ll INFLL = (ll)2e18 + 7LL;
  28. const ld PI = acos(-1);
  29.  
  30. const int dx[] = {1, -1, 0, 0, -1, 1, 1, -1};
  31. const int dy[] = {0, 0, 1, -1, -1, -1, 1, 1};
  32.  
  33. template<class _, class __>
  34.     bool minimize(_ &x, const __ y){
  35.         if(x > y){
  36.             x = y;
  37.             return true;
  38.         } else return false;
  39.     }
  40. template<class _, class __>
  41.     bool maximize(_ &x, const __ y){
  42.         if(x < y){
  43.             x = y;
  44.             return true;
  45.         } else return false;
  46.     }
  47.  
  48. template<class _,class __>
  49.     void Add(_ &x, const __ y) {
  50.         x += y;
  51.         if (x >= M) {
  52.             x -= M;
  53.         }
  54.         return;
  55.     }
  56.  
  57. template<class _,class __>
  58.     void Diff(_ &x, const __ y) {
  59.         x -= y;
  60.         if (x < 0) {
  61.             x += M;
  62.         }
  63.         return;
  64.     }
  65.  
  66. //--------------------------------------------------------------
  67.  
  68. const int MaxN = 670;
  69.  
  70. int n,Q,x,y,a[MaxN],cnt[MaxN][3];
  71. vi f[MaxN][MaxN];
  72.  
  73. struct Adj {
  74.     int a;
  75.     int b;
  76.     int c;
  77. };
  78.  
  79. void sol() {
  80.     cin >> n >> Q >> x >> y;
  81.     for (int i=1;i<=n;i++) cin >> a[i];
  82.     for (int i=1;i<=n;i++) {
  83.         for (int j=0;j<3;j++) cnt[i][j] = cnt[i-1][j];
  84.         cnt[i][a[i]]++;
  85.     }
  86.     for (int i=0;i<=n;i++) {
  87.         for (int j=0;i+j<=n;j++) {
  88.             f[i][j].resize(n - i - j + 1);
  89.             for (int & x : f[i][j]) x = 0;
  90.         }
  91.     }
  92.     queue<Adj> q;
  93.     for (int i=1;i<=n;i++) {
  94.         f[i][0][0] = 1;
  95.         q.push((Adj){i,0,0});
  96.     }
  97.     while (!q.empty()) {
  98.         int a = q.front().a;
  99.         int b = q.front().b;
  100.         int c = q.front().c;
  101.         q.pop();
  102.         for (int i=0;i<=a && i<=x;i++) {
  103.             for (int j=0;j <= b && i+j<=x;j++) {
  104.                 for (int ii=0;ii+i<=a && ii<=y;ii++) {
  105.                     for (int jj=0;jj+j<=b && ii+jj<=y;jj++) {
  106.                         int k = x - i - j;
  107.                         int kk = y - ii - jj;
  108.                         if (k + kk > c) continue;
  109.                         if (!f[a-i-ii+k+jj][b-j-jj+i+kk][c-k-kk+j+ii]) {
  110.                             f[a-i-ii+k+jj][b-j-jj+i+kk][c-k-kk+j+ii] = f[a][b][c] + 1;
  111.                             q.push((Adj){a-i-ii+k+jj,b-j-jj+i+kk,c-k-kk+j+ii});
  112.                         }
  113.                     }
  114.                 }
  115.             }
  116.         }
  117.     }
  118.     while (Q--) {
  119.         int l,r;
  120.         cin >> l >> r;
  121.         cout << f[cnt[r][0] - cnt[l-1][0]][cnt[r][1] - cnt[l-1][1]][cnt[r][2] - cnt[l-1][2]] - 1 << '\n';
  122.     }
  123. }
  124.  
  125. signed main() {
  126. 	freopen("light.inp","r",stdin);
  127. 	freopen("light.out","w",stdout);
  128. 	FAST
  129. 	int t=1;
  130. //	cin >> t;
  131. 	while (t--) sol();
  132. }
  133.  
Success #stdin #stdout 0.01s 14440KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/7D6ct9
language:
C++14 (gcc 8.3)
created:
7 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!