fork download
copy 
  1. #include <iostream>
  2. #include <iomanip>
  3. #include <algorithm>
  4. #include <sstream>
  5. #include <string>
  6. #include <cmath>
  7. #include <vector>
  8. #include <set>
  9. #include <functional>
  10. #include <map>
  11. #include <stack>
  12. #include <climits>
  13. #include <bitset>
  14. #include <numeric>
  15. using namespace std;
  16. #define fast cin.tie(nullptr);cout.tie(nullptr);ios_base::sync_with_stdio(false);
  17. using ll = long long;
  18. using str = string;
  19.  
  20.  
  21.  
  22.  
  23. ll l_r[100000] = { 0 };
  24. ll r_r[100000] = { 0 };
  25. ll b_r[100000] = { 0 };
  26.  
  27.  
  28.  
  29.  
  30.  
  31.  
  32. int main() {
  33.     fast
  34.  
  35.  
  36.         str s;
  37.             cin >> s;
  38.             for (int i = 0; i < s.size(); i++) {
  39.                 if (s[i] == '\\') {
  40.                     r_r[i + 1] = 1;
  41.                 }
  42.                 else  if (s[i] == '/') {
  43.                     l_r[i + 1] = 1;
  44.                 }
  45.                 else  if (s[i] == '_') {
  46.                     b_r[i + 1] = 1;
  47.                 }
  48.             }
  49.             for (int i = 1; i < s.size(); i++) {
  50.                 l_r[i] += l_r[i - 1];
  51.                 r_r[i] += r_r[i - 1];
  52.                 b_r[i] += b_r[i - 1];
  53.             }
  54.             ll ro[100000] = { 0 };
  55.             ll b[100000] = { 0 };
  56.             for (int i = 1; i < 100000; i++) {
  57.                 ro[i] = i;
  58.                 b[i] = i - 1;
  59.             }
  60.             for (int i = 1; i < 100000; i++) {
  61.                 ro[i] += ro[i-1];
  62.                 b[i] += b[i - 1];
  63.             }
  64.  
  65.             int q;
  66.             cin >> q;
  67.  
  68.             while (q--) {
  69.                 int l, r;
  70.                 cin >> l >> r;
  71.                 ll mn_r = min(ro[l - 1] - ro[l - 2], ro[r - 1] - ro[r - 2]);
  72.                 ll ba_n = min(b_r[r], b_r[l - 1]);
  73.                 int re1 = (upper_bound(ro, ro + 100000, mn_r) - ro) - 1;
  74.                 int re2 = (upper_bound(b, b + 100000, ba_n) - b) - 1;
  75.                 cout << min(re1, re2) << endl;
  76.             }
  77.  
  78.  
  79.  
  80.  
  81.  
  82.  
  83.  
  84.  
  85.  
  86.  
  87.  
  88.  
  89.  
  90.  
  91.  
  92.  
  93.  
  94.  
  95.  
  96.  
  97.  
  98.  
  99.  
  100.  
  101.  
  102.  
  103.     return 0;
  104. }
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/yPlhI4
language:
C++14 (gcc 8.3)
created:
10 hours 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!