Ideone.com

fork download

copy

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
 
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <iomanip>
#include <cstdlib>
#include <numeric>
#include <cstdio>
#include <vector>
#include <bitset>
#include <deque>
#include <queue>
#include <cmath>
#include <ctime>
#include <set>
#include <map>
 
using namespace std;
 
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define hashmap unordered_map
#define hashset unordered_set
#define heap priority_queue
#define MS(x, v, n) memset((x), (v), sizeof((x)[0]) * (n))
#define sz(x) int((x).size())
#define all(x) (x).begin(),  (x).end()
#define rall(x) (x).rbegin(), (x).rend()
 
typedef double db;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef unsigned long long ull;
 
void file(const string FILE = "Test")
{
    freopen((FILE + ".INP").c_str(), "r", stdin);
    freopen((FILE + ".ERR").c_str(), "w", stderr);
    freopen((FILE + ".OUT").c_str(), "w", stdout);
}
 
template<typename T> bool maxoreq(T &res, const T &val) { if (res <= val) { res = val; return true; } return false; }
template<typename T> bool minoreq(T &res, const T &val) { if (res >= val) { res = val; return true; } return false; }
template<typename T> bool maximize(T &res, const T &val) { if (res < val) { res = val; return true; } return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val) { res = val; return true; } return false; }
 
const int mvx[] = {0, +1, +0, -0, -1, +1, +1, -1, -1, 0};
const int mvy[] = {0, +0, +1, -1, -0, +1, -1, -1, +1, 0};
 
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====
 
const db EPS = 1e-9;
const db PI = acos(-1);
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int INF = 0x3f3f3f3f;
const int MOD = 1000000007;
const int LIM = 1e6 + 16;
 
struct Node
{
    int length;
    int open;
    int close;
    Node (int length = 0, int open = 0, int close = 0)
    : length(length), open(open), close(close) {}
 
    friend istream &operator >> (istream &cin, Node &a)
    {
        cin >> a.length >> a.open >> a.close;
        return cin;
    }
 
    friend ostream &operator << (ostream &cout, const Node &a)
    {
        cout << a.length << " " << a.open << " " << a.close;
        return cout;
    }
};
 
Node operator + (const Node &a, const Node &b)
{
    int extra = min(a.open, b.close);
 
    Node c;
    c.length = a.length + b.length + extra;
    c.open   = a.open   + b.open   - extra;
    c.close  = a.close  + b.close  - extra;
    return c;
}
 
struct Segtree
{
    int n;
    vector<Node> t;
 
    void init(int lim)
    {
        for (n = 1; n < lim; n <<= 1);
        t.assign(n << 1, Node());
    }
 
    void modify(int p, char c, int ct, int lt, int rt)
    {
        if (rt - lt == 1)
        {
            t[ct] = (c == '(') ? Node(0, 1, 0) : Node(0, 0, 1);
            return ;
        }
 
        int mt = (lt + rt) >> 1;
        if (mt > p)
            modify(p, c, ct * 2 + 1, lt, mt);
        else
            modify(p, c, ct * 2 + 2, mt, rt);
 
        t[ct] = t[ct * 2 + 1] + t[ct * 2 + 2];
    }
 
    void modify(int p, char c)
    {
        return modify(p, c, 0, 0, n);
    }
 
    Node query(int l, int r, int ct, int lt, int rt)
    {
        if (lt >= r || l >= rt) return Node();
        if (lt >= l && r >= rt) return t[ct];
 
        int mt = (lt + rt) >> 1;
        Node lv = query(l, r, ct * 2 + 1, lt, mt);
        Node rv = query(l, r, ct * 2 + 2, mt, rt);
        return lv + rv;
    }
 
    Node query(int l, int r)
    {
        return query(l, r + 1, 0, 0, n);
    }
};
 
int main()
{
//    file("Test");
    ios::sync_with_stdio(NULL);
    cin.tie(NULL);
 
    string s;
    cin >> s;
 
    int n = s.size();
    Segtree S;
    S.init(n + 1);
 
    for (int i = 1; i <= n; ++i)
        S.modify(i, s[i - 1]);
 
    int q;
    cin >> q;
 
    while (q-->0)
    {
        int l, r;
        cin >> l >> r;
        cout << 2 * S.query(l, r).length << "\n";
    }
 
    return 0;
}

Ly8gI3ByYWdtYSBHQ0Mgb3B0aW1pemUoIk8zLHVucm9sbC1sb29wcyIpCi8vICNwcmFnbWEgR0NDIHRhcmdldCgiYXZ4MixibWksYm1pMixsemNudCxwb3BjbnQiKQoKI2luY2x1ZGUgPHVub3JkZXJlZF9tYXA+CiNpbmNsdWRlIDx1bm9yZGVyZWRfc2V0PgojaW5jbHVkZSA8YWxnb3JpdGhtPgojaW5jbHVkZSA8aW9zdHJlYW0+CiNpbmNsdWRlIDxjc3RyaW5nPgojaW5jbHVkZSA8aW9tYW5pcD4KI2luY2x1ZGUgPGNzdGRsaWI+CiNpbmNsdWRlIDxudW1lcmljPgojaW5jbHVkZSA8Y3N0ZGlvPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8Yml0c2V0PgojaW5jbHVkZSA8ZGVxdWU+CiNpbmNsdWRlIDxxdWV1ZT4KI2luY2x1ZGUgPGNtYXRoPgojaW5jbHVkZSA8Y3RpbWU+CiNpbmNsdWRlIDxzZXQ+CiNpbmNsdWRlIDxtYXA+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKI2RlZmluZSBmaSBmaXJzdAojZGVmaW5lIHNlIHNlY29uZAojZGVmaW5lIHBiIHB1c2hfYmFjawojZGVmaW5lIG1wIG1ha2VfcGFpcgojZGVmaW5lIGhhc2htYXAgdW5vcmRlcmVkX21hcAojZGVmaW5lIGhhc2hzZXQgdW5vcmRlcmVkX3NldAojZGVmaW5lIGhlYXAgcHJpb3JpdHlfcXVldWUKI2RlZmluZSBNUyh4LCB2LCBuKSBtZW1zZXQoKHgpLCAodiksIHNpemVvZigoeClbMF0pICogKG4pKQojZGVmaW5lIHN6KHgpIGludCgoeCkuc2l6ZSgpKQojZGVmaW5lIGFsbCh4KSAoeCkuYmVnaW4oKSwgICh4KS5lbmQoKQojZGVmaW5lIHJhbGwoeCkgKHgpLnJiZWdpbigpLCAoeCkucmVuZCgpCgp0eXBlZGVmIGRvdWJsZSBkYjsKdHlwZWRlZiBsb25nIGxvbmcgbGw7CnR5cGVkZWYgbG9uZyBkb3VibGUgbGQ7CnR5cGVkZWYgcGFpcjxpbnQsIGludD4gaWk7CnR5cGVkZWYgdW5zaWduZWQgbG9uZyBsb25nIHVsbDsKCnZvaWQgZmlsZShjb25zdCBzdHJpbmcgRklMRSA9ICJUZXN0IikKewogICAgZnJlb3BlbigoRklMRSArICIuSU5QIikuY19zdHIoKSwgInIiLCBzdGRpbik7CiAgICBmcmVvcGVuKChGSUxFICsgIi5FUlIiKS5jX3N0cigpLCAidyIsIHN0ZGVycik7CiAgICBmcmVvcGVuKChGSUxFICsgIi5PVVQiKS5jX3N0cigpLCAidyIsIHN0ZG91dCk7Cn0KCnRlbXBsYXRlPHR5cGVuYW1lIFQ+IGJvb2wgbWF4b3JlcShUICZyZXMsIGNvbnN0IFQgJnZhbCkgeyBpZiAocmVzIDw9IHZhbCkgeyByZXMgPSB2YWw7IHJldHVybiB0cnVlOyB9IHJldHVybiBmYWxzZTsgfQp0ZW1wbGF0ZTx0eXBlbmFtZSBUPiBib29sIG1pbm9yZXEoVCAmcmVzLCBjb25zdCBUICZ2YWwpIHsgaWYgKHJlcyA+PSB2YWwpIHsgcmVzID0gdmFsOyByZXR1cm4gdHJ1ZTsgfSByZXR1cm4gZmFsc2U7IH0KdGVtcGxhdGU8dHlwZW5hbWUgVD4gYm9vbCBtYXhpbWl6ZShUICZyZXMsIGNvbnN0IFQgJnZhbCkgeyBpZiAocmVzIDwgdmFsKSB7IHJlcyA9IHZhbDsgcmV0dXJuIHRydWU7IH0gcmV0dXJuIGZhbHNlOyB9CnRlbXBsYXRlPHR5cGVuYW1lIFQ+IGJvb2wgbWluaW1pemUoVCAmcmVzLCBjb25zdCBUICZ2YWwpIHsgaWYgKHJlcyA+IHZhbCkgeyByZXMgPSB2YWw7IHJldHVybiB0cnVlOyB9IHJldHVybiBmYWxzZTsgfQoKY29uc3QgaW50IG12eFtdID0gezAsICsxLCArMCwgLTAsIC0xLCArMSwgKzEsIC0xLCAtMSwgMH07CmNvbnN0IGludCBtdnlbXSA9IHswLCArMCwgKzEsIC0xLCAtMCwgKzEsIC0xLCAtMSwgKzEsIDB9OwoKLy8vID09PT0qPT09PSo9PT09Kj09PT0qPT09PSo9PT09Kj09PT0qPT09PSo9PT09Kj09PT0qPT09PSo9PT09Kj09PT0qPT09PSo9PT09Kj09PT0qPT09PQoKY29uc3QgZGIgRVBTID0gMWUtOTsKY29uc3QgZGIgUEkgPSBhY29zKC0xKTsKY29uc3QgbGwgTElORiA9IDB4M2YzZjNmM2YzZjNmM2YzZjsKY29uc3QgaW50IElORiA9IDB4M2YzZjNmM2Y7CmNvbnN0IGludCBNT0QgPSAxMDAwMDAwMDA3Owpjb25zdCBpbnQgTElNID0gMWU2ICsgMTY7CgpzdHJ1Y3QgTm9kZQp7CiAgICBpbnQgbGVuZ3RoOwogICAgaW50IG9wZW47CiAgICBpbnQgY2xvc2U7CiAgICBOb2RlIChpbnQgbGVuZ3RoID0gMCwgaW50IG9wZW4gPSAwLCBpbnQgY2xvc2UgPSAwKQogICAgOiBsZW5ndGgobGVuZ3RoKSwgb3BlbihvcGVuKSwgY2xvc2UoY2xvc2UpIHt9CgogICAgZnJpZW5kIGlzdHJlYW0gJm9wZXJhdG9yID4+IChpc3RyZWFtICZjaW4sIE5vZGUgJmEpCiAgICB7CiAgICAgICAgY2luID4+IGEubGVuZ3RoID4+IGEub3BlbiA+PiBhLmNsb3NlOwogICAgICAgIHJldHVybiBjaW47CiAgICB9CgogICAgZnJpZW5kIG9zdHJlYW0gJm9wZXJhdG9yIDw8IChvc3RyZWFtICZjb3V0LCBjb25zdCBOb2RlICZhKQogICAgewogICAgICAgIGNvdXQgPDwgYS5sZW5ndGggPDwgIiAiIDw8IGEub3BlbiA8PCAiICIgPDwgYS5jbG9zZTsKICAgICAgICByZXR1cm4gY291dDsKICAgIH0KfTsKCk5vZGUgb3BlcmF0b3IgKyAoY29uc3QgTm9kZSAmYSwgY29uc3QgTm9kZSAmYikKewogICAgaW50IGV4dHJhID0gbWluKGEub3BlbiwgYi5jbG9zZSk7CgogICAgTm9kZSBjOwogICAgYy5sZW5ndGggPSBhLmxlbmd0aCArIGIubGVuZ3RoICsgZXh0cmE7CiAgICBjLm9wZW4gICA9IGEub3BlbiAgICsgYi5vcGVuICAgLSBleHRyYTsKICAgIGMuY2xvc2UgID0gYS5jbG9zZSAgKyBiLmNsb3NlICAtIGV4dHJhOwogICAgcmV0dXJuIGM7Cn0KCnN0cnVjdCBTZWd0cmVlCnsKICAgIGludCBuOwogICAgdmVjdG9yPE5vZGU+IHQ7CgogICAgdm9pZCBpbml0KGludCBsaW0pCiAgICB7CiAgICAgICAgZm9yIChuID0gMTsgbiA8IGxpbTsgbiA8PD0gMSk7CiAgICAgICAgdC5hc3NpZ24obiA8PCAxLCBOb2RlKCkpOwogICAgfQoKICAgIHZvaWQgbW9kaWZ5KGludCBwLCBjaGFyIGMsIGludCBjdCwgaW50IGx0LCBpbnQgcnQpCiAgICB7CiAgICAgICAgaWYgKHJ0IC0gbHQgPT0gMSkKICAgICAgICB7CiAgICAgICAgICAgIHRbY3RdID0gKGMgPT0gJygnKSA/IE5vZGUoMCwgMSwgMCkgOiBOb2RlKDAsIDAsIDEpOwogICAgICAgICAgICByZXR1cm4gOwogICAgICAgIH0KCiAgICAgICAgaW50IG10ID0gKGx0ICsgcnQpID4+IDE7CiAgICAgICAgaWYgKG10ID4gcCkKICAgICAgICAgICAgbW9kaWZ5KHAsIGMsIGN0ICogMiArIDEsIGx0LCBtdCk7CiAgICAgICAgZWxzZQogICAgICAgICAgICBtb2RpZnkocCwgYywgY3QgKiAyICsgMiwgbXQsIHJ0KTsKCiAgICAgICAgdFtjdF0gPSB0W2N0ICogMiArIDFdICsgdFtjdCAqIDIgKyAyXTsKICAgIH0KCiAgICB2b2lkIG1vZGlmeShpbnQgcCwgY2hhciBjKQogICAgewogICAgICAgIHJldHVybiBtb2RpZnkocCwgYywgMCwgMCwgbik7CiAgICB9CgogICAgTm9kZSBxdWVyeShpbnQgbCwgaW50IHIsIGludCBjdCwgaW50IGx0LCBpbnQgcnQpCiAgICB7CiAgICAgICAgaWYgKGx0ID49IHIgfHwgbCA+PSBydCkgcmV0dXJuIE5vZGUoKTsKICAgICAgICBpZiAobHQgPj0gbCAmJiByID49IHJ0KSByZXR1cm4gdFtjdF07CgogICAgICAgIGludCBtdCA9IChsdCArIHJ0KSA+PiAxOwogICAgICAgIE5vZGUgbHYgPSBxdWVyeShsLCByLCBjdCAqIDIgKyAxLCBsdCwgbXQpOwogICAgICAgIE5vZGUgcnYgPSBxdWVyeShsLCByLCBjdCAqIDIgKyAyLCBtdCwgcnQpOwogICAgICAgIHJldHVybiBsdiArIHJ2OwogICAgfQoKICAgIE5vZGUgcXVlcnkoaW50IGwsIGludCByKQogICAgewogICAgICAgIHJldHVybiBxdWVyeShsLCByICsgMSwgMCwgMCwgbik7CiAgICB9Cn07CgppbnQgbWFpbigpCnsKLy8gICAgZmlsZSgiVGVzdCIpOwogICAgaW9zOjpzeW5jX3dpdGhfc3RkaW8oTlVMTCk7CiAgICBjaW4udGllKE5VTEwpOwoKICAgIHN0cmluZyBzOwogICAgY2luID4+IHM7CgogICAgaW50IG4gPSBzLnNpemUoKTsKICAgIFNlZ3RyZWUgUzsKICAgIFMuaW5pdChuICsgMSk7CgogICAgZm9yIChpbnQgaSA9IDE7IGkgPD0gbjsgKytpKQogICAgICAgIFMubW9kaWZ5KGksIHNbaSAtIDFdKTsKCiAgICBpbnQgcTsKICAgIGNpbiA+PiBxOwoKICAgIHdoaWxlIChxLS0+MCkKICAgIHsKICAgICAgICBpbnQgbCwgcjsKICAgICAgICBjaW4gPj4gbCA+PiByOwogICAgICAgIGNvdXQgPDwgMiAqIFMucXVlcnkobCwgcikubGVuZ3RoIDw8ICJcbiI7CiAgICB9CgogICAgcmV0dXJuIDA7Cn0K

Success #stdin #stdout 0.01s 5396KB

stdin

copy

Standard input is empty

stdout

copy

https://ideone.com/ugW0DN

language:

C++14 (gcc 8.3)

created:

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!

Discover > Sphere Engine API

Discover > IDE Widget

Choose your language