Submission #549484

#	Time	Username	Problem	Language	Result	Execution time	Memory
549484		duality	Fish 2 (JOI22_fish2)	C++17	25 / 100	4101 ms	152624 KiB

fish2

#define DEBUG 0

#include <bits/stdc++.h>
using namespace std;

#if DEBUG
// basic debugging macros
int __i__,__j__;
#define printLine(l) for(__i__=0;__i__<l;__i__++){cout<<"-";}cout<<endl
#define printLine2(l,c) for(__i__=0;__i__<l;__i__++){cout<<c;}cout<<endl
#define printVar(n) cout<<#n<<": "<<n<<endl
#define printArr(a,l) cout<<#a<<": ";for(__i__=0;__i__<l;__i__++){cout<<a[__i__]<<" ";}cout<<endl
#define print2dArr(a,r,c) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<a[__i__][__j__]<<" ";}cout<<endl;}
#define print2dArr2(a,r,c,l) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<setw(l)<<setfill(' ')<<a[__i__][__j__]<<" ";}cout<<endl;}

// advanced debugging class
// debug 1,2,'A',"test";
class _Debug {
    public:
        template<typename T>
        _Debug& operator,(T val) {
            cout << val << endl;
            return *this;
        }
};
#define debug _Debug(),
#else
#define printLine(l)
#define printLine2(l,c)
#define printVar(n)
#define printArr(a,l)
#define print2dArr(a,r,c)
#define print2dArr2(a,r,c,l)
#define debug
#endif

// define
#define MAX_VAL 999999999
#define MAX_VAL_2 999999999999999999LL
#define EPS 1e-6
#define mp make_pair
#define pb push_back

// typedef
typedef unsigned int UI;
typedef long long int LLI;
typedef unsigned long long int ULLI;
typedef unsigned short int US;
typedef pair<int,int> pii;
typedef pair<LLI,LLI> plli;
typedef vector<int> vi;
typedef vector<LLI> vlli;
typedef vector<pii> vpii;
typedef vector<plli> vplli;

// ---------- END OF TEMPLATE ----------
#pragma GCC optimize("Ofast")

int N,A[100002];
LLI bit[100003];
int update(int i,int num) {
    for (i++; i <= N; i += i & (-i)) bit[i] += num;
    return 0;
}
LLI query(int s,int e) {
    LLI sum = 0;
    for (e++; e > 0; e -= e & (-e)) sum += bit[e];
    for (; s > 0; s -= s & (-s)) sum -= bit[s];
    return sum;
}
set<int> layer[31];
int tree[1 << 18],lazy[1 << 18],occ[1 << 18];
int diff[100003];
int build(int s,int e,int i) {
    if (s == e) {
        occ[i] = 1,tree[i] = diff[s];
        return 0;
    }

    int mid = (s+e) / 2;
    build(s,mid,2*i+1),build(mid+1,e,2*i+2);
    tree[i] = min(tree[2*i+1],tree[2*i+2]),occ[i] = 0;
    if (tree[i] == tree[2*i+1]) occ[i] += occ[2*i+1];
    if (tree[i] == tree[2*i+2]) occ[i] += occ[2*i+2];
    return 0;
}
int prop(int s,int e,int i) {
    if (lazy[i] != 0) {
        tree[i] += lazy[i];
        if (s != e) lazy[2*i+1] += lazy[i],lazy[2*i+2] += lazy[i];
        lazy[i] = 0;
    }
    return 0;
}
int f = 0;
vector<pair<pii,int> > updates;
int com() {
    vector<pair<pii,int> > updates2;
    sort(updates.begin(),updates.end());
    for (auto p: updates) {
        if (!updates2.empty() && (updates2.back().first == p.first)) updates2.back().second += p.second;
        else updates2.pb(p);
    }
    updates = updates2;
    return 0;
}
int update(int s,int e,int as,int ae,int i,int num) {
    if (num == 0) return 0;
    if ((f == 2) && (i == 0)) {
        updates.pb(mp(mp(as,ae),num));
        return 0;
    }
    if ((f == 1) && (i == 0)) updates.pb(mp(mp(as,ae),num));
    prop(s,e,i);
    if ((s > ae) || (e < as)) return 0;
    else if ((s >= as) && (e <= ae)) {
        lazy[i] += num;
        prop(s,e,i);
        return 0;
    }

    int mid = (s+e) / 2;
    update(s,mid,as,ae,2*i+1,num),update(mid+1,e,as,ae,2*i+2,num);
    tree[i] = min(tree[2*i+1],tree[2*i+2]),occ[i] = 0;
    if (tree[i] == tree[2*i+1]) occ[i] += occ[2*i+1];
    if (tree[i] == tree[2*i+2]) occ[i] += occ[2*i+2];
    return 0;
}
pii query(int s,int e,int qs,int qe,int i) {
    prop(s,e,i);
    if ((s > qe) || (e < qs)) return mp(1e9,0);
    else if ((s >= qs) && (e <= qe)) return mp(tree[i],occ[i]);

    int mid = (s+e) / 2;
    pii l = query(s,mid,qs,qe,2*i+1),r = query(mid+1,e,qs,qe,2*i+2);
    return mp(min(l.first,r.first),((l.first <= r.first) ? l.second:0)+((l.first >= r.first) ? r.second:0));
}
int check(int l,int r,int m = -1) {
    if ((m != -1) && ((l > m) || (r < m))) return 0;
    else return (l < r-1) && (min(A[l],A[r]) > query(l+1,r-1));
}
int update2(int p,int a,int t) {
    int i;
    for (i = 0; i < 31; i++) {
        auto it = layer[i].lower_bound(p);
        if (it == layer[i].end()) continue;
        if (t == 1) {
            if ((it != layer[i].begin()) && check(*prev(it),*it,p)) update(0,N-1,*prev(it)+1,*it-1,0,-1);
            if ((next(it) != layer[i].end()) && check(*it,*next(it),p)) update(0,N-1,*it+1,*next(it)-1,0,-1);
            if ((it != layer[i].begin()) && (next(it) != layer[i].end()) && check(*prev(it),*next(it),p))
                update(0,N-1,*prev(it)+1,*next(it)-1,0,-1);
            if ((it != layer[i].begin()) && (prev(it) != layer[i].begin()) && check(*prev(prev(it)),*it,p))
                update(0,N-1,*prev(prev(it))+1,*it-1,0,-1);
            if ((next(it) != layer[i].end()) && (next(next(it)) != layer[i].end()) && check(*it,*next(next(it)),p))
                update(0,N-1,*it+1,*next(next(it))-1,0,-1);
        }
        if (*it == p) layer[i].erase(it);
    }
    update(p,a-A[p]),A[p] = a;
    for (i = 0; i < 31; i++) {
        if (i <= __lg(A[p])) layer[i].insert(p);
        auto it = layer[i].lower_bound(p);
        if (it == layer[i].end()) continue;
        if (t == 1) {
            if ((it != layer[i].begin()) && check(*prev(it),*it,p)) update(0,N-1,*prev(it)+1,*it-1,0,1);
            if ((next(it) != layer[i].end()) && check(*it,*next(it),p)) update(0,N-1,*it+1,*next(it)-1,0,1);
            if ((it != layer[i].begin()) && (next(it) != layer[i].end()) && check(*prev(it),*next(it),p))
                update(0,N-1,*prev(it)+1,*next(it)-1,0,1);
            if ((it != layer[i].begin()) && (prev(it) != layer[i].begin()) && check(*prev(prev(it)),*it,p))
                update(0,N-1,*prev(prev(it))+1,*it-1,0,1);
            if ((next(it) != layer[i].end()) && (next(next(it)) != layer[i].end()) && check(*it,*next(next(it)),p))
                update(0,N-1,*it+1,*next(next(it))-1,0,1);
        }
    }
    return 0;
}
int main() {
    int i;
    int Q;
    scanf("%d",&N);
    for (i = 1; i <= N; i++) scanf("%d",&A[i]);
    A[0] = A[N+1] = 1.1e9,N += 2;

    int j;
    for (i = 0; i < N; i++) {
        for (j = 0; j <= __lg(A[i]); j++) layer[j].insert(i);
    }
    for (i = 0; i < N; i++) update(i,A[i]);
    f = 2;
    for (i = 0; i < 31; i++) {
        for (auto it = layer[i].begin(); it != layer[i].end(); it++) {
            if (it != layer[i].begin()) {
                if (check(*prev(it),*it)) update(0,N-1,*prev(it)+1,*it-1,0,1);
                if (next(it) != layer[i].end()) {
                    if (check(*prev(it),*next(it))) update(0,N-1,*prev(it)+1,*next(it)-1,0,1);
                }
            }
        }
    }
    for (auto [p,n]: updates) diff[p.first] += n,diff[p.second+1] -= n;
    for (i = 1; i < N; i++) diff[i] += diff[i-1];
    f = 0,build(0,N-1,0);
    updates.clear();

    int T,X,Y,L,R;
    scanf("%d",&Q);
    for (i = 0; i < Q; i++) {
        scanf("%d",&T);
        if (T == 1) scanf("%d %d",&X,&Y),update2(X,Y,1);
        else {
            scanf("%d %d",&L,&R);
            int l = A[L-1],r = A[R+1];
            f = 2,update2(L-1,1.1e9,1),update2(R+1,1.1e9,1);
            com(),f = 0;
            for (auto [p,n]: updates) update(0,N-1,p.first,p.second,0,n);
            pii p = query(0,N-1,L,R,0);
            printf("%d\n",p.second);
            update2(L-1,l,-1),update2(R+1,r,-1);
            for (auto [p,n]: updates) update(0,N-1,p.first,p.second,0,-n);
            updates.clear();
        }
    }

    return 0;
}

Compilation message (stderr)

fish2.cpp: In function 'int main()':
fish2.cpp:180:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  180 |     scanf("%d",&N);
      |     ~~~~~^~~~~~~~~
fish2.cpp:181:35: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  181 |     for (i = 1; i <= N; i++) scanf("%d",&A[i]);
      |                              ~~~~~^~~~~~~~~~~~
fish2.cpp:206:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  206 |     scanf("%d",&Q);
      |     ~~~~~^~~~~~~~~
fish2.cpp:208:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  208 |         scanf("%d",&T);
      |         ~~~~~^~~~~~~~~
fish2.cpp:209:26: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  209 |         if (T == 1) scanf("%d %d",&X,&Y),update2(X,Y,1);
      |                     ~~~~~^~~~~~~~~~~~~~~
fish2.cpp:211:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  211 |             scanf("%d %d",&L,&R);
      |             ~~~~~^~~~~~~~~~~~~~~

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