oj.uz

Submission #877328

# Submission time Handle Problem Language Result Execution time Memory
877328 2023-11-23T06:36:47 Z vjudge1 Fish 2 (JOI22_fish2) C++17
8 / 100
 321 ms 29028 KB 
#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;
}
int res = 0;
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;
            }
        }
        if(x[i] == 1 && y[i] == n)res++; 
    }
}
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;
        }
        cout << res << '\n';
    }
}
main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    test();
}

Compilation message

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:138:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  138 | main(){
      | ^~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 6492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 243 ms 29028 KB Output is correct
3 Correct 248 ms 28752 KB Output is correct
4 Correct 240 ms 28752 KB Output is correct
5 Correct 250 ms 28772 KB Output is correct
6 Correct 176 ms 28776 KB Output is correct
7 Correct 321 ms 28772 KB Output is correct
8 Correct 179 ms 28652 KB Output is correct
9 Correct 316 ms 28752 KB Output is correct
10 Correct 251 ms 28776 KB Output is correct
11 Correct 237 ms 28756 KB Output is correct
12 Correct 248 ms 28756 KB Output is correct
13 Correct 247 ms 28612 KB Output is correct
14 Correct 195 ms 28768 KB Output is correct
15 Correct 201 ms 28776 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 6492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 243 ms 29028 KB Output is correct
3 Correct 248 ms 28752 KB Output is correct
4 Correct 240 ms 28752 KB Output is correct
5 Correct 250 ms 28772 KB Output is correct
6 Correct 176 ms 28776 KB Output is correct
7 Correct 321 ms 28772 KB Output is correct
8 Correct 179 ms 28652 KB Output is correct
9 Correct 316 ms 28752 KB Output is correct
10 Correct 251 ms 28776 KB Output is correct
11 Correct 237 ms 28756 KB Output is correct
12 Correct 248 ms 28756 KB Output is correct
13 Correct 247 ms 28612 KB Output is correct
14 Correct 195 ms 28768 KB Output is correct
15 Correct 201 ms 28776 KB Output is correct
16 Incorrect 1 ms 6488 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 243 ms 29028 KB Output is correct
3 Correct 248 ms 28752 KB Output is correct
4 Correct 240 ms 28752 KB Output is correct
5 Correct 250 ms 28772 KB Output is correct
6 Correct 176 ms 28776 KB Output is correct
7 Correct 321 ms 28772 KB Output is correct
8 Correct 179 ms 28652 KB Output is correct
9 Correct 316 ms 28752 KB Output is correct
10 Correct 251 ms 28776 KB Output is correct
11 Correct 237 ms 28756 KB Output is correct
12 Correct 248 ms 28756 KB Output is correct
13 Correct 247 ms 28612 KB Output is correct
14 Correct 195 ms 28768 KB Output is correct
15 Correct 201 ms 28776 KB Output is correct
16 Incorrect 1 ms 6492 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 6492 KB Output isn't correct
2 Halted 0 ms 0 KB -