oj.uz

Submission #549482

# Submission time Handle Problem Language Result Execution time Memory
549482 2022-04-15T21:41:29 Z duality Fish 2 (JOI22_fish2) C++17
25 / 100
 4000 ms 140916 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(),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: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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 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 21 ms 820 KB Output is correct
6 Correct 28 ms 468 KB Output is correct
7 Correct 16 ms 468 KB Output is correct
8 Correct 31 ms 444 KB Output is correct
9 Correct 25 ms 716 KB Output is correct
10 Correct 16 ms 1048 KB Output is correct
11 Correct 24 ms 972 KB Output is correct
12 Correct 23 ms 768 KB Output is correct
13 Correct 29 ms 496 KB Output is correct
14 Correct 10 ms 724 KB Output is correct
15 Correct 24 ms 644 KB Output is correct
16 Correct 18 ms 468 KB Output is correct
17 Correct 20 ms 596 KB Output is correct
18 Correct 27 ms 476 KB Output is correct
19 Correct 19 ms 844 KB Output is correct
20 Correct 22 ms 792 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 873 ms 75012 KB Output is correct
3 Correct 343 ms 34796 KB Output is correct
4 Correct 862 ms 74980 KB Output is correct
5 Correct 390 ms 36680 KB Output is correct
6 Correct 1729 ms 140556 KB Output is correct
7 Correct 90 ms 13984 KB Output is correct
8 Correct 1747 ms 140584 KB Output is correct
9 Correct 88 ms 14028 KB Output is correct
10 Correct 854 ms 76780 KB Output is correct
11 Correct 244 ms 29132 KB Output is correct
12 Correct 184 ms 22140 KB Output is correct
13 Correct 178 ms 21952 KB Output is correct
14 Correct 1195 ms 77552 KB Output is correct
15 Correct 1144 ms 77628 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 1 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 21 ms 820 KB Output is correct
6 Correct 28 ms 468 KB Output is correct
7 Correct 16 ms 468 KB Output is correct
8 Correct 31 ms 444 KB Output is correct
9 Correct 25 ms 716 KB Output is correct
10 Correct 16 ms 1048 KB Output is correct
11 Correct 24 ms 972 KB Output is correct
12 Correct 23 ms 768 KB Output is correct
13 Correct 29 ms 496 KB Output is correct
14 Correct 10 ms 724 KB Output is correct
15 Correct 24 ms 644 KB Output is correct
16 Correct 18 ms 468 KB Output is correct
17 Correct 20 ms 596 KB Output is correct
18 Correct 27 ms 476 KB Output is correct
19 Correct 19 ms 844 KB Output is correct
20 Correct 22 ms 792 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 873 ms 75012 KB Output is correct
23 Correct 343 ms 34796 KB Output is correct
24 Correct 862 ms 74980 KB Output is correct
25 Correct 390 ms 36680 KB Output is correct
26 Correct 1729 ms 140556 KB Output is correct
27 Correct 90 ms 13984 KB Output is correct
28 Correct 1747 ms 140584 KB Output is correct
29 Correct 88 ms 14028 KB Output is correct
30 Correct 854 ms 76780 KB Output is correct
31 Correct 244 ms 29132 KB Output is correct
32 Correct 184 ms 22140 KB Output is correct
33 Correct 178 ms 21952 KB Output is correct
34 Correct 1195 ms 77552 KB Output is correct
35 Correct 1144 ms 77628 KB Output is correct
36 Correct 997 ms 78224 KB Output is correct
37 Correct 500 ms 35868 KB Output is correct
38 Correct 491 ms 35980 KB Output is correct
39 Correct 982 ms 78200 KB Output is correct
40 Correct 452 ms 35536 KB Output is correct
41 Correct 1839 ms 140760 KB Output is correct
42 Correct 1828 ms 140916 KB Output is correct
43 Correct 174 ms 14536 KB Output is correct
44 Correct 206 ms 14140 KB Output is correct
45 Correct 908 ms 73468 KB Output is correct
46 Correct 933 ms 74976 KB Output is correct
47 Correct 293 ms 26172 KB Output is correct
48 Correct 291 ms 22464 KB Output is correct
49 Correct 234 ms 22216 KB Output is correct
50 Correct 1277 ms 78184 KB Output is correct
51 Correct 1177 ms 78020 KB Output is correct
52 Correct 1274 ms 77816 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 873 ms 75012 KB Output is correct
3 Correct 343 ms 34796 KB Output is correct
4 Correct 862 ms 74980 KB Output is correct
5 Correct 390 ms 36680 KB Output is correct
6 Correct 1729 ms 140556 KB Output is correct
7 Correct 90 ms 13984 KB Output is correct
8 Correct 1747 ms 140584 KB Output is correct
9 Correct 88 ms 14028 KB Output is correct
10 Correct 854 ms 76780 KB Output is correct
11 Correct 244 ms 29132 KB Output is correct
12 Correct 184 ms 22140 KB Output is correct
13 Correct 178 ms 21952 KB Output is correct
14 Correct 1195 ms 77552 KB Output is correct
15 Correct 1144 ms 77628 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Execution timed out 4082 ms 36440 KB Time limit exceeded
18 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 873 ms 75012 KB Output is correct
3 Correct 343 ms 34796 KB Output is correct
4 Correct 862 ms 74980 KB Output is correct
5 Correct 390 ms 36680 KB Output is correct
6 Correct 1729 ms 140556 KB Output is correct
7 Correct 90 ms 13984 KB Output is correct
8 Correct 1747 ms 140584 KB Output is correct
9 Correct 88 ms 14028 KB Output is correct
10 Correct 854 ms 76780 KB Output is correct
11 Correct 244 ms 29132 KB Output is correct
12 Correct 184 ms 22140 KB Output is correct
13 Correct 178 ms 21952 KB Output is correct
14 Correct 1195 ms 77552 KB Output is correct
15 Correct 1144 ms 77628 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Execution timed out 4064 ms 75076 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 1 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 21 ms 820 KB Output is correct
6 Correct 28 ms 468 KB Output is correct
7 Correct 16 ms 468 KB Output is correct
8 Correct 31 ms 444 KB Output is correct
9 Correct 25 ms 716 KB Output is correct
10 Correct 16 ms 1048 KB Output is correct
11 Correct 24 ms 972 KB Output is correct
12 Correct 23 ms 768 KB Output is correct
13 Correct 29 ms 496 KB Output is correct
14 Correct 10 ms 724 KB Output is correct
15 Correct 24 ms 644 KB Output is correct
16 Correct 18 ms 468 KB Output is correct
17 Correct 20 ms 596 KB Output is correct
18 Correct 27 ms 476 KB Output is correct
19 Correct 19 ms 844 KB Output is correct
20 Correct 22 ms 792 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 873 ms 75012 KB Output is correct
23 Correct 343 ms 34796 KB Output is correct
24 Correct 862 ms 74980 KB Output is correct
25 Correct 390 ms 36680 KB Output is correct
26 Correct 1729 ms 140556 KB Output is correct
27 Correct 90 ms 13984 KB Output is correct
28 Correct 1747 ms 140584 KB Output is correct
29 Correct 88 ms 14028 KB Output is correct
30 Correct 854 ms 76780 KB Output is correct
31 Correct 244 ms 29132 KB Output is correct
32 Correct 184 ms 22140 KB Output is correct
33 Correct 178 ms 21952 KB Output is correct
34 Correct 1195 ms 77552 KB Output is correct
35 Correct 1144 ms 77628 KB Output is correct
36 Correct 997 ms 78224 KB Output is correct
37 Correct 500 ms 35868 KB Output is correct
38 Correct 491 ms 35980 KB Output is correct
39 Correct 982 ms 78200 KB Output is correct
40 Correct 452 ms 35536 KB Output is correct
41 Correct 1839 ms 140760 KB Output is correct
42 Correct 1828 ms 140916 KB Output is correct
43 Correct 174 ms 14536 KB Output is correct
44 Correct 206 ms 14140 KB Output is correct
45 Correct 908 ms 73468 KB Output is correct
46 Correct 933 ms 74976 KB Output is correct
47 Correct 293 ms 26172 KB Output is correct
48 Correct 291 ms 22464 KB Output is correct
49 Correct 234 ms 22216 KB Output is correct
50 Correct 1277 ms 78184 KB Output is correct
51 Correct 1177 ms 78020 KB Output is correct
52 Correct 1274 ms 77816 KB Output is correct
53 Correct 1 ms 340 KB Output is correct
54 Execution timed out 4082 ms 36440 KB Time limit exceeded
55 Halted 0 ms 0 KB -