oj.uz

Submission #549484

# Submission time Handle Problem Language Result Execution time Memory
549484 2022-04-15T21:44:54 Z duality Fish 2 (JOI22_fish2) C++17
25 / 100
 4000 ms 152624 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 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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 19 ms 724 KB Output is correct
6 Correct 27 ms 592 KB Output is correct
7 Correct 16 ms 584 KB Output is correct
8 Correct 31 ms 340 KB Output is correct
9 Correct 26 ms 468 KB Output is correct
10 Correct 16 ms 1184 KB Output is correct
11 Correct 20 ms 1108 KB Output is correct
12 Correct 21 ms 724 KB Output is correct
13 Correct 28 ms 480 KB Output is correct
14 Correct 10 ms 724 KB Output is correct
15 Correct 24 ms 668 KB Output is correct
16 Correct 19 ms 468 KB Output is correct
17 Correct 20 ms 528 KB Output is correct
18 Correct 27 ms 468 KB Output is correct
19 Correct 18 ms 980 KB Output is correct
20 Correct 21 ms 816 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 787 ms 76072 KB Output is correct
3 Correct 298 ms 35900 KB Output is correct
4 Correct 783 ms 76032 KB Output is correct
5 Correct 312 ms 37812 KB Output is correct
6 Correct 1475 ms 151776 KB Output is correct
7 Correct 67 ms 14088 KB Output is correct
8 Correct 1475 ms 151720 KB Output is correct
9 Correct 69 ms 14148 KB Output is correct
10 Correct 810 ms 76728 KB Output is correct
11 Correct 238 ms 29324 KB Output is correct
12 Correct 157 ms 23036 KB Output is correct
13 Correct 132 ms 22972 KB Output is correct
14 Correct 759 ms 99020 KB Output is correct
15 Correct 781 ms 98952 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 19 ms 724 KB Output is correct
6 Correct 27 ms 592 KB Output is correct
7 Correct 16 ms 584 KB Output is correct
8 Correct 31 ms 340 KB Output is correct
9 Correct 26 ms 468 KB Output is correct
10 Correct 16 ms 1184 KB Output is correct
11 Correct 20 ms 1108 KB Output is correct
12 Correct 21 ms 724 KB Output is correct
13 Correct 28 ms 480 KB Output is correct
14 Correct 10 ms 724 KB Output is correct
15 Correct 24 ms 668 KB Output is correct
16 Correct 19 ms 468 KB Output is correct
17 Correct 20 ms 528 KB Output is correct
18 Correct 27 ms 468 KB Output is correct
19 Correct 18 ms 980 KB Output is correct
20 Correct 21 ms 816 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 787 ms 76072 KB Output is correct
23 Correct 298 ms 35900 KB Output is correct
24 Correct 783 ms 76032 KB Output is correct
25 Correct 312 ms 37812 KB Output is correct
26 Correct 1475 ms 151776 KB Output is correct
27 Correct 67 ms 14088 KB Output is correct
28 Correct 1475 ms 151720 KB Output is correct
29 Correct 69 ms 14148 KB Output is correct
30 Correct 810 ms 76728 KB Output is correct
31 Correct 238 ms 29324 KB Output is correct
32 Correct 157 ms 23036 KB Output is correct
33 Correct 132 ms 22972 KB Output is correct
34 Correct 759 ms 99020 KB Output is correct
35 Correct 781 ms 98952 KB Output is correct
36 Correct 935 ms 80180 KB Output is correct
37 Correct 413 ms 37824 KB Output is correct
38 Correct 425 ms 37536 KB Output is correct
39 Correct 908 ms 80404 KB Output is correct
40 Correct 398 ms 37328 KB Output is correct
41 Correct 1570 ms 152492 KB Output is correct
42 Correct 1546 ms 152624 KB Output is correct
43 Correct 174 ms 15420 KB Output is correct
44 Correct 152 ms 15240 KB Output is correct
45 Correct 864 ms 74156 KB Output is correct
46 Correct 853 ms 76012 KB Output is correct
47 Correct 302 ms 26980 KB Output is correct
48 Correct 200 ms 24372 KB Output is correct
49 Correct 222 ms 24128 KB Output is correct
50 Correct 823 ms 99044 KB Output is correct
51 Correct 854 ms 98916 KB Output is correct
52 Correct 843 ms 98968 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 787 ms 76072 KB Output is correct
3 Correct 298 ms 35900 KB Output is correct
4 Correct 783 ms 76032 KB Output is correct
5 Correct 312 ms 37812 KB Output is correct
6 Correct 1475 ms 151776 KB Output is correct
7 Correct 67 ms 14088 KB Output is correct
8 Correct 1475 ms 151720 KB Output is correct
9 Correct 69 ms 14148 KB Output is correct
10 Correct 810 ms 76728 KB Output is correct
11 Correct 238 ms 29324 KB Output is correct
12 Correct 157 ms 23036 KB Output is correct
13 Correct 132 ms 22972 KB Output is correct
14 Correct 759 ms 99020 KB Output is correct
15 Correct 781 ms 98952 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Execution timed out 4101 ms 38040 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 787 ms 76072 KB Output is correct
3 Correct 298 ms 35900 KB Output is correct
4 Correct 783 ms 76032 KB Output is correct
5 Correct 312 ms 37812 KB Output is correct
6 Correct 1475 ms 151776 KB Output is correct
7 Correct 67 ms 14088 KB Output is correct
8 Correct 1475 ms 151720 KB Output is correct
9 Correct 69 ms 14148 KB Output is correct
10 Correct 810 ms 76728 KB Output is correct
11 Correct 238 ms 29324 KB Output is correct
12 Correct 157 ms 23036 KB Output is correct
13 Correct 132 ms 22972 KB Output is correct
14 Correct 759 ms 99020 KB Output is correct
15 Correct 781 ms 98952 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Execution timed out 4094 ms 77224 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 19 ms 724 KB Output is correct
6 Correct 27 ms 592 KB Output is correct
7 Correct 16 ms 584 KB Output is correct
8 Correct 31 ms 340 KB Output is correct
9 Correct 26 ms 468 KB Output is correct
10 Correct 16 ms 1184 KB Output is correct
11 Correct 20 ms 1108 KB Output is correct
12 Correct 21 ms 724 KB Output is correct
13 Correct 28 ms 480 KB Output is correct
14 Correct 10 ms 724 KB Output is correct
15 Correct 24 ms 668 KB Output is correct
16 Correct 19 ms 468 KB Output is correct
17 Correct 20 ms 528 KB Output is correct
18 Correct 27 ms 468 KB Output is correct
19 Correct 18 ms 980 KB Output is correct
20 Correct 21 ms 816 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 787 ms 76072 KB Output is correct
23 Correct 298 ms 35900 KB Output is correct
24 Correct 783 ms 76032 KB Output is correct
25 Correct 312 ms 37812 KB Output is correct
26 Correct 1475 ms 151776 KB Output is correct
27 Correct 67 ms 14088 KB Output is correct
28 Correct 1475 ms 151720 KB Output is correct
29 Correct 69 ms 14148 KB Output is correct
30 Correct 810 ms 76728 KB Output is correct
31 Correct 238 ms 29324 KB Output is correct
32 Correct 157 ms 23036 KB Output is correct
33 Correct 132 ms 22972 KB Output is correct
34 Correct 759 ms 99020 KB Output is correct
35 Correct 781 ms 98952 KB Output is correct
36 Correct 935 ms 80180 KB Output is correct
37 Correct 413 ms 37824 KB Output is correct
38 Correct 425 ms 37536 KB Output is correct
39 Correct 908 ms 80404 KB Output is correct
40 Correct 398 ms 37328 KB Output is correct
41 Correct 1570 ms 152492 KB Output is correct
42 Correct 1546 ms 152624 KB Output is correct
43 Correct 174 ms 15420 KB Output is correct
44 Correct 152 ms 15240 KB Output is correct
45 Correct 864 ms 74156 KB Output is correct
46 Correct 853 ms 76012 KB Output is correct
47 Correct 302 ms 26980 KB Output is correct
48 Correct 200 ms 24372 KB Output is correct
49 Correct 222 ms 24128 KB Output is correct
50 Correct 823 ms 99044 KB Output is correct
51 Correct 854 ms 98916 KB Output is correct
52 Correct 843 ms 98968 KB Output is correct
53 Correct 1 ms 340 KB Output is correct
54 Execution timed out 4101 ms 38040 KB Time limit exceeded
55 Halted 0 ms 0 KB -