API tools faq
paste
Advertisement
splash365

Untitled

splash365
Mar 31st, 2021
149
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 12.94 KB | None | 0 0
raw download clone embed print report
  1. ///D
  2.  
  3. #include<bits/stdc++.h>
  4. using namespace std;
  5.  
  6. #define     fast            ios_base::sync_with_stdio(false);cin.tie(NULL)
  7. #define     read            freopen("cases.in","r",stdin)
  8. #define     write           freopen("output.txt","w",stdout)
  9. #define     D(x)            cout << '>' << #x << ':' << x << endl
  10. #define     rep(i,k,n)      for(int i=k;i<n;i++)
  11.  
  12. #define     ll              long long int
  13. #define     ull             unsigned long long int
  14. #define     UI              unsigned int
  15. #define     LD              long double
  16. #define     VI              vector<int>
  17. #define     VLL             vector<ll>
  18. #define     VB              vector<bool>
  19. #define     VLD             vector<LD>
  20. #define     VULL            vector<ull>
  21. #define     VVI             vector<VI>
  22. #define     PII             pair<int, int>
  23.  
  24. #define     MP(x, y)        make_pair(x, y)
  25. #define     PB(x)           push_back(x)
  26. #define     ALL(p)          p.begin(),p.end()
  27. #define     CLR(p)          memset(p, 0, sizeof(p))
  28. #define     MEM(a, b)       memset(a, (b), sizeof(a))
  29. #define     ff              first
  30. #define     ss              second
  31.  
  32. inline void sc(int &a) { scanf("%d", &a); }
  33. inline void sc(ll &a) { scanf("%lld", &a); }
  34. inline void sc(ull &a) { scanf("%llu", &a); }
  35. inline void sc(char *a) { scanf("%s", a); }
  36. inline void sc(LD &a) { cin >> a; }
  37. inline void sc(string &a) { cin >> a; }
  38. inline void sc(double &a) { cin >> a; }
  39. inline void sc(bool &a) { int aa; sc(aa); a = aa; }
  40. template<typename T1, typename T2> inline void sc(pair<T1, T2> &a) { sc(a.ff); sc(a.ss); }
  41. template<typename T> inline void sc(vector<T> &a) { for (T &aa : a) sc(aa); }
  42. template<typename T, typename... Args> inline void sc(T &a, Args &... args) { sc(a); sc(args...); }
  43.  
  44. inline void print(const int &a) { printf("%d", a); }
  45. inline void print(const ll &a) { printf("%lld", a); }
  46. inline void print(const ull &a) { printf("%llu", a); }
  47. inline void print(const char *a) { printf("%s", a); }
  48. inline void print(const char &a) { printf("%c", a); }
  49. inline void print(const string &a) { for (const char &aa : a) print(aa); }
  50. inline void print(const bool &a) { printf("%d", a); }
  51. template<typename T1, typename T2> inline void print(const pair<T1, T2> &a) { print("{"); print(a.ff); print(", "); print(a.ss); print("}"); }
  52. template<typename T> inline void print(const T &a) { int i = 0; print("{"); for (const auto &aa : a) { if (i++) print(", "); print(aa); } print("}"); }
  53. template<typename T, typename... Args> inline void print(const T &a, const Args &... args) { print(a); print(" "); print(args...); }
  54. template<typename... Args> inline void O(const Args &... args) { print(args...); print("\n"); }
  55.  
  56. template < typename T > inline T power(T p, T e, T M){ T ret = 1; for(; e > 0; e >>= 1){ if(e & 1) ret = (ret * p) % M; p = (p * p) % M; } return (T)ret; }
  57. template < typename T > inline T power(T p, T e){ T ret = 1; for(; e > 0; e >>= 1){ if(e & 1) ret = (ret * p); p = (p * p); } return (T)ret; }
  58.  
  59. #ifndef ONLINE_JUDGE
  60. #define debug(args...) { string _s = "[" + string(#args) + "] = ["; print(_s); deb(args); }
  61. void deb() {}
  62. template<typename T, typename... Args>
  63. void deb(T a, Args... args) {
  64. print(a), print((sizeof...(args) ? ", " : "]\n"));
  65. deb(args...);
  66. }
  67. #else
  68.     #define debug(args...)
  69. #endif
  70.  
  71. const double    PI = acos(-1.0);
  72. const double    EPS = 1e-9;
  73. const int       MOD = 1e9+7;
  74. const int       MAXN = 1e6+7;
  75.  
  76. #define int ll
  77.  
  78. int mark[MAXN], odd_prefix[5007];
  79.  
  80. signed main() {
  81. #ifndef ONLINE_JUDGE
  82.     write;
  83. #endif
  84.     read;
  85.     int t;
  86.     sc(t);
  87.     while(t--)
  88.     {
  89.         // MEM(mark, 0);
  90.         // MEM(odd_prefix, 0);
  91.         int n;
  92.         sc(n);
  93.         VI vv(n);
  94.         for (int i = 0; i < n; i++)
  95.         {
  96.             sc(vv[i]);
  97.             // mark[vv[i]]++;
  98.             // if(mark[vv[i]] % 2 == 0)
  99.             //     odd_prefix[i + 1] = odd_prefix[i] - 1;
  100.             // else
  101.             //     odd_prefix[i + 1] = odd_prefix[i] + 1;
  102.         }
  103.         int cnt = 0;
  104.         for (int i = 0; i < n; i++)
  105.         {
  106.             // int mark[MAXN] = {0};
  107.             // mark[vv[i]]++;
  108.             // MEM(mark, 0);
  109.             // map<int, int> mark;
  110.             int odd = 0;
  111.             for (int j = i; j < n; j++)
  112.             {
  113.                 mark[vv[j]]++;
  114.                 if(mark[vv[j]] %2 == 0)
  115.                     odd--;
  116.                 else
  117.                     odd++;
  118.                 if(odd == 1) cnt++;
  119.                 // debug(i, j, cnt);
  120.             }
  121.             for (int j = i; j < n; j++) mark[vv[j]] = 0;
  122.         }
  123.         O(cnt);
  124.     }
  125. }
  126.  
  127. ///M
  128. #include<bits/stdc++.h>
  129. using namespace std;
  130.  
  131. #define     rep(i,k,n)      for(int i=k;i<n;i++)
  132. #define     fast            ios_base::sync_with_stdio(false);cin.tie(NULL)
  133. #define     read            freopen("chess.in","r",stdin)
  134. #define     write           freopen("output.txt","w",stdout)
  135. #define     D(x)            cout << '>' << #x << ':' << x << endl
  136. #define     DD(x,y)         cout << '>' << #x << ':' << x << ' ' << #y << ':' << y << endl
  137. #define     DDD(x,y,z)      cout << '>' << #x << ':' << x << ' ' << #y << ':' << y << ' ' << #z << ':' << z << endl
  138. #define     PI              acos(-1)
  139. #define     MP(x, y)        make_pair(x, y)
  140. #define     PB(x)           push_back(x)
  141. #define     ALL(p)          p.begin(),p.end()
  142. #define     CLR(p)          memset(p, 0, sizeof(p))
  143. #define     MEM(a, b)       memset(a, (b), sizeof(a))
  144. #define     ff              first
  145. #define     ss              second
  146. #define     sf              scanf
  147. #define     pf              printf
  148. #define     PII             pair<int, int>
  149. #define     ll              long long int
  150. #define     ull             unsigned long long int
  151.  
  152. inline int two(int n) { return 1 << n; }
  153. inline int test(int n, int b) { return (n>>b)&1; }
  154. inline void set_bit(int & n, int b) { n |= two(b); }
  155. inline void unset_bit(int & n, int b) { n &= ~two(b); }
  156. inline int last_bit(int n) { return n & (-n); }
  157. inline int ones(int n) { int res = 0; while(n && ++res) n-=n&(-n); return res; }
  158.  
  159. template < class T > inline T gcd(T a, T b) {while(b) { a %= b; swap(a, b); } return a;}
  160. template < class T > inline T bigmod(T p, T e, T M){
  161.     ll ret = 1;
  162.     for(; e > 0; e >>= 1){ if(e & 1) ret = (ret * p) % M; p = (p * p) % M; }
  163.     return (T)ret;
  164. }
  165. template < class T > inline T power(T a, T n) {
  166.     if(n==0) return 1;
  167.     if(n==1) return a;
  168.     T R = power(a,n/2);
  169.     return (n%2==0) ? R*R : R*a*R;
  170. }
  171.  
  172. int fx4[] = {0, 0, -1, +1};
  173. int fy4[] = {+1, -1, 0, 0};
  174. int fx8[] = {1, 1, 0, -1, -1, -1, 0, 1, 0};
  175. int fy8[] = {0, 1, 1, 1, 0, -1, -1, -1, 0};
  176. int fx8Knight[] = {+2, +2, +1, -1, -2, -2, -1, +1};
  177. int fy8Knight[] = {+1, -1, -2, -2, -1, +1, +2, +2};
  178.  
  179. const int MAXN = 1e5 + 3;
  180.  
  181. #define int ll
  182.  
  183. signed main()
  184. {
  185. // #ifndef ONLINE_JUDGE
  186. //     write;
  187.     read;
  188. // #endif
  189.     //fast;
  190.     int t;
  191.     cin >> t;
  192.     while(t--){
  193.         int n,k;
  194.         cin>>n>>k;
  195.         int a = n-1 - (k+1)+1;
  196.         int lim = (n-1)/(k+1);
  197.         int sum = lim*(2*a+(lim-1)*(-k-1));
  198.         sum/=2;
  199.         sum*=2;
  200.         sum+=(n-1);
  201.         int tot = n*n - sum;
  202.         cout<<tot-1<<endl;
  203.     }
  204.     return 0;
  205. }
  206.  
  207. ///G
  208.  
  209. #include<bits/stdc++.h>
  210. #include <ext/pb_ds/assoc_container.hpp>
  211. using namespace __gnu_pbds;
  212. using namespace std;
  213.  
  214. #define     int                     long long
  215. #define     unt                     unsigned int
  216. #define     LD                      long double
  217.  
  218. #define     nl                      "\n"
  219. #define     nspace(s)               for(int i=0;i<s;i++)cout<<" ";
  220. #define     wat1(s,x)               nspace(s) ;  cout << #x << " is " << x << nl;
  221. #define     wat2(s,x,y)             nspace(s) ;  cout << #x << " is " << x << "    " << #y << " is " << y << nl ;
  222. #define     wat3(s,x,y,z)           nspace(s) ;  cout << #x << " is " << x << "    " << #y << " is " << y << "    "<< #z << " is " << z << nl;
  223. #define     wat4(s,x,y,z,a)         nspace(s) ;  cout << #x << " is " << x << "    " << #y << " is " << y << "    "<< #z << " is " << z << "    " << #a << " is " << a << nl;
  224. #define     wat5(s,x,y,z,a,b)       nspace(s) ;  cout << #x << " is " << x << "    " << #y << " is " << y << "    "<< #z << " is " << z << "    " << #a << " is " << a << "    " << #b << " is " << b << nl;
  225. #define     line                    cout<<"\n";
  226. #define     gap                     cout<<" ";
  227.  
  228. #define     pii                     pair<int, int>
  229. #define     vpi                     vector<pii>
  230. #define     vii                     vector<int>
  231. #define     vsi                     vector<string>
  232. #define     umap                    unordered_map
  233. #define     pqueue                  priority_queue
  234. #define     mip                     make_pair
  235. #define     pb                      push_back
  236. #define     ppb                     pop_back
  237. #define     pf                      push_front
  238. #define     ppf                     pop_front
  239. #define     ff                      first
  240. #define     ss                      second
  241. #define     all(x)                  x.begin(), x.end()
  242. #define     vlb(x, y)               lower_bound(all(x), y)-x.begin()
  243. #define     vub(x, y)               upper_bound(all(x), y)-x.begin()
  244. #define     takes(a,n,type)         type *a=new type[n+10];
  245. #define     mem(a,x)                memset(a, x, sizeof(a))
  246.  
  247. #define     sp(x)                   setprecision(x) << fixed
  248. #define     PI                      acos(-1.0)
  249. #define     eps                     1e-12
  250.  
  251. #define     read                    freopen("wifi.in","r",stdin)
  252. #define     write                   freopen("output.txt","w",stdout)
  253. #define     file_io                 read;write
  254. #define     fast_io                 ios_base::sync_with_stdio(0);cin.tie(0)
  255.  
  256. #define     fbo                     find_by_order
  257. #define     ofk                     order_of_key
  258.  
  259.  
  260. inline      int    sci()            {int a;scanf("%lld",&a);return a;}
  261. inline      char   scc()            {char a;scanf("%c",&a);return a;}
  262. inline      double scd()            {double a;scanf("%lf",&a);return a;}
  263.  
  264. const       int                     big = INT_MAX;
  265. const       int                     sml = INT_MIN;
  266. const       int                     mod = 100000007;
  267.  
  268. typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
  269.  
  270. int  x4[] = {1, 0, -1, 0};
  271. int  y4[] = {0, 1, 0, -1};
  272. int  x8[] = {1,  0, -1, 0, 1, -1, 1, -1};
  273. int  y8[] = { 0, 1, 0, -1, 1, -1, -1, 1};
  274. int  kx[] = {2, -2, 2, -2, 1, -1, 1, -1};
  275. int  ky[] = { -1, 1, 1, -1, 2, -2, -2, 2};
  276.  
  277.  
  278. inline bool valid(int x, int y, int rs, int cs, int r, int c) {return ((x >= rs && x <= r) && (y >= cs && y <= c));}
  279.  
  280. inline int  two(int n) { return 1LL << n; }
  281. inline int  db2(int n) {  return !(n & 1LL); }
  282. inline bool ispof2 (int x) {return x && (!(x & (x - 1)));}
  283. inline int  check(int n, int b) { return (n >> b) & 1LL; }
  284. inline void biton(int & n, int b) { n |= two(b); }
  285. inline void bitoff(int & n, int b) { n &= ~two(b); }
  286. inline int  ones(int n) { int res = 0; while (n && ++res) n -= n & (-n); return res; }
  287.  
  288.  
  289. int mpow(int x, int y, int p)
  290. {
  291.     int res = 1;
  292.     x = x % p;
  293.     if (x == 0) return 0;
  294.     while (y > 0)
  295.     {
  296.         if (y & 1)  res = (res * x) % p;
  297.         y = y >> 1;
  298.         x = (x * x) % p;
  299.     }
  300.     return res;
  301. }
  302.  
  303.  
  304.  
  305. void fileoj()
  306. {
  307.     #ifndef ONLINE_JUDGE
  308.         file_io;
  309.     #endif
  310. }
  311.  
  312.  
  313.  
  314. int pre[1000000][30];
  315.  
  316.  
  317.  
  318. int ok(vii &v,int val,int mid)
  319. {
  320.     for(int i=0;i<=v.size()-mid;i++)
  321.     {
  322.         int r = 0;
  323.         if(i==0)
  324.         {
  325.             for(int j = 21;j>=0;j--)
  326.             {
  327.                 if(pre[i+mid-1][j])biton(r,j);
  328.             }
  329.             if(r<=val)return r;
  330.             continue;
  331.         }
  332.         for(int j = 21;j>=0;j--)
  333.         {
  334.             if(pre[i+mid-1][j]-pre[i-1][j])biton(r,j);
  335.         }
  336.         if(r<=val)return r;
  337.     }
  338.     return 0;
  339. }
  340.  
  341.  
  342. int bs(vii &v,int val)
  343. {
  344.     int lo = 1;
  345.     int hi = v.size()+1;
  346.     int ans = 0;
  347.     while(lo<hi)
  348.     {
  349.         int mid = (lo+hi)/2;
  350.        
  351.         int okz = ok(v,val,mid);
  352.         //wat2(4,okz,mid);
  353.         if(okz)
  354.         {
  355.             lo = mid+1;
  356.             ans = mid;
  357.         }
  358.         else
  359.         {
  360.             hi = mid;
  361.         }
  362.     }
  363.     return ans;
  364. }
  365.  
  366. int32_t main()
  367. {
  368.     read;
  369.     int t=1;
  370.     cin>>t;
  371.     for(int tc=1;tc<=t;tc++)
  372.     {
  373.         int n,v;
  374.         cin>>n>>v;
  375.         vii vc;
  376.         for(int i=0;i<n;i++)
  377.         {
  378.             int a;
  379.             cin>>a;
  380.             vc.pb(a);
  381.             for(int j=21;j>=0;j--)
  382.             {
  383.                 pre[i][j]+=check(a,j);
  384.             }
  385.            
  386.            
  387.         }
  388.         for(int i=1;i<n;i++)
  389.         {
  390.             for(int j=21;j>=0;j--)
  391.             {
  392.                 pre[i][j]=pre[i][j]+pre[i-1][j];
  393.             }
  394.            
  395.         }
  396.         int ans = bs(vc,v);
  397.         for(int i=0;i<n;i++)
  398.         {
  399.             for(int j=21;j>=0;j--)
  400.             {
  401.                 pre[i][j]=0;
  402.             }
  403.         }
  404.        
  405.         cout<<ans<<nl;
  406.     }
  407. }
  408.  
  409.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!