oj.uz

Submission #596890

# Submission time Handle Problem Language Result Execution time Memory
596890 2022-07-15T08:45:54 Z 이동현(#8450) Fish 2 (JOI22_fish2) C++17
8 / 100
 750 ms 11284 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;
    long long sum = 0;
    for(int i = x; i <= y; ++i){
        while(stkN && stk[stkN - 1][0] < a[i]){
            --stkN;
        }
        if(stkN && 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;
    sum = 0;
    for(int i = y; i >= x; --i){
        while(stkN && stk[stkN - 1][0] < a[i]){
            --stkN;
        }
        if(stkN && 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:131:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  131 |             mid = low + high + 1 >> 1;
      |                   ~~~~~~~~~~~^~~
fish2.cpp:142:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  142 |             mid2 = low2 + high2 >> 1;
      |                    ~~~~~^~~~~~~
fish2.cpp:108:9: warning: unused variable 'dap' [-Wunused-variable]
  108 |     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 1 ms 2644 KB Output is correct
2 Correct 31 ms 11284 KB Output is correct
3 Correct 29 ms 10580 KB Output is correct
4 Correct 31 ms 10836 KB Output is correct
5 Correct 28 ms 10520 KB Output is correct
6 Correct 39 ms 11028 KB Output is correct
7 Correct 29 ms 10708 KB Output is correct
8 Correct 34 ms 11092 KB Output is correct
9 Correct 32 ms 10708 KB Output is correct
10 Correct 39 ms 10452 KB Output is correct
11 Correct 34 ms 10464 KB Output is correct
12 Correct 37 ms 11052 KB Output is correct
13 Correct 31 ms 10880 KB Output is correct
14 Correct 34 ms 10964 KB Output is correct
15 Correct 32 ms 10896 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 1 ms 2644 KB Output is correct
2 Correct 31 ms 11284 KB Output is correct
3 Correct 29 ms 10580 KB Output is correct
4 Correct 31 ms 10836 KB Output is correct
5 Correct 28 ms 10520 KB Output is correct
6 Correct 39 ms 11028 KB Output is correct
7 Correct 29 ms 10708 KB Output is correct
8 Correct 34 ms 11092 KB Output is correct
9 Correct 32 ms 10708 KB Output is correct
10 Correct 39 ms 10452 KB Output is correct
11 Correct 34 ms 10464 KB Output is correct
12 Correct 37 ms 11052 KB Output is correct
13 Correct 31 ms 10880 KB Output is correct
14 Correct 34 ms 10964 KB Output is correct
15 Correct 32 ms 10896 KB Output is correct
16 Correct 1 ms 2644 KB Output is correct
17 Incorrect 750 ms 10856 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 31 ms 11284 KB Output is correct
3 Correct 29 ms 10580 KB Output is correct
4 Correct 31 ms 10836 KB Output is correct
5 Correct 28 ms 10520 KB Output is correct
6 Correct 39 ms 11028 KB Output is correct
7 Correct 29 ms 10708 KB Output is correct
8 Correct 34 ms 11092 KB Output is correct
9 Correct 32 ms 10708 KB Output is correct
10 Correct 39 ms 10452 KB Output is correct
11 Correct 34 ms 10464 KB Output is correct
12 Correct 37 ms 11052 KB Output is correct
13 Correct 31 ms 10880 KB Output is correct
14 Correct 34 ms 10964 KB Output is correct
15 Correct 32 ms 10896 KB Output is correct
16 Runtime error 4 ms 5204 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 -