Ideone.com

fork download

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define si(X) scanf("%d", &(X))
#define sll(X) scanf("%lld",&(X))
#define INFL 0x3f3f3f3f3f3f3f3fLL
const ll mod = 1e9 + 7;
 
ll gcd(ll a,ll b){if(b==0)return a;return gcd(b,a%b);}
ll expo(ll base,ll pow){ll ans = 1;
   while(pow!=0){if(pow&1==1){ans = ans*base;ans = ans%mod;}
   base *= base;base%=mod;pow/=2;}return ans;}
ll inv(ll x){return expo(x,mod-2);}
int dx[8] = {1 , 0 , -1 , 0 , 1 , -1 , -1 , 1};    // last 4 diagonal
int dy[8] = {0 , 1 , 0 , -1 , 1 , 1 , -1 , -1};
/*---------------------------------------------------------------------------------------------------------------------*/
 
const int M = 1e5 + 5;
 
ll pref[M], alpha;
set<pair<ll , ll> > se[M];   // distance, timer
/*
contains pairs of (max_distance, timer) of all leaf nodes attched to node i.
*/
 
int N;
int timer = 0;
int now_time[M];
struct Node{
    ll dis;
    int node;
};
Node segTree[4*M];
 
 
void merge(int ind){
    if(segTree[2*ind].dis > segTree[2*ind + 1].dis){
        segTree[ind].dis = segTree[2*ind].dis;
        segTree[ind].node = segTree[2*ind].node;
    }
    else if(segTree[2*ind].dis == segTree[2*ind + 1].dis){
        int u = segTree[2*ind].node;
        int v = segTree[2*ind + 1].node;
        ll u_tim = now_time[u];
        ll v_tim = now_time[v];
 
 
        if(u_tim > v_tim){
            segTree[ind].dis = segTree[2*ind].dis;
            segTree[ind].node = segTree[2*ind].node;
        }
        else{
            segTree[ind].dis = segTree[2*ind + 1].dis;
            segTree[ind].node = segTree[2*ind + 1].node;
        }
    }
    else{
        segTree[ind].dis = segTree[2*ind + 1].dis;
        segTree[ind].node = segTree[2*ind + 1].node;
    }
}
 
void build(int ind , int l , int r){
    if(l > r) return;
    if(l == r){
        segTree[ind].dis = pref[l];
        segTree[ind].node = l;
        return;
    }
    int mid = (l + r)/2;
    build(2*ind , l , mid);
    build(2*ind + 1 , mid + 1 , r);
    merge(ind);
}
 
pair<int , ll> query(int ind , int l , int r , int ql , int qr){
    if(l > r || ql > qr || l > qr || r < ql || ql == 0 || qr == 0) return make_pair(-1 , -1);
 
 
    if(l >= ql && r <= qr){
        return make_pair(segTree[ind].node , segTree[ind].dis);
    }
    int mid = (l + r)/2;
 
    pair<int , ll> p1 = query(2*ind , l , mid , ql , qr);
    pair<int , ll> p2 = query(2*ind + 1 , mid + 1 , r , ql , qr);
 
    if(p1.second > p2.second)  return p1;
    return p2;
}
 
void update(int ind , int l , int r , int point , ll W){
 
    if(l > r || point < l || point > r ) return;
 
    if(l == r){
        segTree[ind].dis += W;
        return;
    }
 
    int mid = (l + r)/2;
    update(2*ind , l , mid , point , W);
    update(2*ind + 1 , mid + 1 , r , point , W);
    merge(ind);
}
 
pair<int , ll> find_farthest(int x){
    // returns pair of the base node and distance
 
 
 
    int max_node = x;
    ll max_dis = -(*se[x].begin()).first;
    pair<int , ll> ans = make_pair(max_node , max_dis);
 
    pair<int , ll> p1 = query(1 , 1 , N , x + 1 , N);
 
    p1.second = p1.second - pref[x];
 
    pair<int , ll> p2 = query(1 , 1 , N , 1 , x - 1);
 
    p2.second = p2.second + alpha - pref[x];
 
    if(x == 1) p2 = p1;
    if(x == N) p1 = p2;
 
    vector<pair<ll , pair<int , int> > > temp;
 
 
    int u = p1.first;  ll u_dis = p1.second;   ll u_tim = now_time[u];
    int v = p2.first;  ll v_dis = p2.second;   ll v_tim = now_time[v];
 
    max_node = u;
    max_dis  = u_dis;
 
    if((u_dis > v_dis) || (u_dis == v_dis && u_tim > v_tim)){
 
    }
    else{
        p1 = p2;
        max_node = v;
        max_dis  = v_dis;
    }
 
    p2 = ans;
 
    v = p2.first;   v_dis = p2.second;    v_tim = now_time[v];
 
    if((u_dis > v_dis) || (u_dis == v_dis && u_tim > v_tim)){
 
    }
    else{
        p1 = p2;
        max_node = v;
        max_dis  = v_dis;
    }
 
 
    ans.first = max_node;
    ans.second = max_dis;
 
    return ans;
}
 
int main(){
 
    si(N);
    //if(N < 10000) cout<<pref[M+M];
    ll el;
    for(int i = 1 ; i <= N ; i++){
        sll(el);
        alpha += el;
        pref[i + 1] = pref[i] + el;
        se[i].insert(make_pair(0 , 0));
    }
    build(1 , 1 , N);
 
    int q;
    si(q);
 
    while(q--){
 
        timer++;
        int typ, x;
        ll w;
        si(typ);  si(x);
 
        if(typ == 1){
            pair<int , ll> P = find_farthest(x);
            int y = P.first;
            ll omega = P.second;
            sll(w);
 
            pair<ll , ll> PX = *(se[y].begin());
            se[y].erase(se[y].begin());
            PX.first -= w;
            PX.second = -timer;
            se[y].insert(PX);
            now_time[y] = -timer;
 
            update(1 , 1 , N , y , w);
 
        }
 
        else if(typ == 2){
            sll(w);
            ll pres = -(*se[x].begin()).first;
            se[x].insert(make_pair(-w , -timer));
 
            if(w >= pres){
                now_time[x] = -timer;
                update(1 , 1 , N , x , w - pres);
            }
        }
 
        else if(typ == 3){
            pair<int , ll> P = find_farthest(x);
            int y = P.first;
            ll omega = P.second;
 
            pair<ll , ll> PX = *(se[y].begin());
            se[y].erase(se[y].begin());
            ll max_dis = -PX.first;
            ll new_max = -(*se[y].begin()).first;
            now_time[y] = -(*se[y].begin()).second;
            update(1 , 1 , N , y , new_max - max_dis);
        }
 
        else{
            pair<int , ll> P = find_farthest(x);
            int y = P.first;
            ll omega = P.second;
            printf("%lld\n" , omega);
        }
    }
 
 
}

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiNkZWZpbmUgbGwgbG9uZyBsb25nCiNkZWZpbmUgdWxsIHVuc2lnbmVkIGxvbmcgbG9uZwojZGVmaW5lIHNpKFgpIHNjYW5mKCIlZCIsICYoWCkpCiNkZWZpbmUgc2xsKFgpIHNjYW5mKCIlbGxkIiwmKFgpKQojZGVmaW5lIElORkwgMHgzZjNmM2YzZjNmM2YzZjNmTEwKY29uc3QgbGwgbW9kID0gMWU5ICsgNzsKCmxsIGdjZChsbCBhLGxsIGIpe2lmKGI9PTApcmV0dXJuIGE7cmV0dXJuIGdjZChiLGElYik7fQpsbCBleHBvKGxsIGJhc2UsbGwgcG93KXtsbCBhbnMgPSAxOwogICB3aGlsZShwb3chPTApe2lmKHBvdyYxPT0xKXthbnMgPSBhbnMqYmFzZTthbnMgPSBhbnMlbW9kO30KICAgYmFzZSAqPSBiYXNlO2Jhc2UlPW1vZDtwb3cvPTI7fXJldHVybiBhbnM7fQpsbCBpbnYobGwgeCl7cmV0dXJuIGV4cG8oeCxtb2QtMik7fQppbnQgZHhbOF0gPSB7MSAsIDAgLCAtMSAsIDAgLCAxICwgLTEgLCAtMSAsIDF9OyAgICAvLyBsYXN0IDQgZGlhZ29uYWwKaW50IGR5WzhdID0gezAgLCAxICwgMCAsIC0xICwgMSAsIDEgLCAtMSAsIC0xfTsKLyotLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0qLwoKY29uc3QgaW50IE0gPSAxZTUgKyA1OwoKbGwgcHJlZltNXSwgYWxwaGE7CnNldDxwYWlyPGxsICwgbGw+ID4gc2VbTV07ICAgLy8gZGlzdGFuY2UsIHRpbWVyCi8qCmNvbnRhaW5zIHBhaXJzIG9mIChtYXhfZGlzdGFuY2UsIHRpbWVyKSBvZiBhbGwgbGVhZiBub2RlcyBhdHRjaGVkIHRvIG5vZGUgaS4KKi8KCmludCBOOwppbnQgdGltZXIgPSAwOwppbnQgbm93X3RpbWVbTV07CnN0cnVjdCBOb2RlewogICAgbGwgZGlzOwogICAgaW50IG5vZGU7Cn07Ck5vZGUgc2VnVHJlZVs0Kk1dOwoKCnZvaWQgbWVyZ2UoaW50IGluZCl7CiAgICBpZihzZWdUcmVlWzIqaW5kXS5kaXMgPiBzZWdUcmVlWzIqaW5kICsgMV0uZGlzKXsKICAgICAgICBzZWdUcmVlW2luZF0uZGlzID0gc2VnVHJlZVsyKmluZF0uZGlzOwogICAgICAgIHNlZ1RyZWVbaW5kXS5ub2RlID0gc2VnVHJlZVsyKmluZF0ubm9kZTsKICAgIH0KICAgIGVsc2UgaWYoc2VnVHJlZVsyKmluZF0uZGlzID09IHNlZ1RyZWVbMippbmQgKyAxXS5kaXMpewogICAgICAgIGludCB1ID0gc2VnVHJlZVsyKmluZF0ubm9kZTsKICAgICAgICBpbnQgdiA9IHNlZ1RyZWVbMippbmQgKyAxXS5ub2RlOwogICAgICAgIGxsIHVfdGltID0gbm93X3RpbWVbdV07CiAgICAgICAgbGwgdl90aW0gPSBub3dfdGltZVt2XTsKICAgICAgICAKICAgICAgICAKICAgICAgICBpZih1X3RpbSA+IHZfdGltKXsKICAgICAgICAgICAgc2VnVHJlZVtpbmRdLmRpcyA9IHNlZ1RyZWVbMippbmRdLmRpczsKICAgICAgICAgICAgc2VnVHJlZVtpbmRdLm5vZGUgPSBzZWdUcmVlWzIqaW5kXS5ub2RlOwogICAgICAgIH0KICAgICAgICBlbHNlewogICAgICAgICAgICBzZWdUcmVlW2luZF0uZGlzID0gc2VnVHJlZVsyKmluZCArIDFdLmRpczsKICAgICAgICAgICAgc2VnVHJlZVtpbmRdLm5vZGUgPSBzZWdUcmVlWzIqaW5kICsgMV0ubm9kZTsKICAgICAgICB9CiAgICB9CiAgICBlbHNlewogICAgICAgIHNlZ1RyZWVbaW5kXS5kaXMgPSBzZWdUcmVlWzIqaW5kICsgMV0uZGlzOwogICAgICAgIHNlZ1RyZWVbaW5kXS5ub2RlID0gc2VnVHJlZVsyKmluZCArIDFdLm5vZGU7CiAgICB9Cn0KCnZvaWQgYnVpbGQoaW50IGluZCAsIGludCBsICwgaW50IHIpewogICAgaWYobCA+IHIpIHJldHVybjsKICAgIGlmKGwgPT0gcil7CiAgICAgICAgc2VnVHJlZVtpbmRdLmRpcyA9IHByZWZbbF07CiAgICAgICAgc2VnVHJlZVtpbmRdLm5vZGUgPSBsOwogICAgICAgIHJldHVybjsKICAgIH0KICAgIGludCBtaWQgPSAobCArIHIpLzI7CiAgICBidWlsZCgyKmluZCAsIGwgLCBtaWQpOwogICAgYnVpbGQoMippbmQgKyAxICwgbWlkICsgMSAsIHIpOwogICAgbWVyZ2UoaW5kKTsKfQoKcGFpcjxpbnQgLCBsbD4gcXVlcnkoaW50IGluZCAsIGludCBsICwgaW50IHIgLCBpbnQgcWwgLCBpbnQgcXIpewogICAgaWYobCA+IHIgfHwgcWwgPiBxciB8fCBsID4gcXIgfHwgciA8IHFsIHx8IHFsID09IDAgfHwgcXIgPT0gMCkgcmV0dXJuIG1ha2VfcGFpcigtMSAsIC0xKTsKICAgIAogICAgCiAgICBpZihsID49IHFsICYmIHIgPD0gcXIpewogICAgICAgIHJldHVybiBtYWtlX3BhaXIoc2VnVHJlZVtpbmRdLm5vZGUgLCBzZWdUcmVlW2luZF0uZGlzKTsKICAgIH0KICAgIGludCBtaWQgPSAobCArIHIpLzI7CiAgICAKICAgIHBhaXI8aW50ICwgbGw+IHAxID0gcXVlcnkoMippbmQgLCBsICwgbWlkICwgcWwgLCBxcik7CiAgICBwYWlyPGludCAsIGxsPiBwMiA9IHF1ZXJ5KDIqaW5kICsgMSAsIG1pZCArIDEgLCByICwgcWwgLCBxcik7CiAgICAKICAgIGlmKHAxLnNlY29uZCA+IHAyLnNlY29uZCkgIHJldHVybiBwMTsKICAgIHJldHVybiBwMjsKfQoKdm9pZCB1cGRhdGUoaW50IGluZCAsIGludCBsICwgaW50IHIgLCBpbnQgcG9pbnQgLCBsbCBXKXsKICAgIAogICAgaWYobCA+IHIgfHwgcG9pbnQgPCBsIHx8IHBvaW50ID4gciApIHJldHVybjsKICAgIAogICAgaWYobCA9PSByKXsKICAgICAgICBzZWdUcmVlW2luZF0uZGlzICs9IFc7CiAgICAgICAgcmV0dXJuOwogICAgfQoKICAgIGludCBtaWQgPSAobCArIHIpLzI7CiAgICB1cGRhdGUoMippbmQgLCBsICwgbWlkICwgcG9pbnQgLCBXKTsKICAgIHVwZGF0ZSgyKmluZCArIDEgLCBtaWQgKyAxICwgciAsIHBvaW50ICwgVyk7CiAgICBtZXJnZShpbmQpOwp9CgpwYWlyPGludCAsIGxsPiBmaW5kX2ZhcnRoZXN0KGludCB4KXsKICAgIC8vIHJldHVybnMgcGFpciBvZiB0aGUgYmFzZSBub2RlIGFuZCBkaXN0YW5jZQogICAgCiAgICAKICAgIAogICAgaW50IG1heF9ub2RlID0geDsKICAgIGxsIG1heF9kaXMgPSAtKCpzZVt4XS5iZWdpbigpKS5maXJzdDsKICAgIHBhaXI8aW50ICwgbGw+IGFucyA9IG1ha2VfcGFpcihtYXhfbm9kZSAsIG1heF9kaXMpOwogICAgCiAgICBwYWlyPGludCAsIGxsPiBwMSA9IHF1ZXJ5KDEgLCAxICwgTiAsIHggKyAxICwgTik7CiAgICAgICAgCiAgICBwMS5zZWNvbmQgPSBwMS5zZWNvbmQgLSBwcmVmW3hdOwogICAgICAgIAogICAgcGFpcjxpbnQgLCBsbD4gcDIgPSBxdWVyeSgxICwgMSAsIE4gLCAxICwgeCAtIDEpOwogICAgICAgIAogICAgcDIuc2Vjb25kID0gcDIuc2Vjb25kICsgYWxwaGEgLSBwcmVmW3hdOwogICAgCiAgICBpZih4ID09IDEpIHAyID0gcDE7CiAgICBpZih4ID09IE4pIHAxID0gcDI7CiAgICAKICAgIHZlY3RvcjxwYWlyPGxsICwgcGFpcjxpbnQgLCBpbnQ+ID4gPiB0ZW1wOwogICAgICAgIAogICAgICAgIAogICAgaW50IHUgPSBwMS5maXJzdDsgIGxsIHVfZGlzID0gcDEuc2Vjb25kOyAgIGxsIHVfdGltID0gbm93X3RpbWVbdV07CiAgICBpbnQgdiA9IHAyLmZpcnN0OyAgbGwgdl9kaXMgPSBwMi5zZWNvbmQ7ICAgbGwgdl90aW0gPSBub3dfdGltZVt2XTsKICAgIAogICAgbWF4X25vZGUgPSB1OwogICAgbWF4X2RpcyAgPSB1X2RpczsKICAgIAogICAgaWYoKHVfZGlzID4gdl9kaXMpIHx8ICh1X2RpcyA9PSB2X2RpcyAmJiB1X3RpbSA+IHZfdGltKSl7CiAgICAgICAgCiAgICB9CiAgICBlbHNlewogICAgICAgIHAxID0gcDI7CiAgICAgICAgbWF4X25vZGUgPSB2OwogICAgICAgIG1heF9kaXMgID0gdl9kaXM7CiAgICB9CiAgICAKICAgIHAyID0gYW5zOwogICAgCiAgICB2ID0gcDIuZmlyc3Q7ICAgdl9kaXMgPSBwMi5zZWNvbmQ7ICAgIHZfdGltID0gbm93X3RpbWVbdl07CiAgICAKICAgIGlmKCh1X2RpcyA+IHZfZGlzKSB8fCAodV9kaXMgPT0gdl9kaXMgJiYgdV90aW0gPiB2X3RpbSkpewogICAgICAgIAogICAgfQogICAgZWxzZXsKICAgICAgICBwMSA9IHAyOwogICAgICAgIG1heF9ub2RlID0gdjsKICAgICAgICBtYXhfZGlzICA9IHZfZGlzOwogICAgfQogICAgCiAgICAKICAgIGFucy5maXJzdCA9IG1heF9ub2RlOwogICAgYW5zLnNlY29uZCA9IG1heF9kaXM7CiAgICAKICAgIHJldHVybiBhbnM7Cn0KCmludCBtYWluKCl7CiAgICAKICAgIHNpKE4pOwogICAgLy9pZihOIDwgMTAwMDApIGNvdXQ8PHByZWZbTStNXTsKICAgIGxsIGVsOwogICAgZm9yKGludCBpID0gMSA7IGkgPD0gTiA7IGkrKyl7CiAgICAgICAgc2xsKGVsKTsKICAgICAgICBhbHBoYSArPSBlbDsKICAgICAgICBwcmVmW2kgKyAxXSA9IHByZWZbaV0gKyBlbDsKICAgICAgICBzZVtpXS5pbnNlcnQobWFrZV9wYWlyKDAgLCAwKSk7CiAgICB9CiAgICBidWlsZCgxICwgMSAsIE4pOwogICAgCiAgICBpbnQgcTsKICAgIHNpKHEpOwogICAKICAgIHdoaWxlKHEtLSl7CiAgICAgICAgCiAgICAgICAgdGltZXIrKzsKICAgICAgICBpbnQgdHlwLCB4OwogICAgICAgIGxsIHc7CiAgICAgICAgc2kodHlwKTsgIHNpKHgpOwogICAgICAgIAogICAgICAgIGlmKHR5cCA9PSAxKXsKICAgICAgICAgICAgcGFpcjxpbnQgLCBsbD4gUCA9IGZpbmRfZmFydGhlc3QoeCk7CiAgICAgICAgICAgIGludCB5ID0gUC5maXJzdDsKICAgICAgICAgICAgbGwgb21lZ2EgPSBQLnNlY29uZDsKICAgICAgICAgICAgc2xsKHcpOwogICAgICAgICAgICAKICAgICAgICAgICAgcGFpcjxsbCAsIGxsPiBQWCA9ICooc2VbeV0uYmVnaW4oKSk7CiAgICAgICAgICAgIHNlW3ldLmVyYXNlKHNlW3ldLmJlZ2luKCkpOwogICAgICAgICAgICBQWC5maXJzdCAtPSB3OwogICAgICAgICAgICBQWC5zZWNvbmQgPSAtdGltZXI7CiAgICAgICAgICAgIHNlW3ldLmluc2VydChQWCk7CiAgICAgICAgICAgIG5vd190aW1lW3ldID0gLXRpbWVyOwogICAgICAgICAgICAKICAgICAgICAgICAgdXBkYXRlKDEgLCAxICwgTiAsIHkgLCB3KTsKICAgICAgICAgICAgCiAgICAgICAgfQogICAgICAgIAogICAgICAgIGVsc2UgaWYodHlwID09IDIpewogICAgICAgICAgICBzbGwodyk7CiAgICAgICAgICAgIGxsIHByZXMgPSAtKCpzZVt4XS5iZWdpbigpKS5maXJzdDsKICAgICAgICAgICAgc2VbeF0uaW5zZXJ0KG1ha2VfcGFpcigtdyAsIC10aW1lcikpOwogICAgICAgICAgICAKICAgICAgICAgICAgaWYodyA+PSBwcmVzKXsKICAgICAgICAgICAgICAgIG5vd190aW1lW3hdID0gLXRpbWVyOwogICAgICAgICAgICAgICAgdXBkYXRlKDEgLCAxICwgTiAsIHggLCB3IC0gcHJlcyk7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgCiAgICAgICAgZWxzZSBpZih0eXAgPT0gMyl7CiAgICAgICAgICAgIHBhaXI8aW50ICwgbGw+IFAgPSBmaW5kX2ZhcnRoZXN0KHgpOwogICAgICAgICAgICBpbnQgeSA9IFAuZmlyc3Q7CiAgICAgICAgICAgIGxsIG9tZWdhID0gUC5zZWNvbmQ7CiAgICAgICAgICAgIAogICAgICAgICAgICBwYWlyPGxsICwgbGw+IFBYID0gKihzZVt5XS5iZWdpbigpKTsKICAgICAgICAgICAgc2VbeV0uZXJhc2Uoc2VbeV0uYmVnaW4oKSk7CiAgICAgICAgICAgIGxsIG1heF9kaXMgPSAtUFguZmlyc3Q7CiAgICAgICAgICAgIGxsIG5ld19tYXggPSAtKCpzZVt5XS5iZWdpbigpKS5maXJzdDsKICAgICAgICAgICAgbm93X3RpbWVbeV0gPSAtKCpzZVt5XS5iZWdpbigpKS5zZWNvbmQ7CiAgICAgICAgICAgIHVwZGF0ZSgxICwgMSAsIE4gLCB5ICwgbmV3X21heCAtIG1heF9kaXMpOwogICAgICAgIH0KICAgICAgICAKICAgICAgICBlbHNlewogICAgICAgICAgICBwYWlyPGludCAsIGxsPiBQID0gZmluZF9mYXJ0aGVzdCh4KTsKICAgICAgICAgICAgaW50IHkgPSBQLmZpcnN0OwogICAgICAgICAgICBsbCBvbWVnYSA9IFAuc2Vjb25kOwogICAgICAgICAgICBwcmludGYoIiVsbGRcbiIgLCBvbWVnYSk7CiAgICAgICAgfQogICAgfQoJCiAgICAKfQ==

Success #stdin #stdout 0.02s 7808KB

stdin

Standard input is empty

stdout

https://ideone.com/1Z3glS

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