fork download
copy 
  1. #include<cstdio>
  2. #include<vector>
  3. #include<algorithm>
  4. #include<string.h>
  5. #include<iostream>
  6. #define mp make_pair
  7.  
  8. using namespace std;
  9.  
  10. typedef long long int ll;
  11.  
  12. bool cmp(pair<ll, ll> &a, pair<ll, ll> &b){
  13.     if(a.second == b.second) return a.first < b.first;
  14.     return a.second > b.second;
  15. }
  16.  
  17. ll ans[300001], a[100007], b[100007], n, m, initial_len, mark[100007], count_filter, max_up, n1, n2;
  18.  
  19. vector< pair<ll, ll> > bat, filter;
  20.  
  21. void initialize(){
  22.     for(int j=0; j<300001; j++)
  23.         ans[j] = 0;
  24.  
  25.     for(int j=0; j<100001; j++){
  26.         a[j] = 0;
  27.         b[j] = 0;
  28.         mark[j] = 0;
  29.     }
  30.  
  31.     bat.clear();
  32.     filter.clear();
  33.     //selected.clear();
  34.     return;
  35. }
  36.  
  37. void multiply(){
  38.     for(int j=0; j<n1; j+=17){
  39.         ll temp = 0, curr, counts = 0;
  40.         if(j + 16 < n1) curr = j+16;
  41.         else{
  42.             curr = n1 - 1;
  43.             counts = 17 - (n1 - 1 - j + 1);
  44.         }
  45.         while(counts < 17){
  46.             temp = temp*10 + a[curr];
  47.             curr--;
  48.             counts++;
  49.         }
  50.         curr = j;
  51.         ll carry = 0;
  52.         for(int i = n2 - 1; i >= 0; i--){
  53.             ans[curr] += temp*b[i] + carry;
  54.             carry = ans[curr]/10;
  55.             ans[curr] = ans[curr] % 10;
  56.             curr++;
  57.         }
  58.         while(carry){
  59.             ans[curr++] = carry % 10;
  60.             carry /= 10;
  61.         }
  62.     }
  63.     return;
  64. }
  65.  
  66. /*void set_bits(int day){
  67.     int start = day;
  68.     for(int j=0; j < initial_len; j++)
  69.         ans[start++] += k[j];
  70.     return;
  71. }*/
  72.  
  73. void build_ans(){
  74. 	n2 = 0;
  75.     for(int j=max_up; j >= 0; j--)
  76.        b[n2++] = mark[j];
  77.    	//n2 = max_up + 1;
  78.     multiply();
  79.     return;
  80. }
  81.  
  82. void select_bats(){
  83.     int avail = m;
  84.     for(int j=0; j < count_filter && avail > 0; j++){
  85.         pair<ll, ll> p = filter[j];
  86.         if(j == 0) max_up = p.second;
  87.         if(mark[ p.second ] == 0 || j == count_filter - 1){
  88.             //printf("%d %d\n",p.first, p.second);
  89.             for(ll i=p.first; i <= p.second; i++)
  90.                 mark[i] = 1;
  91.             avail--;
  92.         }
  93.         else{
  94.             ll i;
  95.             for(i = p.second; i >= p.first; i--)
  96.                 if(mark[i] == 1) continue;
  97.                 else break;
  98.             if(i < p.first) continue;
  99.             if(i > filter[j+1].second || (i - p.first) > (filter[j+1].second - filter[j+1].first)){
  100.                 //printf("%d %d\n",p.first, p.second);
  101.                 for(int t=p.first; t <= p.second; t++)
  102.                     mark[t] = 1;
  103.                 avail--;
  104.             }
  105.         }
  106.     }
  107.     return;
  108. }
  109.  
  110. void filter_bats(){
  111.     ll left = bat[0].first, right = bat[0].second;
  112.     for(int j=0; j<n; j++){
  113.         pair<int, int> p = bat[j];
  114.         if(j!= 0 && p.first >= left && right  >= p.second ) continue;
  115.         filter.push_back(p);
  116.         if(left > p.first) left = p.first;
  117.         if(right < p.second) right = p.second;
  118.     }
  119.     count_filter = filter.size();
  120.     return;
  121. }
  122.  
  123. void solve(){
  124.     sort(bat.begin(), bat.end(), cmp);
  125.  
  126.     /*for(int j=0; j<n; j++)
  127.         printf("%d %d\n",bat[j].first, bat[j].second);*/
  128.  
  129.     filter_bats();
  130.     select_bats();
  131.     build_ans();
  132.  
  133.     /*for(int j=0; j<n1; j++)
  134.     	printf("%lld ",a[j]);
  135.     printf("\n");
  136.     for(int j=0; j<n2; j++)
  137.     	printf("%lld ",b[j]);
  138.     printf("\n");*/
  139.  
  140.     ll carry = 0;
  141.     for(int j=0; j < 300001; j++){
  142.         ans[j] += carry;
  143.         carry = ans[j]/2;
  144.         ans[j] = ans[j] % 2;
  145.     }
  146.  
  147.     int j = 300000;
  148.     while(ans[j] == 0 && j >= 0)
  149.         j--;
  150.     if(j < 0){
  151.     	printf("0\n");
  152.     	return;
  153.     }
  154.     for(; j >= 0; j--)
  155.         printf("%lld",ans[j]);
  156.     printf("\n");
  157.     return;
  158. }
  159.  
  160. int main(){
  161.     int t;
  162.     scanf("%d",&t);
  163.     while(t--){
  164.         initialize();
  165.         scanf("%lld %lld",&n ,&m);
  166.         for(int j=0; j<n; j++){
  167.             ll l, r;
  168.             scanf("%lld %lld",&l ,&r);
  169.             bat.push_back(mp(l, r));
  170.         }
  171.         char s[100001];
  172.         scanf("%s",&s);
  173.         initial_len = strlen(s);
  174.         for(int j=0; j<initial_len; j++)
  175.             a[j] = s[initial_len - j - 1] - '0';
  176.         n1 = initial_len;
  177.  
  178.         solve();
  179.     }
  180.     return 0;
  181. }
Success #stdin #stdout 0s 19928KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/fQzkmo
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!