fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define fi first
  3. #define se second
  4. #define all(v) v.begin() , v.end()
  5. #define sz(v) int(v.size())
  6. #define unq(v) sort(all(v)); v.resize(unique(all(v)) - v.begin());
  7. using namespace std;
  8.  
  9. typedef long long ll;
  10. typedef pair<int , int> ii;
  11. typedef pair<long long , int> lli;
  12.  
  13. const int maxN = int(2e6)+7;
  14.  
  15. int n , m , sum[maxN] , l[maxN] , r[maxN] , t[maxN] , res[maxN];
  16. string s;
  17.  
  18. void update(int x){
  19.     for (; x <= n ; x += x&-x) t[x]++;
  20. }
  21.  
  22. int get(int x){
  23.     int ans = 0;
  24.     for (; x >= 1 ; x -= x&-x) ans += t[x];
  25.     return ans;
  26. }
  27.  
  28. void TH1(){
  29.     for (int i = 1 ; i <= n ; i++) t[i] = 0;
  30.     vector<ii> event , query;
  31.     for (int i = 1 ; i <= n ; i++){
  32.         sum[i] = sum[i - 1];
  33.         if (s[i] == '+') sum[i]++; else sum[i]--;
  34.         event.push_back({sum[i] , i});
  35.     }
  36.     sort(all(event)); reverse(all(event));
  37.     for (int i = 1 ; i <= m ; i++){
  38.         if (l[i] <= r[i]) query.push_back({sum[l[i] - 1] , i});
  39.     }
  40.     sort(all(query)); reverse(all(query));
  41.     for (int i = 0 , j = -1 ; i < sz(query) ; i++){
  42.         while (j + 1 < sz(event) && event[j + 1].fi > query[i].fi){
  43.             j++;
  44.             update(event[j].se);
  45.         }
  46.         int id = query[i].se;
  47.         res[id] = get(r[id]) - get(l[id] - 1);
  48.     }
  49. }
  50.  
  51. void TH2(){
  52.     for (int i = 1 ; i <= n ; i++) t[i] = 0;
  53.     for (int i = 1 ; i <= n / 2 ; i++){
  54.         swap(s[i] , s[n - i + 1]);
  55.     }
  56.     vector<ii> event , query;
  57.     sum[0] = 0;
  58.     for (int i = 1 ; i <= n ; i++){
  59.         sum[i] = sum[i - 1];
  60.         if (s[i] == '+') sum[i]++; else sum[i]--;
  61.         event.push_back({sum[i] , i});
  62.     }
  63.     sort(all(event)); reverse(all(event));
  64.     for (int i = 1 ; i <= m ; i++){
  65.         if (l[i] > r[i]){
  66.             l[i] = n - l[i] + 1;
  67.             r[i] = n - r[i] + 1;
  68.             query.push_back({sum[l[i] - 1] , i});
  69.         }
  70.     }
  71.     sort(all(query)); reverse(all(query));
  72.     for (int i = 0 , j = -1 ; i < sz(query) ; i++){
  73.         while (j + 1 < sz(event) && event[j + 1].fi > query[i].fi){
  74.             j++;
  75.             update(event[j].se);
  76.         }
  77.         int id = query[i].se;
  78.         res[id] = get(r[id]) - get(l[id] - 1);
  79.     }
  80. }
  81.  
  82. void solve(){
  83.     cin >> n >> m >> s;
  84.     s = '#' + s;
  85.     for (int i = 1 ; i <= m ; i++) cin >> l[i] >> r[i];
  86.     TH1();
  87.     TH2();
  88.     for (int i = 1 ; i <= m ; i++){
  89.         cout << res[i] << "\n";
  90.     }
  91. }
  92.  
  93. #define name "A"
  94.  
  95. int main(){
  96.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  97.     if (fopen(name".INP" , "r")){
  98.         freopen(name".INP" , "r" , stdin);
  99.         freopen(name".OUT" , "w" , stdout);
  100.     }
  101.     int t = 1; //cin >> t;
  102.     while (t--) solve();
  103.     return 0;
  104. }
  105.  
Success #stdin #stdout 0s 5660KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/BbYzVq
language:
C++14 (gcc 8.3)
created:
6 days 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!