Ideone.com

fork download

copy

#include <bits/stdc++.h>
#define ll long long
#define INF 1000000005
#define MOD 1000000007
#define EPS 1e-10
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;--i)
#define srep(i,s,t) for(int i=(int)(s);i<(int)(t);++i)
#define each(a,b) for(const auto& (a): (b))
#define all(v) (v).begin(),(v).end()
#define len(v) (int)(v).size()
#define zip(v) sort(all(v)),v.erase(unique(all(v)),v.end())
#define cmx(x,y) x=max(x,y)
#define cmn(x,y) x=min(x,y)
#define fi first
#define se second
#define pb push_back
#define show(x) cout<<#x<<" = "<<(x)<<endl
#define sar(a,n) {cout<<#a<<":";rep(pachico,n)cout<<" "<<a[pachico];cout<<endl;}
 
using namespace std;
 
template<typename S,typename T>auto&operator<<(ostream&o,pair<S,T>p){return o<<"{"<<p.fi<<","<<p.se<<"}";}
template<typename T>auto&operator<<(ostream&o,set<T>s){for(auto&e:s)o<<e<<" ";return o;}
template<typename S,typename T,typename U>
auto&operator<<(ostream&o,priority_queue<S,T,U>q){while(!q.empty())o<<q.top()<<" ",q.pop();return o;}
template<typename K,typename T>auto&operator<<(ostream&o,map<K,T>&m){for(auto&e:m)o<<e<<" ";return o;}
template<typename T>auto&operator<<(ostream&o,vector<T>v){for(auto&e:v)o<<e<<" ";return o;}
void ashow(){cout<<endl;}template<typename T,typename...A>void ashow(T t,A...a){cout<<t<<" ";ashow(a...);}
template<typename S,typename T,typename U>
struct TRI{S fi;T se;U th;TRI(){}TRI(S f,T s,U t):fi(f),se(s),th(t){}
bool operator<(const TRI&_)const{return(fi==_.fi)?((se==_.se)?(th<_.th):(se<_.se)):(fi<_.fi);}};
template<typename S,typename T,typename U>
auto&operator<<(ostream&o,TRI<S,T,U>&t){return o<<"{"<<t.fi<<","<<t.se<<","<<t.th<<"}";}
 
typedef pair<int, int> P;
typedef pair<ll,ll> pll;
typedef TRI<int, int, int> tri;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<P> vp;
typedef vector<string> vs;
 
const int MAX_N = 100005;
 
template<typename _Tp> class node {
public:
    const int key;
    int sum, pmin;
    _Tp data;
    node *left, *right, *par;
    node(const int _key, _Tp&& _data) noexcept
         : key(_key), sum((_data == INF) ? -1 : 1), pmin(min(sum, 0)), data(move(_data)),
		 	 left(nullptr), right(nullptr), par(nullptr){}
    inline bool isRoot() const { return !par; }
    void eval(){
        sum = pmin = 0;
        if(left) sum += left->sum, pmin = min(pmin, left->pmin);
        sum += ((data == INF) ? -1 : 1), pmin = min(pmin, sum);
        if(right){
            pmin = min(pmin, sum + right->pmin), sum += right->sum;
        }
    }
    void rotate(bool right_){
        node<_Tp> *p = par, *g = p->par;
        if(right_){
            if((p->left = right)) right->par = p;
            right = p, p->par = this;
        }else{
            if((p->right = left)) left->par = p;
            left = p, p->par = this;
        }
        p->eval(), eval();
        if(!(par = g)) return;
        if(g->left == p) g->left = this;
        if(g->right == p) g->right = this;
        g->eval();
    }
};
 
template<typename _Tp>
node<_Tp>* splay(node<_Tp>* u) noexcept {
    if(!u) return nullptr;
    while(!(u->isRoot())){
        node<_Tp> *p = u->par, *gp = p->par;
        if(p->isRoot()){
            u->rotate((u == p->left));
        }else{
            bool flag = (u == p->left);
            if((u == p->left) == (p == gp->left)){
                p->rotate(flag), u->rotate(flag);
            }else{
                u->rotate(flag), u->rotate(!flag);
            }
        }
    }
    return u;
}
 
template<typename _Tp>
pair<node<_Tp>*, bool> get(const int _key, node<_Tp>* root){
    node<_Tp> *cur = nullptr, *nx = root, *res = nullptr;
    while(nx){
        cur = nx;
        if(cur->key <= _key) nx = cur->right, res = cur;
        else nx = cur->left;
    }
    node<_Tp>* tmp = splay(cur);
    return res ? make_pair(splay(res), true) : make_pair(tmp, false);
}
 
template<typename _Tp>
node<_Tp>* join(node<_Tp>* root1, node<_Tp>* root2) noexcept {
    if(!root1 || !root2) return root1 ? root1 : root2;
    node<_Tp> *cur = nullptr, *nx = root1;
    while(nx) cur = nx, nx = cur->right;
    node<_Tp>* ver = splay(cur);
    ver->right = root2, ver->eval(), root2->par = ver;
    return ver;
}
 
template<typename _Tp>
node<_Tp>* insert(node<_Tp>* ver, node<_Tp>* root) noexcept {
    if(!root) return ver;
    node<_Tp> *cur = nullptr, *nx = root;
    while(nx){
        cur = nx;
        if(cur->key > ver->key) nx = cur->left;
        else nx = cur->right;
    }
    if(cur->key > ver->key) cur->left = ver, ver->par = cur;
    else cur->right = ver, ver->par = cur;
    cur->eval();
    return splay(ver);
}
 
template<typename _Tp>
node<_Tp> *erase(node<_Tp> *ver){
    ver = splay(ver);
    node<_Tp> *l = ver->left, *r = ver->right;
    if(l) l->par = nullptr;
    if(r) r->par = nullptr;
    delete ver;
    return join(l, r);
}
 
template<typename _Tp> class RetroactiveDeque {
public:
    node<_Tp> *lroot, *rroot;
private:
    int left_pos(const int _time){
        pair<node<_Tp>*, bool> lres = get(_time, lroot);
        lroot = lres.first;
        int l = 0;
        if(lres.second) l = (lroot->left ? lroot->left->sum : 0) + ((lroot->data == INF) ? -1 : 1);
        return l;
    }
    int right_pos(const int _time){
        pair<node<_Tp>*, bool> rres = get(_time, rroot);
        rroot = rres.first;
        int r = 0;
        if(rres.second) r = (rroot->left ? rroot->left->sum : 0) + ((rroot->data == INF) ? -1 : 1);
        return r;
    }
    template<typename Data>
    node<_Tp> *push_front_impl(Data&& data, const int _time){
        _Tp new_data = forward<Data>(data);
        node<_Tp> *new_node = new node<_Tp>(_time, move(new_data));
        lroot = insert(new_node, lroot);
        return new_node;
    }
    node<_Tp> *pop_front_impl(const int _time){
        node<_Tp> *new_node = new node<_Tp>(_time, INF);
        lroot = insert(new_node, lroot);
        return new_node;
    }
    template<typename Data>
    node<_Tp> *push_back_impl(Data&& data, const int _time){
        _Tp new_data = forward<Data>(data);
        node<_Tp> *new_node = new node<_Tp>(_time, move(new_data));
        rroot = insert(new_node, rroot);
        return new_node;
    }
    node<_Tp> *pop_back_impl(const int _time){
        node<_Tp> *new_node = new node<_Tp>(_time, INF);
        rroot = insert(new_node, rroot);
        return new_node;
    }
    pair<node<_Tp>*, bool> find(int index, node<_Tp>* root){
        if(!root) return make_pair(nullptr, false);
        node<_Tp> *cur = root, *nx = root->left, *res = nullptr;
        if(!nx && index == 0) return make_pair(root, true);
        else if(!nx || index < nx->pmin) return make_pair(root, false);
        while(nx){
            cur = nx;
            int cur_sum = (cur->left ? cur->left->sum : 0) + ((cur->data == INF) ? -1 : 1);
            if(cur->right){
                if(cur_sum + cur->right->pmin <= index){
                    nx = cur->right, index -= cur_sum;
                    continue;
                }
            }
            if(cur_sum == index){
                res = cur;
                break;
            }else nx = cur->left;
        }
        node<_Tp> *tmp = splay(cur);
        if(!res) return make_pair(tmp, true);
        cur = splay(res), nx = cur->right;
        assert(nx);
        while(nx) cur = nx, nx = cur->left;
        return make_pair(splay(cur), true);
    }
    _Tp query_impl(int index, const int _time, bool back){
        const int lpos = left_pos(_time), rpos = right_pos(_time);
        // ashow(lpos, rpos);
        if(lpos + rpos == 0) return -1;
        if(back) index = lpos + rpos - 1;
        const int lid = lpos - index, rid = index + 1 - lpos;
        pair<node<_Tp>*, bool> lres = find(lid - 1, lroot);
        pair<node<_Tp>*, bool> rres = find(rid - 1, rroot);
        lroot = lres.first, rroot = rres.first;
        if(lres.second){
            if(rres.second){
                return (lroot->key < rroot->key) ? rroot->data : lroot->data;
            }else{
                return lroot->data;
            }
        }else{
            assert(rres.second);
            return rroot->data;
        }
    }
public:
    RetroactiveDeque() : lroot(nullptr), rroot(nullptr){}
    size_t size(const int _time){ return left_pos(_time) + right_pos(_time); }
    _Tp front(const int _time){ return query_impl(0, _time, false); }
    _Tp back(const int _time){ return query_impl(0, _time, true); }
    node<_Tp> *push_front(const _Tp& value, const int _time){ return push_front_impl(value, _time); }
    node<_Tp> *push_front(_Tp&& value, const int _time){ return push_front_impl(move(value), _time); }
    node<_Tp> *pop_front(const int _time){ return pop_front_impl(_time); }
    node<_Tp> *push_back(const _Tp& value, const int _time){ return push_back_impl(value, _time); }
    node<_Tp> *push_back(_Tp&& value, const int _time){ return push_back_impl(move(value), _time); }
    node<_Tp> *pop_back(const int _time){ return pop_back_impl(_time); }
    _Tp query(const size_t index, const int _time){ return query_impl(index, _time, false); }
};
 
char c[12];
 
int main()
{
    int n, t, x;
	scanf("%d", &n);
    string s;
    unordered_map<int, pair<node<int>*, bool> > ump;
    RetroactiveDeque<int> rd;
    rep(i,n){
		scanf("%d %s", &t, c);
        if(c[0] == '-'){
			pair<node<int>*, bool> res = ump[t];
			if(res.second) rd.lroot = erase(res.first);
			else rd.rroot = erase(res.first);
		}else if(c[0] == '?'){
			printf("%d %d\n", rd.front(t), rd.back(t));
			fflush(stdout);
			continue;
        }else if(c[1] == 'o' && c[4] == 'b'){
            ump[t] = make_pair(rd.pop_back(t), false);
        }else if(c[1] == 'o' && c[4] == 'f'){
            ump[t] = make_pair(rd.pop_front(t), true);
		}else if(c[1] == 'u' && c[5] == 'b'){
			scanf("%d", &x);
            ump[t] = make_pair(rd.push_back(x, t), false);
        }else{
			scanf("%d", &x);
            ump[t] = make_pair(rd.push_front(x, t), true);
        }
		printf("0 0\n");
		fflush(stdout);
    }
    return 0;
}

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CiNkZWZpbmUgbGwgbG9uZyBsb25nCiNkZWZpbmUgSU5GIDEwMDAwMDAwMDUKI2RlZmluZSBNT0QgMTAwMDAwMDAwNwojZGVmaW5lIEVQUyAxZS0xMAojZGVmaW5lIHJlcChpLG4pIGZvcihpbnQgaT0wO2k8KGludCkobik7KytpKQojZGVmaW5lIHJyZXAoaSxuKSBmb3IoaW50IGk9KGludCkobiktMTtpPj0wOy0taSkKI2RlZmluZSBzcmVwKGkscyx0KSBmb3IoaW50IGk9KGludCkocyk7aTwoaW50KSh0KTsrK2kpCiNkZWZpbmUgZWFjaChhLGIpIGZvcihjb25zdCBhdXRvJiAoYSk6IChiKSkKI2RlZmluZSBhbGwodikgKHYpLmJlZ2luKCksKHYpLmVuZCgpCiNkZWZpbmUgbGVuKHYpIChpbnQpKHYpLnNpemUoKQojZGVmaW5lIHppcCh2KSBzb3J0KGFsbCh2KSksdi5lcmFzZSh1bmlxdWUoYWxsKHYpKSx2LmVuZCgpKQojZGVmaW5lIGNteCh4LHkpIHg9bWF4KHgseSkKI2RlZmluZSBjbW4oeCx5KSB4PW1pbih4LHkpCiNkZWZpbmUgZmkgZmlyc3QKI2RlZmluZSBzZSBzZWNvbmQKI2RlZmluZSBwYiBwdXNoX2JhY2sKI2RlZmluZSBzaG93KHgpIGNvdXQ8PCN4PDwiID0gIjw8KHgpPDxlbmRsCiNkZWZpbmUgc2FyKGEsbikge2NvdXQ8PCNhPDwiOiI7cmVwKHBhY2hpY28sbiljb3V0PDwiICI8PGFbcGFjaGljb107Y291dDw8ZW5kbDt9CiAKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKIAp0ZW1wbGF0ZTx0eXBlbmFtZSBTLHR5cGVuYW1lIFQ+YXV0byZvcGVyYXRvcjw8KG9zdHJlYW0mbyxwYWlyPFMsVD5wKXtyZXR1cm4gbzw8InsiPDxwLmZpPDwiLCI8PHAuc2U8PCJ9Ijt9CnRlbXBsYXRlPHR5cGVuYW1lIFQ+YXV0byZvcGVyYXRvcjw8KG9zdHJlYW0mbyxzZXQ8VD5zKXtmb3IoYXV0byZlOnMpbzw8ZTw8IiAiO3JldHVybiBvO30KdGVtcGxhdGU8dHlwZW5hbWUgUyx0eXBlbmFtZSBULHR5cGVuYW1lIFU+CmF1dG8mb3BlcmF0b3I8PChvc3RyZWFtJm8scHJpb3JpdHlfcXVldWU8UyxULFU+cSl7d2hpbGUoIXEuZW1wdHkoKSlvPDxxLnRvcCgpPDwiICIscS5wb3AoKTtyZXR1cm4gbzt9CnRlbXBsYXRlPHR5cGVuYW1lIEssdHlwZW5hbWUgVD5hdXRvJm9wZXJhdG9yPDwob3N0cmVhbSZvLG1hcDxLLFQ+Jm0pe2ZvcihhdXRvJmU6bSlvPDxlPDwiICI7cmV0dXJuIG87fQp0ZW1wbGF0ZTx0eXBlbmFtZSBUPmF1dG8mb3BlcmF0b3I8PChvc3RyZWFtJm8sdmVjdG9yPFQ+dil7Zm9yKGF1dG8mZTp2KW88PGU8PCIgIjtyZXR1cm4gbzt9CnZvaWQgYXNob3coKXtjb3V0PDxlbmRsO310ZW1wbGF0ZTx0eXBlbmFtZSBULHR5cGVuYW1lLi4uQT52b2lkIGFzaG93KFQgdCxBLi4uYSl7Y291dDw8dDw8IiAiO2FzaG93KGEuLi4pO30KdGVtcGxhdGU8dHlwZW5hbWUgUyx0eXBlbmFtZSBULHR5cGVuYW1lIFU+CnN0cnVjdCBUUkl7UyBmaTtUIHNlO1UgdGg7VFJJKCl7fVRSSShTIGYsVCBzLFUgdCk6ZmkoZiksc2UocyksdGgodCl7fQpib29sIG9wZXJhdG9yPChjb25zdCBUUkkmXyljb25zdHtyZXR1cm4oZmk9PV8uZmkpPygoc2U9PV8uc2UpPyh0aDxfLnRoKTooc2U8Xy5zZSkpOihmaTxfLmZpKTt9fTsKdGVtcGxhdGU8dHlwZW5hbWUgUyx0eXBlbmFtZSBULHR5cGVuYW1lIFU+CmF1dG8mb3BlcmF0b3I8PChvc3RyZWFtJm8sVFJJPFMsVCxVPiZ0KXtyZXR1cm4gbzw8InsiPDx0LmZpPDwiLCI8PHQuc2U8PCIsIjw8dC50aDw8In0iO30KIAp0eXBlZGVmIHBhaXI8aW50LCBpbnQ+IFA7CnR5cGVkZWYgcGFpcjxsbCxsbD4gcGxsOwp0eXBlZGVmIFRSSTxpbnQsIGludCwgaW50PiB0cmk7CnR5cGVkZWYgdmVjdG9yPGludD4gdmk7CnR5cGVkZWYgdmVjdG9yPHZpPiB2dmk7CnR5cGVkZWYgdmVjdG9yPGxsPiB2bDsKdHlwZWRlZiB2ZWN0b3I8dmw+IHZ2bDsKdHlwZWRlZiB2ZWN0b3I8ZG91YmxlPiB2ZDsKdHlwZWRlZiB2ZWN0b3I8UD4gdnA7CnR5cGVkZWYgdmVjdG9yPHN0cmluZz4gdnM7CiAKY29uc3QgaW50IE1BWF9OID0gMTAwMDA1OwogCnRlbXBsYXRlPHR5cGVuYW1lIF9UcD4gY2xhc3Mgbm9kZSB7CnB1YmxpYzoKICAgIGNvbnN0IGludCBrZXk7CiAgICBpbnQgc3VtLCBwbWluOwogICAgX1RwIGRhdGE7CiAgICBub2RlICpsZWZ0LCAqcmlnaHQsICpwYXI7CiAgICBub2RlKGNvbnN0IGludCBfa2V5LCBfVHAmJiBfZGF0YSkgbm9leGNlcHQKICAgICAgICAgOiBrZXkoX2tleSksIHN1bSgoX2RhdGEgPT0gSU5GKSA/IC0xIDogMSksIHBtaW4obWluKHN1bSwgMCkpLCBkYXRhKG1vdmUoX2RhdGEpKSwKCQkgCSBsZWZ0KG51bGxwdHIpLCByaWdodChudWxscHRyKSwgcGFyKG51bGxwdHIpe30KICAgIGlubGluZSBib29sIGlzUm9vdCgpIGNvbnN0IHsgcmV0dXJuICFwYXI7IH0KICAgIHZvaWQgZXZhbCgpewogICAgICAgIHN1bSA9IHBtaW4gPSAwOwogICAgICAgIGlmKGxlZnQpIHN1bSArPSBsZWZ0LT5zdW0sIHBtaW4gPSBtaW4ocG1pbiwgbGVmdC0+cG1pbik7CiAgICAgICAgc3VtICs9ICgoZGF0YSA9PSBJTkYpID8gLTEgOiAxKSwgcG1pbiA9IG1pbihwbWluLCBzdW0pOwogICAgICAgIGlmKHJpZ2h0KXsKICAgICAgICAgICAgcG1pbiA9IG1pbihwbWluLCBzdW0gKyByaWdodC0+cG1pbiksIHN1bSArPSByaWdodC0+c3VtOwogICAgICAgIH0KICAgIH0KICAgIHZvaWQgcm90YXRlKGJvb2wgcmlnaHRfKXsKICAgICAgICBub2RlPF9UcD4gKnAgPSBwYXIsICpnID0gcC0+cGFyOwogICAgICAgIGlmKHJpZ2h0Xyl7CiAgICAgICAgICAgIGlmKChwLT5sZWZ0ID0gcmlnaHQpKSByaWdodC0+cGFyID0gcDsKICAgICAgICAgICAgcmlnaHQgPSBwLCBwLT5wYXIgPSB0aGlzOwogICAgICAgIH1lbHNlewogICAgICAgICAgICBpZigocC0+cmlnaHQgPSBsZWZ0KSkgbGVmdC0+cGFyID0gcDsKICAgICAgICAgICAgbGVmdCA9IHAsIHAtPnBhciA9IHRoaXM7CiAgICAgICAgfQogICAgICAgIHAtPmV2YWwoKSwgZXZhbCgpOwogICAgICAgIGlmKCEocGFyID0gZykpIHJldHVybjsKICAgICAgICBpZihnLT5sZWZ0ID09IHApIGctPmxlZnQgPSB0aGlzOwogICAgICAgIGlmKGctPnJpZ2h0ID09IHApIGctPnJpZ2h0ID0gdGhpczsKICAgICAgICBnLT5ldmFsKCk7CiAgICB9Cn07CiAKdGVtcGxhdGU8dHlwZW5hbWUgX1RwPgpub2RlPF9UcD4qIHNwbGF5KG5vZGU8X1RwPiogdSkgbm9leGNlcHQgewogICAgaWYoIXUpIHJldHVybiBudWxscHRyOwogICAgd2hpbGUoISh1LT5pc1Jvb3QoKSkpewogICAgICAgIG5vZGU8X1RwPiAqcCA9IHUtPnBhciwgKmdwID0gcC0+cGFyOwogICAgICAgIGlmKHAtPmlzUm9vdCgpKXsKICAgICAgICAgICAgdS0+cm90YXRlKCh1ID09IHAtPmxlZnQpKTsKICAgICAgICB9ZWxzZXsKICAgICAgICAgICAgYm9vbCBmbGFnID0gKHUgPT0gcC0+bGVmdCk7CiAgICAgICAgICAgIGlmKCh1ID09IHAtPmxlZnQpID09IChwID09IGdwLT5sZWZ0KSl7CiAgICAgICAgICAgICAgICBwLT5yb3RhdGUoZmxhZyksIHUtPnJvdGF0ZShmbGFnKTsKICAgICAgICAgICAgfWVsc2V7CiAgICAgICAgICAgICAgICB1LT5yb3RhdGUoZmxhZyksIHUtPnJvdGF0ZSghZmxhZyk7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICB9CiAgICByZXR1cm4gdTsKfQogCnRlbXBsYXRlPHR5cGVuYW1lIF9UcD4KcGFpcjxub2RlPF9UcD4qLCBib29sPiBnZXQoY29uc3QgaW50IF9rZXksIG5vZGU8X1RwPiogcm9vdCl7CiAgICBub2RlPF9UcD4gKmN1ciA9IG51bGxwdHIsICpueCA9IHJvb3QsICpyZXMgPSBudWxscHRyOwogICAgd2hpbGUobngpewogICAgICAgIGN1ciA9IG54OwogICAgICAgIGlmKGN1ci0+a2V5IDw9IF9rZXkpIG54ID0gY3VyLT5yaWdodCwgcmVzID0gY3VyOwogICAgICAgIGVsc2UgbnggPSBjdXItPmxlZnQ7CiAgICB9CiAgICBub2RlPF9UcD4qIHRtcCA9IHNwbGF5KGN1cik7CiAgICByZXR1cm4gcmVzID8gbWFrZV9wYWlyKHNwbGF5KHJlcyksIHRydWUpIDogbWFrZV9wYWlyKHRtcCwgZmFsc2UpOwp9CiAKdGVtcGxhdGU8dHlwZW5hbWUgX1RwPgpub2RlPF9UcD4qIGpvaW4obm9kZTxfVHA+KiByb290MSwgbm9kZTxfVHA+KiByb290Mikgbm9leGNlcHQgewogICAgaWYoIXJvb3QxIHx8ICFyb290MikgcmV0dXJuIHJvb3QxID8gcm9vdDEgOiByb290MjsKICAgIG5vZGU8X1RwPiAqY3VyID0gbnVsbHB0ciwgKm54ID0gcm9vdDE7CiAgICB3aGlsZShueCkgY3VyID0gbngsIG54ID0gY3VyLT5yaWdodDsKICAgIG5vZGU8X1RwPiogdmVyID0gc3BsYXkoY3VyKTsKICAgIHZlci0+cmlnaHQgPSByb290MiwgdmVyLT5ldmFsKCksIHJvb3QyLT5wYXIgPSB2ZXI7CiAgICByZXR1cm4gdmVyOwp9CiAKdGVtcGxhdGU8dHlwZW5hbWUgX1RwPgpub2RlPF9UcD4qIGluc2VydChub2RlPF9UcD4qIHZlciwgbm9kZTxfVHA+KiByb290KSBub2V4Y2VwdCB7CiAgICBpZighcm9vdCkgcmV0dXJuIHZlcjsKICAgIG5vZGU8X1RwPiAqY3VyID0gbnVsbHB0ciwgKm54ID0gcm9vdDsKICAgIHdoaWxlKG54KXsKICAgICAgICBjdXIgPSBueDsKICAgICAgICBpZihjdXItPmtleSA+IHZlci0+a2V5KSBueCA9IGN1ci0+bGVmdDsKICAgICAgICBlbHNlIG54ID0gY3VyLT5yaWdodDsKICAgIH0KICAgIGlmKGN1ci0+a2V5ID4gdmVyLT5rZXkpIGN1ci0+bGVmdCA9IHZlciwgdmVyLT5wYXIgPSBjdXI7CiAgICBlbHNlIGN1ci0+cmlnaHQgPSB2ZXIsIHZlci0+cGFyID0gY3VyOwogICAgY3VyLT5ldmFsKCk7CiAgICByZXR1cm4gc3BsYXkodmVyKTsKfQogCnRlbXBsYXRlPHR5cGVuYW1lIF9UcD4Kbm9kZTxfVHA+ICplcmFzZShub2RlPF9UcD4gKnZlcil7CiAgICB2ZXIgPSBzcGxheSh2ZXIpOwogICAgbm9kZTxfVHA+ICpsID0gdmVyLT5sZWZ0LCAqciA9IHZlci0+cmlnaHQ7CiAgICBpZihsKSBsLT5wYXIgPSBudWxscHRyOwogICAgaWYocikgci0+cGFyID0gbnVsbHB0cjsKICAgIGRlbGV0ZSB2ZXI7CiAgICByZXR1cm4gam9pbihsLCByKTsKfQogCnRlbXBsYXRlPHR5cGVuYW1lIF9UcD4gY2xhc3MgUmV0cm9hY3RpdmVEZXF1ZSB7CnB1YmxpYzoKICAgIG5vZGU8X1RwPiAqbHJvb3QsICpycm9vdDsKcHJpdmF0ZToKICAgIGludCBsZWZ0X3Bvcyhjb25zdCBpbnQgX3RpbWUpewogICAgICAgIHBhaXI8bm9kZTxfVHA+KiwgYm9vbD4gbHJlcyA9IGdldChfdGltZSwgbHJvb3QpOwogICAgICAgIGxyb290ID0gbHJlcy5maXJzdDsKICAgICAgICBpbnQgbCA9IDA7CiAgICAgICAgaWYobHJlcy5zZWNvbmQpIGwgPSAobHJvb3QtPmxlZnQgPyBscm9vdC0+bGVmdC0+c3VtIDogMCkgKyAoKGxyb290LT5kYXRhID09IElORikgPyAtMSA6IDEpOwogICAgICAgIHJldHVybiBsOwogICAgfQogICAgaW50IHJpZ2h0X3Bvcyhjb25zdCBpbnQgX3RpbWUpewogICAgICAgIHBhaXI8bm9kZTxfVHA+KiwgYm9vbD4gcnJlcyA9IGdldChfdGltZSwgcnJvb3QpOwogICAgICAgIHJyb290ID0gcnJlcy5maXJzdDsKICAgICAgICBpbnQgciA9IDA7CiAgICAgICAgaWYocnJlcy5zZWNvbmQpIHIgPSAocnJvb3QtPmxlZnQgPyBycm9vdC0+bGVmdC0+c3VtIDogMCkgKyAoKHJyb290LT5kYXRhID09IElORikgPyAtMSA6IDEpOwogICAgICAgIHJldHVybiByOwogICAgfQogICAgdGVtcGxhdGU8dHlwZW5hbWUgRGF0YT4KICAgIG5vZGU8X1RwPiAqcHVzaF9mcm9udF9pbXBsKERhdGEmJiBkYXRhLCBjb25zdCBpbnQgX3RpbWUpewogICAgICAgIF9UcCBuZXdfZGF0YSA9IGZvcndhcmQ8RGF0YT4oZGF0YSk7CiAgICAgICAgbm9kZTxfVHA+ICpuZXdfbm9kZSA9IG5ldyBub2RlPF9UcD4oX3RpbWUsIG1vdmUobmV3X2RhdGEpKTsKICAgICAgICBscm9vdCA9IGluc2VydChuZXdfbm9kZSwgbHJvb3QpOwogICAgICAgIHJldHVybiBuZXdfbm9kZTsKICAgIH0KICAgIG5vZGU8X1RwPiAqcG9wX2Zyb250X2ltcGwoY29uc3QgaW50IF90aW1lKXsKICAgICAgICBub2RlPF9UcD4gKm5ld19ub2RlID0gbmV3IG5vZGU8X1RwPihfdGltZSwgSU5GKTsKICAgICAgICBscm9vdCA9IGluc2VydChuZXdfbm9kZSwgbHJvb3QpOwogICAgICAgIHJldHVybiBuZXdfbm9kZTsKICAgIH0KICAgIHRlbXBsYXRlPHR5cGVuYW1lIERhdGE+CiAgICBub2RlPF9UcD4gKnB1c2hfYmFja19pbXBsKERhdGEmJiBkYXRhLCBjb25zdCBpbnQgX3RpbWUpewogICAgICAgIF9UcCBuZXdfZGF0YSA9IGZvcndhcmQ8RGF0YT4oZGF0YSk7CiAgICAgICAgbm9kZTxfVHA+ICpuZXdfbm9kZSA9IG5ldyBub2RlPF9UcD4oX3RpbWUsIG1vdmUobmV3X2RhdGEpKTsKICAgICAgICBycm9vdCA9IGluc2VydChuZXdfbm9kZSwgcnJvb3QpOwogICAgICAgIHJldHVybiBuZXdfbm9kZTsKICAgIH0KICAgIG5vZGU8X1RwPiAqcG9wX2JhY2tfaW1wbChjb25zdCBpbnQgX3RpbWUpewogICAgICAgIG5vZGU8X1RwPiAqbmV3X25vZGUgPSBuZXcgbm9kZTxfVHA+KF90aW1lLCBJTkYpOwogICAgICAgIHJyb290ID0gaW5zZXJ0KG5ld19ub2RlLCBycm9vdCk7CiAgICAgICAgcmV0dXJuIG5ld19ub2RlOwogICAgfQogICAgcGFpcjxub2RlPF9UcD4qLCBib29sPiBmaW5kKGludCBpbmRleCwgbm9kZTxfVHA+KiByb290KXsKICAgICAgICBpZighcm9vdCkgcmV0dXJuIG1ha2VfcGFpcihudWxscHRyLCBmYWxzZSk7CiAgICAgICAgbm9kZTxfVHA+ICpjdXIgPSByb290LCAqbnggPSByb290LT5sZWZ0LCAqcmVzID0gbnVsbHB0cjsKICAgICAgICBpZighbnggJiYgaW5kZXggPT0gMCkgcmV0dXJuIG1ha2VfcGFpcihyb290LCB0cnVlKTsKICAgICAgICBlbHNlIGlmKCFueCB8fCBpbmRleCA8IG54LT5wbWluKSByZXR1cm4gbWFrZV9wYWlyKHJvb3QsIGZhbHNlKTsKICAgICAgICB3aGlsZShueCl7CiAgICAgICAgICAgIGN1ciA9IG54OwogICAgICAgICAgICBpbnQgY3VyX3N1bSA9IChjdXItPmxlZnQgPyBjdXItPmxlZnQtPnN1bSA6IDApICsgKChjdXItPmRhdGEgPT0gSU5GKSA/IC0xIDogMSk7CiAgICAgICAgICAgIGlmKGN1ci0+cmlnaHQpewogICAgICAgICAgICAgICAgaWYoY3VyX3N1bSArIGN1ci0+cmlnaHQtPnBtaW4gPD0gaW5kZXgpewogICAgICAgICAgICAgICAgICAgIG54ID0gY3VyLT5yaWdodCwgaW5kZXggLT0gY3VyX3N1bTsKICAgICAgICAgICAgICAgICAgICBjb250aW51ZTsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgfQogICAgICAgICAgICBpZihjdXJfc3VtID09IGluZGV4KXsKICAgICAgICAgICAgICAgIHJlcyA9IGN1cjsKICAgICAgICAgICAgICAgIGJyZWFrOwogICAgICAgICAgICB9ZWxzZSBueCA9IGN1ci0+bGVmdDsKICAgICAgICB9CiAgICAgICAgbm9kZTxfVHA+ICp0bXAgPSBzcGxheShjdXIpOwogICAgICAgIGlmKCFyZXMpIHJldHVybiBtYWtlX3BhaXIodG1wLCB0cnVlKTsKICAgICAgICBjdXIgPSBzcGxheShyZXMpLCBueCA9IGN1ci0+cmlnaHQ7CiAgICAgICAgYXNzZXJ0KG54KTsKICAgICAgICB3aGlsZShueCkgY3VyID0gbngsIG54ID0gY3VyLT5sZWZ0OwogICAgICAgIHJldHVybiBtYWtlX3BhaXIoc3BsYXkoY3VyKSwgdHJ1ZSk7CiAgICB9CiAgICBfVHAgcXVlcnlfaW1wbChpbnQgaW5kZXgsIGNvbnN0IGludCBfdGltZSwgYm9vbCBiYWNrKXsKICAgICAgICBjb25zdCBpbnQgbHBvcyA9IGxlZnRfcG9zKF90aW1lKSwgcnBvcyA9IHJpZ2h0X3BvcyhfdGltZSk7CiAgICAgICAgLy8gYXNob3cobHBvcywgcnBvcyk7CiAgICAgICAgaWYobHBvcyArIHJwb3MgPT0gMCkgcmV0dXJuIC0xOwogICAgICAgIGlmKGJhY2spIGluZGV4ID0gbHBvcyArIHJwb3MgLSAxOwogICAgICAgIGNvbnN0IGludCBsaWQgPSBscG9zIC0gaW5kZXgsIHJpZCA9IGluZGV4ICsgMSAtIGxwb3M7CiAgICAgICAgcGFpcjxub2RlPF9UcD4qLCBib29sPiBscmVzID0gZmluZChsaWQgLSAxLCBscm9vdCk7CiAgICAgICAgcGFpcjxub2RlPF9UcD4qLCBib29sPiBycmVzID0gZmluZChyaWQgLSAxLCBycm9vdCk7CiAgICAgICAgbHJvb3QgPSBscmVzLmZpcnN0LCBycm9vdCA9IHJyZXMuZmlyc3Q7CiAgICAgICAgaWYobHJlcy5zZWNvbmQpewogICAgICAgICAgICBpZihycmVzLnNlY29uZCl7CiAgICAgICAgICAgICAgICByZXR1cm4gKGxyb290LT5rZXkgPCBycm9vdC0+a2V5KSA/IHJyb290LT5kYXRhIDogbHJvb3QtPmRhdGE7CiAgICAgICAgICAgIH1lbHNlewogICAgICAgICAgICAgICAgcmV0dXJuIGxyb290LT5kYXRhOwogICAgICAgICAgICB9CiAgICAgICAgfWVsc2V7CiAgICAgICAgICAgIGFzc2VydChycmVzLnNlY29uZCk7CiAgICAgICAgICAgIHJldHVybiBycm9vdC0+ZGF0YTsKICAgICAgICB9CiAgICB9CnB1YmxpYzoKICAgIFJldHJvYWN0aXZlRGVxdWUoKSA6IGxyb290KG51bGxwdHIpLCBycm9vdChudWxscHRyKXt9CiAgICBzaXplX3Qgc2l6ZShjb25zdCBpbnQgX3RpbWUpeyByZXR1cm4gbGVmdF9wb3MoX3RpbWUpICsgcmlnaHRfcG9zKF90aW1lKTsgfQogICAgX1RwIGZyb250KGNvbnN0IGludCBfdGltZSl7IHJldHVybiBxdWVyeV9pbXBsKDAsIF90aW1lLCBmYWxzZSk7IH0KICAgIF9UcCBiYWNrKGNvbnN0IGludCBfdGltZSl7IHJldHVybiBxdWVyeV9pbXBsKDAsIF90aW1lLCB0cnVlKTsgfQogICAgbm9kZTxfVHA+ICpwdXNoX2Zyb250KGNvbnN0IF9UcCYgdmFsdWUsIGNvbnN0IGludCBfdGltZSl7IHJldHVybiBwdXNoX2Zyb250X2ltcGwodmFsdWUsIF90aW1lKTsgfQogICAgbm9kZTxfVHA+ICpwdXNoX2Zyb250KF9UcCYmIHZhbHVlLCBjb25zdCBpbnQgX3RpbWUpeyByZXR1cm4gcHVzaF9mcm9udF9pbXBsKG1vdmUodmFsdWUpLCBfdGltZSk7IH0KICAgIG5vZGU8X1RwPiAqcG9wX2Zyb250KGNvbnN0IGludCBfdGltZSl7IHJldHVybiBwb3BfZnJvbnRfaW1wbChfdGltZSk7IH0KICAgIG5vZGU8X1RwPiAqcHVzaF9iYWNrKGNvbnN0IF9UcCYgdmFsdWUsIGNvbnN0IGludCBfdGltZSl7IHJldHVybiBwdXNoX2JhY2tfaW1wbCh2YWx1ZSwgX3RpbWUpOyB9CiAgICBub2RlPF9UcD4gKnB1c2hfYmFjayhfVHAmJiB2YWx1ZSwgY29uc3QgaW50IF90aW1lKXsgcmV0dXJuIHB1c2hfYmFja19pbXBsKG1vdmUodmFsdWUpLCBfdGltZSk7IH0KICAgIG5vZGU8X1RwPiAqcG9wX2JhY2soY29uc3QgaW50IF90aW1lKXsgcmV0dXJuIHBvcF9iYWNrX2ltcGwoX3RpbWUpOyB9CiAgICBfVHAgcXVlcnkoY29uc3Qgc2l6ZV90IGluZGV4LCBjb25zdCBpbnQgX3RpbWUpeyByZXR1cm4gcXVlcnlfaW1wbChpbmRleCwgX3RpbWUsIGZhbHNlKTsgfQp9OwogCmNoYXIgY1sxMl07CgppbnQgbWFpbigpCnsKICAgIGludCBuLCB0LCB4OwoJc2NhbmYoIiVkIiwgJm4pOwogICAgc3RyaW5nIHM7CiAgICB1bm9yZGVyZWRfbWFwPGludCwgcGFpcjxub2RlPGludD4qLCBib29sPiA+IHVtcDsKICAgIFJldHJvYWN0aXZlRGVxdWU8aW50PiByZDsKICAgIHJlcChpLG4pewoJCXNjYW5mKCIlZCAlcyIsICZ0LCBjKTsKICAgICAgICBpZihjWzBdID09ICctJyl7CgkJCXBhaXI8bm9kZTxpbnQ+KiwgYm9vbD4gcmVzID0gdW1wW3RdOwoJCQlpZihyZXMuc2Vjb25kKSByZC5scm9vdCA9IGVyYXNlKHJlcy5maXJzdCk7CgkJCWVsc2UgcmQucnJvb3QgPSBlcmFzZShyZXMuZmlyc3QpOwoJCX1lbHNlIGlmKGNbMF0gPT0gJz8nKXsKCQkJcHJpbnRmKCIlZCAlZFxuIiwgcmQuZnJvbnQodCksIHJkLmJhY2sodCkpOwoJCQlmZmx1c2goc3Rkb3V0KTsKCQkJY29udGludWU7CiAgICAgICAgfWVsc2UgaWYoY1sxXSA9PSAnbycgJiYgY1s0XSA9PSAnYicpewogICAgICAgICAgICB1bXBbdF0gPSBtYWtlX3BhaXIocmQucG9wX2JhY2sodCksIGZhbHNlKTsKICAgICAgICB9ZWxzZSBpZihjWzFdID09ICdvJyAmJiBjWzRdID09ICdmJyl7CiAgICAgICAgICAgIHVtcFt0XSA9IG1ha2VfcGFpcihyZC5wb3BfZnJvbnQodCksIHRydWUpOwoJCX1lbHNlIGlmKGNbMV0gPT0gJ3UnICYmIGNbNV0gPT0gJ2InKXsKCQkJc2NhbmYoIiVkIiwgJngpOwogICAgICAgICAgICB1bXBbdF0gPSBtYWtlX3BhaXIocmQucHVzaF9iYWNrKHgsIHQpLCBmYWxzZSk7CiAgICAgICAgfWVsc2V7CgkJCXNjYW5mKCIlZCIsICZ4KTsKICAgICAgICAgICAgdW1wW3RdID0gbWFrZV9wYWlyKHJkLnB1c2hfZnJvbnQoeCwgdCksIHRydWUpOwogICAgICAgIH0KCQlwcmludGYoIjAgMFxuIik7CgkJZmZsdXNoKHN0ZG91dCk7CiAgICB9CiAgICByZXR1cm4gMDsKfQo=

Success #stdin #stdout 0.02s 4952KB

stdin

copy

Standard input is empty

stdout

copy

https://ideone.com/SfocpO

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