oj.uz

Submission #683403

# Submission time Handle Problem Language Result Execution time Memory
683403 2023-01-18T10:30:29 Z FatihSolak Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
64 / 100
 2209 ms 262144 KB 
#include <bits/stdc++.h>
#define N 1000005
using namespace std;
int a[N];
int ans[N];
struct node{
    int val = 0,maxi = -1;
};
struct node2{
    int l = 0,r = 0, val = 0;
}tree[N*20];
vector<pair<int,int>> roots;
int cnt = 1;
int upd(int v,int tl,int tr,int pos,int val){
    if(tl == tr){
        int nw = ++cnt;
        tree[nw].val = tree[v].val + val;
        return nw;
    }
    int tm = (tl + tr)/2;
    if(pos <= tm){
        int nw = ++cnt;
        tree[nw].l = upd(tree[v].l,tl,tm,pos,val);
        tree[nw].r = tree[v].r;
        tree[nw].val = tree[tree[nw].l].val +  tree[tree[nw].r].val;
        return nw;
    }
    else{
        int nw = ++cnt;
        tree[nw].l = tree[v].l;
        tree[nw].r = upd(tree[v].r,tm+1,tr,pos,val);
        tree[nw].val = tree[tree[nw].l].val +  tree[tree[nw].r].val;
        return nw;
    }
}
int gett(int v,int tl,int tr,int l,int r){
    if(r < tl || tr < l){
        return 0;
    }
    if(l <= tl && tr <= r){
        return tree[v].val;
    }
    int tm = (tl + tr)/2;
    return gett(tree[v].l,tl,tm,l,r) + gett(tree[v].r,tm+1,tr,l,r);
}
struct SegTree{
    vector<node> t;
    int n;
    int k;
    SegTree(int sz){
        n = sz;
        t.assign(4*n,{0,-1});
        build(1,1,n);
    }
    node merge(node a,node b){
        node ret;
        ret.val = max(a.val,b.val);
        ret.maxi = max(a.maxi,b.maxi);
        return ret;
    }
    void build(int v,int tl,int tr){
        if(tl == tr){
            t[v].maxi = a[tl];
            return;
        }
        int tm = (tl + tr)/2;
        build(v*2,tl,tm);
        build(v*2+1,tm+1,tr);
        t[v] = merge(t[v*2],t[v*2+1]);
        for(int i = tm+1;i<=tr;i++){
            if(a[i] < t[v*2].maxi){
                t[v].val = max(t[v].val,t[v*2].maxi + a[i]);
            }
        }
    }
    node get(int v,int tl,int tr,int l,int r){
        if(tr < l || r < tl){
            return {0,-1};
        }
        if(l <= tl && tr <= r){
            return t[v];
        }
        int tm = (tl + tr)/2;
        node a = get(v*2,tl,tm,l,r);
        node b = get(v*2+1,tm+1,tr,l,r);
        int num = k+1 - a.maxi;
        if(num < a.maxi){
            int cnt = 0;
            int idx = upper_bound(roots.begin(),roots.end(),make_pair(num,0),greater<pair<int,int>>()) - roots.begin() - 1;
            if(roots[0].first >= num){
                cnt += gett(roots[idx].second,1,n,max(l,tm+1),min(r,tr));
            }
            idx = upper_bound(roots.begin(),roots.end(),make_pair(a.maxi,0),greater<pair<int,int>>()) - roots.begin() - 1;
            if(roots[0].first >= a.maxi)
                cnt -= gett(roots[idx].second,1,n,max(l,tm+1),min(r,tr));
            if(cnt)
                a.val = k+1;
        }
        return merge(a,b);
    }
    node get(int l,int r,int kk){
        k = kk;
        return get(1,1,n,l,r);
    }
};
void solve(){
    int n,m;
    cin >> n >> m;
    vector<int> cmp;
    for(int i = 1;i<=n;i++){
        cin >> a[i];
        cmp.push_back(i);
    }
    sort(cmp.begin(),cmp.end(),[&](int x,int y){
        return a[x] > a[y];
    });
    roots.push_back({a[cmp[0]],1});
    for(auto u:cmp){
        int tmp = roots.back().second;
        if(roots.back().first == a[u])
            roots.pop_back();
        roots.push_back({a[u],upd(tmp,1,n,u,1)});
    }
    SegTree t(n);
    for(int i = 1;i<=m;i++){
        int l,r,k;
        cin >> l >> r >> k;
        ans[i] = t.get(l,r,k).val <= k;
    }
    for(int i = 1;i<=m;i++){
        cout << ans[i] << '\n';
    }
}
    
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    #ifdef Local
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    #ifdef Local
    cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

Subtask #1
8.0 / 8.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 0 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #2
9.0 / 9.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 0 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 12 ms 596 KB Output is correct
12 Correct 13 ms 1428 KB Output is correct
13 Correct 15 ms 1364 KB Output is correct
14 Correct 27 ms 1468 KB Output is correct
15 Correct 23 ms 1472 KB Output is correct
16 Correct 13 ms 1364 KB Output is correct
17 Correct 5 ms 1236 KB Output is correct
18 Correct 5 ms 1364 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 1214 ms 262144 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 725 ms 25744 KB Output is correct
2 Correct 692 ms 25760 KB Output is correct
3 Correct 441 ms 25844 KB Output is correct
4 Correct 452 ms 25732 KB Output is correct
5 Correct 405 ms 25720 KB Output is correct
6 Correct 520 ms 25620 KB Output is correct
7 Correct 518 ms 25708 KB Output is correct
8 Correct 136 ms 25676 KB Output is correct
9 Correct 34 ms 984 KB Output is correct
10 Correct 115 ms 25660 KB Output is correct

Subtask #5
30.0 / 30.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 0 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 12 ms 596 KB Output is correct
12 Correct 13 ms 1428 KB Output is correct
13 Correct 15 ms 1364 KB Output is correct
14 Correct 27 ms 1468 KB Output is correct
15 Correct 23 ms 1472 KB Output is correct
16 Correct 13 ms 1364 KB Output is correct
17 Correct 5 ms 1236 KB Output is correct
18 Correct 5 ms 1364 KB Output is correct
19 Correct 2114 ms 54920 KB Output is correct
20 Correct 2187 ms 54936 KB Output is correct
21 Correct 2116 ms 54944 KB Output is correct
22 Correct 2117 ms 54856 KB Output is correct
23 Correct 2209 ms 54920 KB Output is correct
24 Correct 1275 ms 54896 KB Output is correct
25 Correct 1259 ms 55016 KB Output is correct
26 Correct 1286 ms 54996 KB Output is correct
27 Correct 1321 ms 54928 KB Output is correct
28 Correct 1359 ms 54904 KB Output is correct
29 Correct 1253 ms 55020 KB Output is correct
30 Correct 1266 ms 54960 KB Output is correct
31 Correct 1246 ms 54996 KB Output is correct
32 Correct 1321 ms 55004 KB Output is correct
33 Correct 1244 ms 54984 KB Output is correct
34 Correct 1318 ms 55052 KB Output is correct
35 Correct 1367 ms 55040 KB Output is correct
36 Correct 1225 ms 55008 KB Output is correct
37 Correct 1294 ms 55020 KB Output is correct
38 Correct 1338 ms 55040 KB Output is correct
39 Correct 862 ms 54836 KB Output is correct
40 Correct 178 ms 35408 KB Output is correct
41 Correct 259 ms 53348 KB Output is correct

Subtask #6
0 / 23.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 0 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 12 ms 596 KB Output is correct
12 Correct 13 ms 1428 KB Output is correct
13 Correct 15 ms 1364 KB Output is correct
14 Correct 27 ms 1468 KB Output is correct
15 Correct 23 ms 1472 KB Output is correct
16 Correct 13 ms 1364 KB Output is correct
17 Correct 5 ms 1236 KB Output is correct
18 Correct 5 ms 1364 KB Output is correct
19 Runtime error 1214 ms 262144 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -