oj.uz

Submission #793124

# Submission time Handle Problem Language Result Execution time Memory
793124 2023-07-25T14:10:55 Z hafo Index (COCI21_index) C++14
110 / 110
 1725 ms 84428 KB 
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define pb push_back
#define pa pair<int, int>
#define pall pair<ll, int>
#define fi first
#define se second
#define TASK "test"
#define Size(x) (int) x.size()
#define all(x) x.begin(), x.end()
using namespace std;

template<typename T1, typename T2> bool mini (T1 &a, T2 b) {if(a > b) a = b; else return 0; return 1;}
template<typename T1, typename T2> bool maxi (T1 &a, T2 b) {if(a < b) a = b; else return 0; return 1;}

const int MOD = 1e9 + 7;
const int LOG = 20;
const int maxn = 2e5 + 7;
const ll oo = 1e18 + 69;

int n, q, a[maxn], u, v;

struct state {
    int val, l, r;
    friend bool operator < (state a, state b) {
        return a.val < b.val;
    }

    friend bool operator > (state &a, state &b) {
        return a.val > b.val;
    }
};

struct ST {
    struct node {
        vector<state> x;
        friend node operator + (node &a, node &b) {
            node c;
            int i = 0, j = 0, i2 = 0, j2 = 0;
            while(i < Size(a.x) || j < Size(b.x)) {
                if(j == Size(b.x) || (i != Size(a.x) && a.x[i].val < b.x[j].val)) {
                    c.x.pb(a.x[i++]);
                    if(i2 < Size(a.x) && c.x.back() > a.x[i2]) i2 = i - 1;
                    if(j2 < Size(b.x) && c.x.back() > b.x[j2]) j2 = j;
                } else {
                    c.x.pb(b.x[j++]);
                    if(i2 < Size(a.x) && c.x.back() > a.x[i2]) i2 = i;
                    if(j2 < Size(b.x) && c.x.back() > b.x[j2]) j2 = j - 1;
                }   
                c.x.back().l = i2;
                c.x.back().r = j2;
            }
            return c;
        }
    };

    node st[4 * maxn];

    void build(int id, int l, int r) {
        if(l == r) {
            st[id].x.pb({a[l], 1, 1});
            return;
        }
        int mid = l + r >> 1;
        build(id << 1, l, mid);
        build(id << 1 | 1, mid + 1, r);
        st[id] = st[id << 1] + st[id << 1 | 1];
    }

    int get(int id, int l, int r, int u, int v, int x, int cur) {
        if(id == 1) cur = lower_bound(all(st[id].x), state({x, 0, 0})) - st[id].x.begin();
        if(r < u || l > v || cur == Size(st[id].x)) return 0;
        if(u <= l && r <= v) return Size(st[id].x) - cur;
        int mid = l + r >> 1;
        return get(id << 1, l, mid, u, v, x, st[id].x[cur].l) + get(id << 1 | 1, mid + 1, r, u, v, x, st[id].x[cur].r);
    }

} st;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    //freopen(TASK".inp", "r", stdin);
    //freopen(TASK".out", "w", stdout);

    cin>>n>>q;
    for(int i = 1; i <= n; i++) cin>>a[i];
    st.build(1, 1, n);

    while(q--) {
        cin>>u>>v;
        int l = 1, r = (v - u + 1), res = 0, mid;
        while(l <= r) {
            mid = l + r >> 1;
            if(st.get(1, 1, n, u, v, mid, 0) >= mid) {
                res = mid;
                l = mid + 1;
            } else r = mid - 1;
        }
        cout<<res<<"\n";
    }
    return 0;
}

Compilation message

index.cpp: In member function 'void ST::build(int, int, int)':
index.cpp:65:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |         int mid = l + r >> 1;
      |                   ~~^~~
index.cpp: In member function 'int ST::get(int, int, int, int, int, int, int)':
index.cpp:75:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   75 |         int mid = l + r >> 1;
      |                   ~~^~~
index.cpp: In function 'int main()':
index.cpp:96:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   96 |             mid = l + r >> 1;
      |                   ~~^~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19284 KB Output is correct
2 Correct 11 ms 19316 KB Output is correct
3 Correct 11 ms 19284 KB Output is correct
4 Correct 11 ms 19244 KB Output is correct
5 Correct 11 ms 19268 KB Output is correct
6 Correct 12 ms 19260 KB Output is correct
7 Correct 11 ms 19284 KB Output is correct
8 Correct 12 ms 19312 KB Output is correct
9 Correct 12 ms 19252 KB Output is correct
10 Correct 12 ms 19188 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19284 KB Output is correct
2 Correct 11 ms 19316 KB Output is correct
3 Correct 11 ms 19284 KB Output is correct
4 Correct 11 ms 19244 KB Output is correct
5 Correct 11 ms 19268 KB Output is correct
6 Correct 12 ms 19260 KB Output is correct
7 Correct 11 ms 19284 KB Output is correct
8 Correct 12 ms 19312 KB Output is correct
9 Correct 12 ms 19252 KB Output is correct
10 Correct 12 ms 19188 KB Output is correct
11 Correct 300 ms 34076 KB Output is correct
12 Correct 326 ms 34160 KB Output is correct
13 Correct 316 ms 34052 KB Output is correct
14 Correct 297 ms 34124 KB Output is correct
15 Correct 281 ms 34092 KB Output is correct
16 Correct 296 ms 34064 KB Output is correct
17 Correct 284 ms 34024 KB Output is correct
18 Correct 293 ms 34044 KB Output is correct
19 Correct 281 ms 34080 KB Output is correct
20 Correct 280 ms 34064 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19284 KB Output is correct
2 Correct 11 ms 19316 KB Output is correct
3 Correct 11 ms 19284 KB Output is correct
4 Correct 11 ms 19244 KB Output is correct
5 Correct 11 ms 19268 KB Output is correct
6 Correct 12 ms 19260 KB Output is correct
7 Correct 11 ms 19284 KB Output is correct
8 Correct 12 ms 19312 KB Output is correct
9 Correct 12 ms 19252 KB Output is correct
10 Correct 12 ms 19188 KB Output is correct
11 Correct 300 ms 34076 KB Output is correct
12 Correct 326 ms 34160 KB Output is correct
13 Correct 316 ms 34052 KB Output is correct
14 Correct 297 ms 34124 KB Output is correct
15 Correct 281 ms 34092 KB Output is correct
16 Correct 296 ms 34064 KB Output is correct
17 Correct 284 ms 34024 KB Output is correct
18 Correct 293 ms 34044 KB Output is correct
19 Correct 281 ms 34080 KB Output is correct
20 Correct 280 ms 34064 KB Output is correct
21 Correct 1651 ms 84228 KB Output is correct
22 Correct 1610 ms 84416 KB Output is correct
23 Correct 1633 ms 84356 KB Output is correct
24 Correct 1680 ms 84352 KB Output is correct
25 Correct 1648 ms 84260 KB Output is correct
26 Correct 1665 ms 84344 KB Output is correct
27 Correct 1628 ms 84264 KB Output is correct
28 Correct 1621 ms 84428 KB Output is correct
29 Correct 1629 ms 84272 KB Output is correct
30 Correct 1725 ms 84384 KB Output is correct