oj.uz

Submission #549480

# Submission time Handle Problem Language Result Execution time Memory
549480 2022-04-15T21:40:22 Z duality Fish 2 (JOI22_fish2) C++17
8 / 100
 4000 ms 140712 KB 
#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 build(int s,int e,int i) {
    if (s == e) {
        occ[i] = 1;
        return 0;
    }

    int mid = (s+e) / 2;
    build(s,mid,2*i+1),build(mid+1,e,2*i+2);
    occ[i] = e-s+1;
    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 ((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);
    }
    build(0,N-1,0);
    for (i = 0; i < N; i++) update(i,A[i]);
    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);
                }
            }
        }
    }

    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();
            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);
            f = 0,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

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 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 340 KB Output is correct
2 Correct 857 ms 75100 KB Output is correct
3 Correct 348 ms 34884 KB Output is correct
4 Correct 833 ms 74864 KB Output is correct
5 Correct 361 ms 36796 KB Output is correct
6 Correct 1749 ms 140676 KB Output is correct
7 Correct 85 ms 14028 KB Output is correct
8 Correct 1674 ms 140712 KB Output is correct
9 Correct 91 ms 14124 KB Output is correct
10 Correct 807 ms 76712 KB Output is correct
11 Correct 242 ms 29460 KB Output is correct
12 Correct 163 ms 22120 KB Output is correct
13 Correct 181 ms 22040 KB Output is correct
14 Correct 1196 ms 77548 KB Output is correct
15 Correct 1111 ms 77516 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 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 340 KB Output is correct
2 Correct 857 ms 75100 KB Output is correct
3 Correct 348 ms 34884 KB Output is correct
4 Correct 833 ms 74864 KB Output is correct
5 Correct 361 ms 36796 KB Output is correct
6 Correct 1749 ms 140676 KB Output is correct
7 Correct 85 ms 14028 KB Output is correct
8 Correct 1674 ms 140712 KB Output is correct
9 Correct 91 ms 14124 KB Output is correct
10 Correct 807 ms 76712 KB Output is correct
11 Correct 242 ms 29460 KB Output is correct
12 Correct 163 ms 22120 KB Output is correct
13 Correct 181 ms 22040 KB Output is correct
14 Correct 1196 ms 77548 KB Output is correct
15 Correct 1111 ms 77516 KB Output is correct
16 Incorrect 1 ms 340 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 340 KB Output is correct
2 Correct 857 ms 75100 KB Output is correct
3 Correct 348 ms 34884 KB Output is correct
4 Correct 833 ms 74864 KB Output is correct
5 Correct 361 ms 36796 KB Output is correct
6 Correct 1749 ms 140676 KB Output is correct
7 Correct 85 ms 14028 KB Output is correct
8 Correct 1674 ms 140712 KB Output is correct
9 Correct 91 ms 14124 KB Output is correct
10 Correct 807 ms 76712 KB Output is correct
11 Correct 242 ms 29460 KB Output is correct
12 Correct 163 ms 22120 KB Output is correct
13 Correct 181 ms 22040 KB Output is correct
14 Correct 1196 ms 77548 KB Output is correct
15 Correct 1111 ms 77516 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Execution timed out 4066 ms 75128 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

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