fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. #define fi first
  5. #define se second
  6. #define siz(x) (int)(x.size())
  7. #define all(x) x.begin(), x.end()
  8. #define debug_arr(x,len) for(int _=1; _<=len; _++) cout<<x[_]<<" "; cout<<'\n';
  9. #define debug(x) cout<<'\n'<<#x<<": "<<x<<'\n';
  10. const int maxN=1e7+5, maxM=1e3+5;
  11.  
  12. int n, m, k, q, good[maxN], a[maxM][maxM], check[maxM][maxM], pref[maxM][maxM];
  13. vector<int>snt;
  14.  
  15. void sieve()
  16. {
  17.     for(int i=2; i<=1e7; i+=1) good[i]=1;
  18.     for(int i=2; i<=1e7; i+=1)
  19.     {
  20.         if(good[i])
  21.         {
  22.             for(int j=i*2; j<=1e7; j+=i) good[j]=0;
  23.         }
  24.     }
  25.     for(int i=2; i<=1e7; i+=1)
  26.     {
  27.         if(good[i]) snt.push_back(i);
  28.     }
  29. }
  30.  
  31. void solve()
  32. {
  33.     int row1=1, col1=n, row2=1, col2=m, dem=-1;
  34.     while(row1<=col1 && row2<=col2)
  35.     {
  36.         for(int i=row2; i<=col2; i+=1)
  37.         {
  38.             if(!check[row1][i] && !a[row1][i]) a[row1][i]=snt[++dem];
  39.             // cout<<row1<<" "<<i<<'\n';
  40.         }
  41.         row1++;
  42.         for(int i=row1; i<=col1; i+=1)
  43.         {
  44.             if(!check[i][col2] && !a[i][col2]) a[i][col2]=snt[++dem];
  45.             // cout<<i<<" "<<col2<<'\n';
  46.         }
  47.         col2--;
  48.         for(int i=col2; i>=row2; i-=1)
  49.         {
  50.             if(!check[col1][i] && !a[col1][i]) a[col1][i]=snt[++dem];
  51.             // cout<<col1<<" "<<i<<'\n';
  52.         }
  53.         col1--;
  54.         for(int i=col1; i>=row1; i-=1)
  55.         {
  56.             if(!check[i][row2] && !a[i][row2]) a[i][row2]=snt[++dem];
  57.             // cout<<i<<" "<<row2<<'\n';
  58.         }
  59.         row2++;
  60.     }
  61.     // for(int i=1; i<=n; i+=1)
  62.     // {
  63.     //     for(int j=1; j<=m; j+=1) cout<<a[i][j]<<" "; cout<<'\n';
  64.     // }
  65.     for(int i=1; i<=n; i+=1)
  66.     {
  67.         for(int j=1; j<=m; j+=1) 
  68.         {
  69.             pref[i][j]=pref[i-1][j]+pref[i][j-1]-pref[i-1][j-1]+a[i][j];
  70.         }
  71.     }
  72.     for(int i=1; i<=q; i+=1)
  73.     {
  74.         int x1, y1, x2, y2;
  75.         cin>>x1>>y1>>x2>>y2;
  76.         int ans=pref[x2][y2]-pref[x1-1][y2]-pref[x2][y1-1]+pref[x1-1][y1-1];
  77.         cout<<ans<<'\n';
  78.     }
  79. }
  80.  
  81. int32_t main()
  82. {
  83.     ios_base::sync_with_stdio(0); cin.tie(0);
  84.     sieve();
  85.     cin>>n>>m>>k>>q;
  86.     for(int i=1; i<=k; i+=1)
  87.     {
  88.         int x,y; cin>>x>>y;
  89.         check[x][y]=1;
  90.     }
  91.     solve();
  92. }
  93.  
Success #stdin #stdout 0.29s 91340KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Mp6sfb
language:
C++14 (gcc 8.3)
created:
10 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!