fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. using namespace std;
  4. int n,m,q,k,a[1003][1003],st[4003],x[100005],ans[2000006];
  5. set <int> se;
  6. map <int,int> mp;
  7. vector <pair<int,int>> ve[2000006];
  8. void UPDATE(int id, int l, int r, int i, int v)
  9. {
  10.     if (l>i || r<i) return;
  11.     else if (l==r)
  12.     {
  13.         st[id]=v;
  14.         return;
  15.     }
  16.     int mid=(l+r)/2;
  17.     if (i<=mid) UPDATE(id*2,l,mid,i,v);
  18.     else UPDATE(id*2+1,mid+1,r,i,v);
  19.     st[id]=max(st[id*2],st[id*2+1]);
  20. }
  21. int GET(int id, int l, int r, int u, int v)
  22. {
  23.     if (l>v || r<u) return -1e18;
  24.     else if (l>=u && r<=v) return st[id];
  25.     int mid=(l+r)/2;
  26.     return max(GET(id*2,l,mid,u,v),GET(id*2+1,mid+1,r,u,v));
  27. }
  28. void NEN()
  29. {
  30.     int j=0;
  31.     for (int i=1;i<=q;i++) se.insert(x[i]%k);
  32.     for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) se.insert(a[i][j]%k);
  33.     for (int v : se) j++,mp[v]=j;
  34.     for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) ve[mp[a[i][j]%k]].push_back({i,j});
  35. }
  36. void SOLVE()
  37. {
  38.     for (int i=1;i<=2000000;i++) if (ve[i].size())
  39.     {
  40.         int res=0;
  41.         for (int j=1;j<=m;j++) UPDATE(1,1,m,j,0);
  42.         for (pair <int,int> p : ve[i])
  43.         {
  44.             int y=p.second,mx=GET(1,1,m,1,y)+1;
  45.             if (GET(1,1,m,y,y)<mx) UPDATE(1,1,m,y,mx),res=max(res,mx);
  46.         }
  47.         ans[i]=res;
  48.     }
  49. }
  50. signed main()
  51. {
  52.     ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
  53.     cin>>n>>m>>q>>k;
  54.     for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) cin>>a[i][j];
  55.     for (int i=1;i<=q;i++) cin>>x[i];
  56.     NEN(),SOLVE();
  57.     for (int i=1;i<=q;i++) cout<<ans[mp[x[i]%k]]<<'\n';
  58.     return 0;
  59. }
Success #stdin #stdout 0.02s 51392KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/QPij3Y
language:
C++14 (gcc 8.3)
created:
1 day 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!