Submission #877327

#	Time	Username	Problem	Language	Result	Execution time	Memory
877327		vjudge1	Fish 2 (JOI22_fish2)	C++17	8 / 100	4030 ms	284880 KiB

fish2

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 1;
typedef long long ll;
#define int long long
int n,a[N],x[N],y[N];
ll pref[N],sf[N];
mt19937 rng(252351);
struct node{
    node *l = 0,*r = 0;
    int sz,val,mn,mx,prior,pos;
    node(int k,int p):pos(p),sz(1),val(k),mn(k),mx(k),prior(rng()){}
};
using pnode = node *;
int sz(pnode x){
    return (x ? x->sz : 0);
}
int mn(pnode x){
    return (x ? x->mn : 1e18);
}
int mx(pnode x){
    return (x ? x->mx : 0);
}
void upd(pnode &a){
    a->sz = sz(a->l) + sz(a->r) + 1;
    a->mx = max({mx(a->l),mx(a->r),a->val});
    a->mn = min({mn(a->l),mn(a->r),a->val});
}
pnode merge(pnode a,pnode b){
    if(!a) return b;
    if(!b) return a;
    if(a->prior > b->prior){
        a->r = merge(a->r,b);
        upd(a);
        return a;
    }else{
        b->l = merge(a,b->l);
        upd(b);
        return b;
    }
}
pair<pnode,pnode> split(pnode x,int k){
    if(!x) return {0,0};
    if(sz(x->l) >= k){
        auto [l,r] = split(x->l,k);
        x->l = r;
        upd(x);
        return {l,x};
    }else{
        auto [l,r] = split(x->r,k - sz(x->l) - 1);
        x->r = l;
        upd(x);
        return {x,r};
    }
}
pnode t = NULL,g = NULL;

int f_l(pnode cur,int val){
    if(mn(cur) >= val) return n;
    if(cur->l && mn(cur->l) < val){
        return f_l(cur->l,val);
    }
    if(cur->val < val) return (cur->pos);
    return f_l(cur->r,val);
}
int find_less(pnode cur,int l,int r,int val){
    auto [l1,r1] = split(cur,l - 1);
    auto [l2,r2] = split(r1,r); 
    int res = f_l(l2,val);
    cur = merge(l1,merge(l2,r2));
    return res;
}
int f_r(pnode cur,int val){
    if(mx(cur) <= val) return 1;
    if(cur->r && mx(cur->r) > val){
        return f_r(cur->r,val);
    }
    if(cur->val > val) return cur->pos;
    return f_r(cur->l,val);
}
int find_more(pnode cur,int l,int r,int val){
    auto [l1,r1] = split(cur,l - 1);
    auto [l2,r2] = split(r1,r); 
    int res = f_r(l2,val);
    cur = merge(l1,merge(l2,r2));
    return res;
}
void build(){
    t = g = NULL;
    for(int i = 1;i <= n;i++){
        pref[i] = pref[i - 1] + a[i];
    }
    for(int i = 1;i <= n;i++){
        t = merge(t,new node(pref[i] - a[i + 1],i));
        g = merge(g,new node(a[i - 1] + pref[i - 1],i));
    }
    for(int i = 1;i <= n;i++){
        x[i] = i;
        y[i] = i;
        ll sum = a[i];
        while(x[i] != 1 || y[i] != n){
            sum = pref[y[i]] - pref[x[i] - 1];
            // cout << x[i] << ' ' << y[i] << '\n';
            int val = find_less(t,y[i],n,pref[y[i]] - sum);
            if(val != y[i]){
                y[i] = val;
                continue;
            }else{
                int val1 = find_more(g,1,x[i],sum + pref[x[i] - 1]);
                if(val1 == x[i]) break;
                x[i] = val1;
            }
        }
    }
}
void test(){
    cin >> n;
    for(int i = 1;i <= n;i++){
        cin >> a[i];
        pref[i] = pref[i - 1] + a[i];
    }
    int q;
    cin >> q;
    build();
    while(q--){
        int tp,l,r;
        cin >> tp >> l >> r;
        if(tp == 1){
            a[l] = r;
            build();
            continue;
        }
        int res = 0;
        for(int j = l;j <= r;j++){
            if(x[j] <= l && y[j] >= r) res++;
        }
        cout << res << '\n';
    }
}
main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    test();
}

Compilation message (stderr)

fish2.cpp: In constructor 'node::node(long long int, long long int)':
fish2.cpp:11:28: warning: 'node::pos' will be initialized after [-Wreorder]
   11 |     int sz,val,mn,mx,prior,pos;
      |                            ^~~
fish2.cpp:11:9: warning:   'long long int node::sz' [-Wreorder]
   11 |     int sz,val,mn,mx,prior,pos;
      |         ^~
fish2.cpp:12:5: warning:   when initialized here [-Wreorder]
   12 |     node(int k,int p):pos(p),sz(1),val(k),mn(k),mx(k),prior(rng()){}
      |     ^~~~
fish2.cpp: At global scope:
fish2.cpp:140:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  140 | main(){
      | ^~~~

• Subtask 1: 0 / 5
• Subtask 2: 8 / 8
• Subtask 3: 0 / 12
• Subtask 4: 0 / 23
• Subtask 5: 0 / 35
• Subtask 6: 0 / 17