oj.uz

Submission #597884

# Submission time Handle Problem Language Result Execution time Memory
597884 2022-07-17T04:02:49 Z qwerasdfzxcl Fish 2 (JOI22_fish2) C++14
8 / 100
 368 ms 18840 KB 
#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);
        }
    }
}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 update(int x, int y){
    ///todo
}

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

    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);

    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

fish2.cpp: In function 'int main()':
fish2.cpp:203:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  203 |     for (auto &[l, r]:P) tree4.update(1, 1, n, l, r);
      |                ^
fish2.cpp:186:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  186 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
fish2.cpp:187:33: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  187 |     for (int 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:209:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  209 |         scanf("%d %d %d", &op, &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 9684 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 6 ms 9712 KB Output is correct
2 Correct 278 ms 18284 KB Output is correct
3 Correct 360 ms 18260 KB Output is correct
4 Correct 283 ms 18324 KB Output is correct
5 Correct 368 ms 18052 KB Output is correct
6 Correct 81 ms 18312 KB Output is correct
7 Correct 206 ms 17044 KB Output is correct
8 Correct 89 ms 18360 KB Output is correct
9 Correct 172 ms 16968 KB Output is correct
10 Correct 190 ms 17220 KB Output is correct
11 Correct 256 ms 17200 KB Output is correct
12 Correct 91 ms 17504 KB Output is correct
13 Correct 118 ms 17488 KB Output is correct
14 Correct 94 ms 18840 KB Output is correct
15 Correct 106 ms 18748 KB Output is correct

Subtask #3
0 / 12.0

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

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9712 KB Output is correct
2 Correct 278 ms 18284 KB Output is correct
3 Correct 360 ms 18260 KB Output is correct
4 Correct 283 ms 18324 KB Output is correct
5 Correct 368 ms 18052 KB Output is correct
6 Correct 81 ms 18312 KB Output is correct
7 Correct 206 ms 17044 KB Output is correct
8 Correct 89 ms 18360 KB Output is correct
9 Correct 172 ms 16968 KB Output is correct
10 Correct 190 ms 17220 KB Output is correct
11 Correct 256 ms 17200 KB Output is correct
12 Correct 91 ms 17504 KB Output is correct
13 Correct 118 ms 17488 KB Output is correct
14 Correct 94 ms 18840 KB Output is correct
15 Correct 106 ms 18748 KB Output is correct
16 Incorrect 5 ms 9712 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9712 KB Output is correct
2 Correct 278 ms 18284 KB Output is correct
3 Correct 360 ms 18260 KB Output is correct
4 Correct 283 ms 18324 KB Output is correct
5 Correct 368 ms 18052 KB Output is correct
6 Correct 81 ms 18312 KB Output is correct
7 Correct 206 ms 17044 KB Output is correct
8 Correct 89 ms 18360 KB Output is correct
9 Correct 172 ms 16968 KB Output is correct
10 Correct 190 ms 17220 KB Output is correct
11 Correct 256 ms 17200 KB Output is correct
12 Correct 91 ms 17504 KB Output is correct
13 Correct 118 ms 17488 KB Output is correct
14 Correct 94 ms 18840 KB Output is correct
15 Correct 106 ms 18748 KB Output is correct
16 Incorrect 5 ms 9684 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

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