fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long
  5.  
  6. bool getBit(ll num, int idx)
  7. {
  8.     return ((num >> idx) & 1);
  9. }
  10.  
  11. const int mod=1e9+7;
  12.  
  13. void solve()
  14. {
  15.     int N;
  16.     cin>>N;
  17.     vector<int>A(N);
  18.     for (int I=0;I<N;I++)
  19.     {
  20.         cin>>A[I];
  21.     }
  22.     sort(A.begin(),A.end());
  23.     vector<map<int,int>>B;
  24.     vector<vector<int>>temp;
  25.     temp.push_back({0});
  26.     for (int I=1;I<(1<<N);I++)
  27.     {
  28.         vector<int>V;
  29.         for (int J=0;J<N;J++)
  30.         {
  31.             if (getBit(I,J))
  32.             {
  33.                 V.push_back(A[J]);
  34.             }
  35.         }
  36.         temp.push_back(V);
  37.     }
  38.     sort(temp.begin(),temp.end());
  39.     for (auto it:temp)
  40.     {
  41.         map<int,int>tempe;
  42.         for (auto itt:it)
  43.         {
  44.             tempe[itt]++;
  45.         }
  46.         B.push_back(tempe);
  47.     }
  48.     map<int,vector<ll>>primes;
  49.     for (int I=0;I<N;I++)
  50.     {
  51.         vector<ll>V((1<<N)+2,0);
  52.         primes[A[I]]=V;
  53.     }
  54.     int Q;
  55.     cin>>Q;
  56.     for (int I=0;I<Q;I++)
  57.     {
  58.         int l,r,x;
  59.         cin>>l>>r>>x;
  60.         primes[x][l]++;;
  61.         primes[x][r+1]--;
  62.     }
  63.     int sz=B.size();
  64.     for (int I=0;I<N;I++)
  65.     {
  66.         for (int J=1;J<sz;J++)
  67.         {
  68.             primes[A[I]][J]+=primes[A[I]][J-1];
  69.         }
  70.         for (int J=1;J<sz;J++)
  71.         {
  72.             if (B[J][A[I]]%2==0)
  73.             {
  74.                 if (primes[A[I]][J]%2!=0)
  75.                 {
  76.                     B[J][A[I]]=1;
  77.                 }
  78.             }
  79.             else if (B[J][A[I]]%2!=0)
  80.             {
  81.                 if (primes[A[I]][J]%2!=0)
  82.                 {
  83.                     B[J][A[I]]=0;
  84.                 }
  85.             }
  86.         }
  87.     }
  88.  
  89.     for (auto it:B)
  90.     {
  91.         ll res=1;
  92.  
  93.         for (auto itt:it)
  94.         {
  95.             if (itt.second>0)
  96.             {
  97.                 res*=itt.first;
  98.                 res%=mod;
  99.             }
  100.         }
  101.         if (res == 0)continue;
  102.         cout<<res<<" ";
  103.     }
  104.     cout<<endl;
  105. }
  106.  
  107. int main()
  108. {
  109.     cin.tie(0);
  110.  
  111.     int t = 1;
  112.  
  113.     //cin >> t;
  114.  
  115.     while (t--)
  116.     {
  117.         solve();
  118.     }
  119.  
  120.     return 0;
  121. }
  122.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 

	

		
	 
	
	
			

					
			
			
			
			
			
			
			
			

			
			
			
		

	
		
		

			

			                        







			
			

				

	
					
					 https://ideone.com/T8km83
					
					
					
					
					

												

												
						
						

					

					
					
					

						
language:

						
C++14 (gcc 8.3)

					

					

						
created:
								
						
12 days 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!