Submission #597890

#	Time	Username	Problem	Language	Result	Execution time	Memory
597890		qwerasdfzxcl	Fish 2 (JOI22_fish2)	C++14	100 / 100	2236 ms	23296 KiB

fish2

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
int n, a[100100];

struct Seg1{
    ll tree[200200], sz;
    void init(int n){
        sz = n;
        for (int i=sz;i<sz*2;i++) tree[i] = a[i-sz];
        for (int i=sz-1;i;i--) tree[i] = tree[i<<1] + tree[i<<1|1];
    }
    void update(int p, int x){
        for (tree[p+=sz]=x;p>1;p>>=1) tree[p>>1] = tree[p] + tree[p^1];
    }
    ll query(int l, int r){
        ++r;
        ll ret = 0;
        for (l+=sz, r+=sz;l<r;l>>=1, r>>=1){
            if (l&1) ret += tree[l++];
            if (r&1) ret += tree[--r];
        }
        return ret;
    }
}tree1;

struct Seg2{
    int tree[400400];
    void init(int i, int l, int r){
        if (l==r) {tree[i] = a[l]; return;}
        int m = (l+r)>>1;
        init(i<<1, l, m); init(i<<1|1, m+1, r);
        tree[i] = max(tree[i<<1], tree[i<<1|1]);
    }
    void update(int i, int l, int r, int p, int x){
        if (p<l || r<p) return;
        if (l==r) {tree[i] = x; return;}
        int m = (l+r)>>1;
        update(i<<1, l, m, p, x); update(i<<1|1, m+1, r, p, x);
        tree[i] = max(tree[i<<1], tree[i<<1|1]);
    }
    int left_bound(int i, int l, int r, int s, int e, ll x){
        if (r<s || e<l) return -1;
        if (tree[i] <= x) return -1;
        if (l==r) return l;

        int m = (l+r)>>1;
        int tmp = left_bound(i<<1|1, m+1, r, s, e, x);
        if (tmp!=-1) return tmp;
        return left_bound(i<<1, l, m, s, e, x);
    }
    int right_bound(int i, int l, int r, int s, int e, ll x){
        if (r<s || e<l) return -1;
        if (tree[i] <= x) return -1;
        if (l==r) return l;

        int m = (l+r)>>1;
        int tmp = right_bound(i<<1, l, m, s, e, x);
        if (tmp!=-1) return tmp;
        return right_bound(i<<1|1, m+1, r, s, e, x);
    }
}tree2;

struct Node{
    int mn, cnt;
    Node(){}
    Node(int _mn, int _cnt): mn(_mn), cnt(_cnt) {}
    Node operator + (const Node &N) const{
        if (mn < N.mn) return *this;
        if (mn > N.mn) return N;
        return Node(mn, cnt+N.cnt);
    }
};

struct Seg3{
    Node tree[400400];
    int lazy[400400];
    void init(int i, int l, int r){
        if (l==r) {tree[i] = Node(0, 1); return;}
        int m = (l+r)>>1;
        init(i<<1, l, m); init(i<<1|1, m+1, r);
        tree[i] = tree[i<<1] + tree[i<<1|1];
    }
    void propagate(int i, int l, int r){
        tree[i].mn += lazy[i];
        if (l!=r){
            lazy[i<<1] += lazy[i];
            lazy[i<<1|1] += lazy[i];
        }
        lazy[i] = 0;
    }
    void update(int i, int l, int r, int s, int e, int x){
        propagate(i, l, r);
        if (r<s || e<l) return;
        if (s<=l && r<=e){
            lazy[i] += x;
            propagate(i, l, r);
            return;
        }
        int m = (l+r)>>1;
        update(i<<1, l, m, s, e, x); update(i<<1|1, m+1, r, s, e, x);
        tree[i] = tree[i<<1] + tree[i<<1|1];
    }
    Node query(int i, int l, int r, int s, int e){
        propagate(i, l, r);
        if (r<s || e<l) return Node(1e9, 0);
        if (s<=l && r<=e) return tree[i];
        int m = (l+r)>>1;
        return query(i<<1, l, m, s, e) + query(i<<1|1, m+1, r, s, e);
    }
}tree3;

struct Seg4{
    vector<pair<int, int>> tree[400400];
    void update(int i, int l, int r, int s, int e){
        if (l==r) {
            tree[i].emplace_back(s, e);
            tree3.update(1, 1, n, s, e, 1);
            return;
        }

        int m = (l+r)>>1;
        if (e<=m) update(i<<1, l, m, s, e);
        else if (m+1<=s) update(i<<1|1, m+1, r, s, e);
        else{
            tree[i].emplace_back(s, e);
            tree3.update(1, 1, n, s, e, 1);
        }
    }
    void erase(int i, int l, int r, int p){
        while(!tree[i].empty() && tree[i].back().first <= p && p <= tree[i].back().second){
            tree3.update(1, 1, n, tree[i].back().first, tree[i].back().second, -1);
            tree[i].pop_back();
        }
        if (l==r) return;

        int m = (l+r)>>1;
        if (p<=m) erase(i<<1, l, m, p);
        else erase(i<<1|1, m+1, r, p);
    }
    void debug(int i, int l, int r){
        printf("[%d, %d]: ", l, r);
        for (auto &[x, y]:tree[i]) printf("[%d, %d] / ", x, y);
        printf("\n");
        if (l==r) return;

        int m = (l+r)>>1;
        debug(i<<1, l, m);
        debug(i<<1|1, m+1, r);
    }
}tree4;

bool cmp(pair<int, int> &x, pair<int, int> &y){return x.second-x.first < y.second-y.first;}

bool ok(int l, int r, int s, int e){
    ll L = s==l?1e18:a[s-1], R = e==r?1e18:a[e+1];
    ll S = tree1.query(s, e);
    return S<L && S<R;
}

vector<int> getL(int l, int r, int s){
    vector<int> ret;
    int cur = s;
    while(true){
        int nxt = tree2.left_bound(1, 1, n, l, cur-1, tree1.query(cur, s));
        if (nxt==-1) break;
        ret.push_back(nxt+1);
        cur = nxt;
    }

    ret.push_back(l);
    return ret;
}

vector<int> getR(int l, int r, int s){
    vector<int> ret;
    int cur = s;
    while(true){
        int nxt = tree2.right_bound(1, 1, n, cur+1, r, tree1.query(s, cur));
        if (nxt==-1) break;
        //printf(" %d %d -> %d\n", s, cur, nxt);
        ret.push_back(nxt-1);
        cur = nxt;
    }
    ret.push_back(r);
    return ret;
}

void refresh(int x, vector<pair<int, int>> &P){
    if (x<1 || x>n) return;
    tree4.erase(1, 1, n, x);
    auto L = getL(1, n, x);
    auto R = getR(1, n, x);


    for (auto &l:L){
        for (auto &r:R) if (ok(1, n, l, r)){
            P.emplace_back(l, r);
        }
    }
}

void update(int x, int y){
    tree1.update(x, y);
    tree2.update(1, 1, n, x, y);
    a[x] = y;

    vector<pair<int, int>> P;
    refresh(x-1, P);
    refresh(x, P);
    refresh(x+1, P);

    sort(P.begin(), P.end(), cmp);
    P.erase(unique(P.begin(), P.end()), P.end());
    for (auto &[l, r]:P) tree4.update(1, 1, n, l, r);

    //tree4.debug(1, 1, n);
}

int query(int l, int r){
    auto R0 = getR(l, r-1, l);
    auto L0 = getL(l+1, r, r);

    int nl = l, nr = r;
    for (auto &x:R0) if (ok(l, r, l, x)) nl = x+1;
    for (auto &x:L0) if (ok(l, r, x, r)) nr = x-1;

    return tree3.query(1, 1, n, nl, nr).cnt;
}

int main(){
    scanf("%d", &n);
    for (int i=1;i<=n;i++) scanf("%d", a+i);

    tree1.init(n+1);
    tree2.init(1, 1, n);
    tree3.init(1, 1, n);

    vector<pair<int, int>> P;
    for (int i=1;i<=n;i++){
        //printf("ok %d\n", i);
        auto R = getR(1, n, i);
        for (auto &x:R) if (ok(1, n, i, x)){
            P.emplace_back(i, x);
            //printf("%d %d\n", i, x);
        }
    }
    sort(P.begin(), P.end(), cmp);
    for (auto &[l, r]:P) tree4.update(1, 1, n, l, r);

    //tree4.debug(1, 1, n);

    int q;
    scanf("%d", &q);
    while(q--){
        int op, x, y;
        scanf("%d %d %d", &op, &x, &y);
        if (op==1) update(x, y);
        else printf("%d\n", query(x, y));
    }
    return 0;
}

Compilation message (stderr)

fish2.cpp: In member function 'void Seg4::debug(int, int, int)':
fish2.cpp:144:20: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  144 |         for (auto &[x, y]:tree[i]) printf("[%d, %d] / ", x, y);
      |                    ^
fish2.cpp: In function 'void update(int, int)':
fish2.cpp:216:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  216 |     for (auto &[l, r]:P) tree4.update(1, 1, n, l, r);
      |                ^
fish2.cpp: In function 'int main()':
fish2.cpp:250:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  250 |     for (auto &[l, r]:P) tree4.update(1, 1, n, l, r);
      |                ^
fish2.cpp:233:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  233 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
fish2.cpp:234:33: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  234 |     for (int i=1;i<=n;i++) scanf("%d", a+i);
      |                            ~~~~~^~~~~~~~~~~
fish2.cpp:255:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  255 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
fish2.cpp:258:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  258 |         scanf("%d %d %d", &op, &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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