fork download
copy 
  1.     #include<bits/stdc++.h>
  2.  
  3.     using namespace std;
  4.  
  5.     ///***********SEXY & I KNOW IT******************///
  6.     #define uli unsigned long long int
  7.     ///***input******// for +ve int
  8.     inline uli in() {
  9.         uli p=0; register char ch=0;
  10.         while(ch<'0' or ch>'9') {ch=getchar();}
  11.         while(ch>='0' and ch<='9') {p=(p<<1)+(p<<3)+ch-'0'; ch=getchar();}
  12.         return p;
  13.     }
  14.     ///***output*****// for +ve int
  15.     #define pc(x) putchar(x)
  16.     inline void dukya(uli n){
  17.             uli N = n, rev, count_ = 0;
  18.             rev = N;
  19.             if (N == 0) { pc('0'); pc('\n'); return ;}
  20.             while ((rev % 10) == 0) { count_++; rev /= 10;}
  21.             rev = 0;
  22.             while (N != 0) { rev = (rev<<3) + (rev<<1) + N % 10; N /= 10;}
  23.             while (rev != 0) { pc(rev % 10 + '0'); rev /= 10;}
  24.             while (count_--) pc('0');
  25.             pc('\n');
  26.         }
  27.     ///
  28.     #define li  long long int
  29.     #define ld long double
  30.     #define lega(n) scanf("%lld", &n)
  31.     #define dley(n, m) scanf("%lld %lld", &n, &m)
  32.     #define dega(n) printf("%lld\n", n)
  33.     #define chal(n) for(li i=0;i<n; ++i)
  34.     #define FOR(i, n, c) for(i=c; i<n; i++)
  35.     #define fpos(n) for(auto pos=n.begin(); pos!=n.end(); ++pos)
  36.     #define frng(n) for(auto val : n)
  37.     #define ot(n) cout<<n<<"\n"
  38.     #define wl(n) while(n--)
  39.     #define vs vector<string>
  40.     #define vi vector<li>
  41.     #define ii pair<li, li>
  42.     #define mii map<ii, li>
  43.     #define mli map<li, li>
  44.     #define met multiset<li>
  45.     #define p_b(n) push_back(n)
  46.     #define ict int test_case=in(); wl(test_case)
  47.     #define INF 1000000009
  48.     #define mod 1000000007
  49.     #define EPS 0;.000000001
  50.     #define lipos(s) s&-s
  51.     #define fastScan ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL)
  52.     ///****************************************///
  53.     void maxSubarray(vi arr, li n, li m)
  54.     {
  55.         li x, prefix = 0, maxim = 0;
  56.  
  57.         set<li> S;
  58.         S.insert(0);
  59.         map<li, li> mm;
  60.         vi pre;
  61.        li co=0;
  62.         for (li i = 0; i < n; i++)
  63.         {
  64.             prefix = (prefix + arr[i])%m;
  65.             auto it = S.upper_bound(prefix);
  66.             maxim=max(maxim, prefix);
  67.             if (it != S.end())
  68.                 {
  69.                     maxim=max(maxim, (prefix - (*it) + m));
  70.                 }
  71.             S.insert(prefix);
  72.             pre.push_back(prefix);
  73.         }
  74.         mm[0]++;
  75.         chal(n)
  76.         {
  77.             if((pre[i]-maxim)>=0)
  78.                 co+=mm[pre[i]-maxim];
  79.             co+=mm[pre[i]-maxim+m];
  80.             mm[pre[i]]++;
  81.         }
  82.       ot(maxim<<" "<<co);
  83.         return;
  84.     }
  85.     int main()
  86.     {
  87.         ict
  88.         {
  89.             li n=in();
  90.            li p=in();
  91.             vi A;
  92.             chal(n)
  93.             A.push_back(in());
  94.             maxSubarray(A, n, p);
  95.  
  96.         }
  97.     }
  98.  
Success #stdin #stdout 0s 15248KB
comments (?)
stdin
copy 
4
2 3
1 2
3 5
2 4 3
3 100
1 3 5
4 3
1 2 3 4
stdout
copy 
2 1
4 2
9 1
2 2
https://ideone.com/XE9HKo
language:
C++14 (gcc 8.3)
created:
6 years 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!