oj.uz

Submission #596878

# Submission time Handle Problem Language Result Execution time Memory
596878 2022-07-15T08:38:04 Z 이동현(#8450) Fish 2 (JOI22_fish2) C++17
8 / 100
 715 ms 11656 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize9("Ofast")
#pragma GCC optimize("unroll-loops")
#define int long long
using namespace std;

const int NS = (int)1e5 + 4;
int acnt[NS];
vector<long long> stk[NS];
int stkN;
int ans[NS];
int ansN;

struct mxSeg{
    int n;
    vector<int> tr;
    mxSeg(){}
    mxSeg(int n):n(n + 4){
        tr.resize(n * 4);
    }
    void push(int x, int s, int e, int pos, int val){
        if(s == e){
            tr[x] = val;
            return;
        }
        int m = s + e >> 1;
        if(pos <= m) push(x * 2, s, m, pos, val);
        else push(x * 2 + 1, m + 1, e, pos, val);
        tr[x] = max(tr[x * 2], tr[x * 2 + 1]);
    }
    int get(int x, int s, int e, int fs, int fe){
        if(fe < s || fs > e) return -(int)1e18;
        if(fs <= s && fe >= e) return tr[x];
        int m = s + e >> 1;
        return max(get(x * 2, s, m, fs, fe), get(x * 2 + 1, m + 1, e, fs, fe));
    }
};

struct mnSeg{
    int n;
    vector<int> tr;
    mnSeg(){}
    mnSeg(int n):n(n + 4){
        tr.resize(n * 4);
    }
    void push(int x, int s, int e, int pos, int val){
        if(s == e){
            tr[x] = val;
            return;
        }
        int m = s + e >> 1;
        if(pos <= m) push(x * 2, s, m, pos, val);
        else push(x * 2 + 1, m + 1, e, pos, val);
        tr[x] = min(tr[x * 2], tr[x * 2 + 1]);
    }
    int get(int x, int s, int e, int fs, int fe){
        if(fe < s || fs > e) return (int)1e18;
        if(fs <= s && fe >= e) return tr[x];
        int m = s + e >> 1;
        return min(get(x * 2, s, m, fs, fe), get(x * 2 + 1, m + 1, e, fs, fe));
    }
};

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n; cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; ++i){
        cin >> a[i];
    }
    int q; cin >> q;
    int x = 0, y = n - 1;
    for(int i = x; i <= y; ++i) acnt[i] = 0;
    stkN = ansN = 0;
    stk[stkN++] = {(int)1e9, x - 1, 0};
    long long sum = 0;
    for(int i = x; i <= y; ++i){
        while(stk[stkN - 1][0] < a[i]){
            --stkN;
        }
        if(sum - stk[stkN - 1][2] < a[i]){
            while(ansN && ans[ansN - 1] > stk[stkN - 1][1]){
                --ansN;
            }
        }
        sum += a[i];
        stk[stkN++] = {a[i], i, sum};
        ans[ansN++] = i;
    }
    for(int i = 0; i < ansN; ++i) ++acnt[ans[i]];
    stkN = ansN = 0;
    stk[stkN++] = {(int)1e9, y + 1, 0};
    sum = 0;
    for(int i = y; i >= x; --i){
        while(stk[stkN - 1][0] < a[i]){
            --stkN;
        }
        if(sum - stk[stkN - 1][2] < a[i]){
            while(ansN && ans[ansN - 1] < stk[stkN - 1][1]){
                --ansN;
            }
        }
        sum += a[i];
        stk[stkN++] = {a[i], i, sum};
        ans[ansN++] = i;
    }
    for(int i = 0; i < ansN; ++i) ++acnt[ans[i]];
    int dap = 0;
    for(int i = 0; i < n; ++i) acnt[i] = (acnt[i] == 2);
    for(int i = 1; i < n; ++i){
        acnt[i] += acnt[i - 1];
    }
    mxSeg mxtr(n + 4);
    mnSeg mntr(n + 4);
    for(int i = 0; i < n; ++i){
        if(i){
            a[i] += a[i - 1];
            mntr.push(1, 0, n - 1, i, 2 * a[i - 1] - a[i]);
            mxtr.push(1, 0, n - 1, i, 2 * a[i] - a[i - 1]);
        }
        else{
            mntr.push(1, 0, n - 1, i, -a[i]);
            mxtr.push(1, 0, n - 1, i, 2 * a[i]);
        }
    }
    while(q--){
        int t, x, y; cin >> t >> x >> y;
        --x, --y;
        int low = x - 1, high = y, mid;
        while(low < high){
            mid = low + high + 1 >> 1;
            if(mntr.get(1, 0, n - 1, mid, y) < (x ? a[x - 1] : 0)){
                low = mid;
            }
            else{
                high = mid - 1;
            }
        }

        int low2 = x, high2 = y + 1, mid2;
        while(low2 < high2){
            mid2 = low2 + high2 >> 1;
            if(mxtr.get(1, 0, n - 1, x, mid2) > a[y]){
                high2 = mid2;
            }
            else{
                low2 = mid2 + 1;
            }
        }
        if(low2 == y + 1) --low2;
        if(low == x - 1) ++low;
        int dap = 0;
        if(low <= low2){
            dap = acnt[low2] - (low ? acnt[low - 1] : 0);
        }
        cout << dap << '\n';
    }
    return 0;
}

Compilation message

fish2.cpp:3: warning: ignoring '#pragma GCC optimize9' [-Wunknown-pragmas]
    3 | #pragma GCC optimize9("Ofast")
      | 
fish2.cpp: In member function 'void mxSeg::push(long long int, long long int, long long int, long long int, long long int)':
fish2.cpp:27:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 |         int m = s + e >> 1;
      |                 ~~^~~
fish2.cpp: In member function 'long long int mxSeg::get(long long int, long long int, long long int, long long int, long long int)':
fish2.cpp:35:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |         int m = s + e >> 1;
      |                 ~~^~~
fish2.cpp: In member function 'void mnSeg::push(long long int, long long int, long long int, long long int, long long int)':
fish2.cpp:52:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |         int m = s + e >> 1;
      |                 ~~^~~
fish2.cpp: In member function 'long long int mnSeg::get(long long int, long long int, long long int, long long int, long long int)':
fish2.cpp:60:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   60 |         int m = s + e >> 1;
      |                 ~~^~~
fish2.cpp: In function 'int main()':
fish2.cpp:133:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  133 |             mid = low + high + 1 >> 1;
      |                   ~~~~~~~~~~~^~~
fish2.cpp:144:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  144 |             mid2 = low2 + high2 >> 1;
      |                    ~~~~~^~~~~~~
fish2.cpp:110:9: warning: unused variable 'dap' [-Wunused-variable]
  110 |     int dap = 0;
      |         ^~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2644 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 2 ms 2644 KB Output is correct
2 Correct 35 ms 11288 KB Output is correct
3 Correct 35 ms 10524 KB Output is correct
4 Correct 36 ms 10836 KB Output is correct
5 Correct 32 ms 10576 KB Output is correct
6 Correct 35 ms 11096 KB Output is correct
7 Correct 32 ms 10708 KB Output is correct
8 Correct 35 ms 11028 KB Output is correct
9 Correct 29 ms 10504 KB Output is correct
10 Correct 30 ms 10516 KB Output is correct
11 Correct 27 ms 10452 KB Output is correct
12 Correct 29 ms 10900 KB Output is correct
13 Correct 29 ms 10836 KB Output is correct
14 Correct 30 ms 11040 KB Output is correct
15 Correct 32 ms 11024 KB Output is correct

Subtask #3
0 / 12.0

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

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 35 ms 11288 KB Output is correct
3 Correct 35 ms 10524 KB Output is correct
4 Correct 36 ms 10836 KB Output is correct
5 Correct 32 ms 10576 KB Output is correct
6 Correct 35 ms 11096 KB Output is correct
7 Correct 32 ms 10708 KB Output is correct
8 Correct 35 ms 11028 KB Output is correct
9 Correct 29 ms 10504 KB Output is correct
10 Correct 30 ms 10516 KB Output is correct
11 Correct 27 ms 10452 KB Output is correct
12 Correct 29 ms 10900 KB Output is correct
13 Correct 29 ms 10836 KB Output is correct
14 Correct 30 ms 11040 KB Output is correct
15 Correct 32 ms 11024 KB Output is correct
16 Correct 2 ms 2772 KB Output is correct
17 Incorrect 715 ms 11656 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 35 ms 11288 KB Output is correct
3 Correct 35 ms 10524 KB Output is correct
4 Correct 36 ms 10836 KB Output is correct
5 Correct 32 ms 10576 KB Output is correct
6 Correct 35 ms 11096 KB Output is correct
7 Correct 32 ms 10708 KB Output is correct
8 Correct 35 ms 11028 KB Output is correct
9 Correct 29 ms 10504 KB Output is correct
10 Correct 30 ms 10516 KB Output is correct
11 Correct 27 ms 10452 KB Output is correct
12 Correct 29 ms 10900 KB Output is correct
13 Correct 29 ms 10836 KB Output is correct
14 Correct 30 ms 11040 KB Output is correct
15 Correct 32 ms 11024 KB Output is correct
16 Runtime error 4 ms 5208 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

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