oj.uz

Submission #919572

# Submission time Handle Problem Language Result Execution time Memory
919572 2024-02-01T07:17:44 Z manizare Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
64 / 100
 2492 ms 262148 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("O3,unroll-loops")
#define pb push_back
#define F first
#define S second 
#define all(a) a.begin(),a.end()
#define pii pair <int,int>
#define PII pair<pii , pii>
#define int long long 
#define sz(v) (int)v.size()
#define rep(i , a , b) for(int i=a;i <= (b);i++)
#define per(i , a , b) for(int i=a;i >= (b);i--)
#define deb(x) cout <<#x << " : " << x << "\n" ; 
using namespace std ;   
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 1e6+ 10 , maxm = 1e6+10 , lg = 18 , inf= 1e18 , mod = 998244353 ;
int par[maxn] , l[maxn] , ans[maxn ] , a[maxn] , L[maxn] , w[maxn] , mx[4*maxn] ;int n, q ;
vector <int> vec[maxn] , qu[maxn] , up[maxn] ;

int find(int v){
    if(par[v]==0)return v;
    return par[v] = find(par[v]) ;
}
void mrg(int x ,int y){ 
    if(x==y)return ;
    l[y] = l[x] ; 
    par[x] = y ; 
}
void upd(int x ,int w, int p =1 ,int l =1 , int r =n ){
    int mid = (l+r)/2 ,pl = p<< 1, pr =p<<1|1 ;
    if(x > r || l > x){
        return ;
    }
    if(l==r){
        mx[p] = w;
        return ;
    }
    upd(x,w,pl,l,mid);
    upd(x,w,pr,mid+1,r);
    mx[p] = max(mx[pl] , mx[pr]) ;
}
int que(int le, int ri ,int p = 1, int l = 1, int r= n){
    int mid = (l+r)/2 ,pl =p<<1 ,pr = p<<1|1 ;
    if(le > r || l > ri)return -inf;
    if(le <= l && r <= ri){
        return mx[p] ;
    }
    return max(que(le,ri,pl,l,mid),que(le,ri,pr,mid+1,r));
}

signed main(){
	ios_base::sync_with_stdio(false);cin.tie(0);
    cin >> n >> q ;
    vector <int> cm ;
    rep(i , 1, n){
        cin >> a[i] ;
        l[i] = i ;
        cm.pb(a[i]);
    }
    sort(all(cm) );
    cm.resize(unique(all(cm))-cm.begin());
    vector <pii> c ; 
    rep(i , 1, n){
        if(i!=n)c.pb({i,i+1}) ;
        a[i]=lower_bound(all(cm) , a[i]) - cm.begin() ;
        vec[a[i]].pb(i) ;
    }
    a[0] = a[n+1] = inf ;
    rep(i , 0 , sz(cm)-1){
        for(int x : vec[i]){
            if(a[x-1] < a[x]){
                c.pb({l[find(x-1)]-1 , x}) ;
            }
            if(a[x+1] < a[x]){
                c.pb({x,find(x+1)+1}) ;
            }
        }
        for(int x : vec[i]){
            if(a[x-1] <= a[x]){
                mrg(find(x-1) , find(x)) ;
            }
            if(a[x+1] <= a[x]){
                mrg(find(x) , find(x+1)) ;
            }
        }
    }
    vector <pii> c2 ;
    for(pii f : c){
        if(f.F <= 0 || f.S > n || a[f.F] <= a[f.S])continue ;
        up[f.S].pb(f.F) ;
    }
    rep(i , 1, q){
        int r ;
        cin >> L[i] >> r >> w[i]  ; 
        qu[r].pb(i) ;
    }
    rep(i , 1, n){
        for(int x : up[i]){
            upd(x , cm[a[x]] + cm[a[i]]) ;
        }
        for(int id : qu[i]){
            ans[id] = que(L[id] , i) ;
        }
    }
    rep(i ,1 , q){
        if(w[i] >= ans[i]){
            cout << 1 << "\n";
        }else{
            cout << 0 << "\n" ;
        }
    }
}
/*
    
*/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 82520 KB Output is correct
2 Correct 21 ms 82776 KB Output is correct
3 Correct 22 ms 82624 KB Output is correct
4 Correct 21 ms 82520 KB Output is correct
5 Correct 22 ms 82520 KB Output is correct
6 Correct 21 ms 82776 KB Output is correct
7 Correct 23 ms 82776 KB Output is correct
8 Correct 22 ms 82776 KB Output is correct
9 Correct 23 ms 82520 KB Output is correct
10 Correct 21 ms 82624 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 82520 KB Output is correct
2 Correct 21 ms 82776 KB Output is correct
3 Correct 22 ms 82624 KB Output is correct
4 Correct 21 ms 82520 KB Output is correct
5 Correct 22 ms 82520 KB Output is correct
6 Correct 21 ms 82776 KB Output is correct
7 Correct 23 ms 82776 KB Output is correct
8 Correct 22 ms 82776 KB Output is correct
9 Correct 23 ms 82520 KB Output is correct
10 Correct 21 ms 82624 KB Output is correct
11 Correct 24 ms 82776 KB Output is correct
12 Correct 25 ms 83288 KB Output is correct
13 Correct 25 ms 83416 KB Output is correct
14 Correct 27 ms 83288 KB Output is correct
15 Correct 26 ms 83460 KB Output is correct
16 Correct 26 ms 83280 KB Output is correct
17 Correct 26 ms 83036 KB Output is correct
18 Correct 24 ms 83036 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 2492 ms 262148 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 102508 KB Output is correct
2 Correct 117 ms 101380 KB Output is correct
3 Correct 85 ms 94836 KB Output is correct
4 Correct 87 ms 94792 KB Output is correct
5 Correct 88 ms 95036 KB Output is correct
6 Correct 69 ms 94228 KB Output is correct
7 Correct 69 ms 94152 KB Output is correct
8 Correct 89 ms 94920 KB Output is correct
9 Correct 46 ms 87240 KB Output is correct
10 Correct 78 ms 95012 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 82520 KB Output is correct
2 Correct 21 ms 82776 KB Output is correct
3 Correct 22 ms 82624 KB Output is correct
4 Correct 21 ms 82520 KB Output is correct
5 Correct 22 ms 82520 KB Output is correct
6 Correct 21 ms 82776 KB Output is correct
7 Correct 23 ms 82776 KB Output is correct
8 Correct 22 ms 82776 KB Output is correct
9 Correct 23 ms 82520 KB Output is correct
10 Correct 21 ms 82624 KB Output is correct
11 Correct 24 ms 82776 KB Output is correct
12 Correct 25 ms 83288 KB Output is correct
13 Correct 25 ms 83416 KB Output is correct
14 Correct 27 ms 83288 KB Output is correct
15 Correct 26 ms 83460 KB Output is correct
16 Correct 26 ms 83280 KB Output is correct
17 Correct 26 ms 83036 KB Output is correct
18 Correct 24 ms 83036 KB Output is correct
19 Correct 314 ms 127672 KB Output is correct
20 Correct 321 ms 127416 KB Output is correct
21 Correct 267 ms 127928 KB Output is correct
22 Correct 298 ms 127500 KB Output is correct
23 Correct 280 ms 126408 KB Output is correct
24 Correct 172 ms 116164 KB Output is correct
25 Correct 163 ms 117880 KB Output is correct
26 Correct 176 ms 117944 KB Output is correct
27 Correct 184 ms 117432 KB Output is correct
28 Correct 195 ms 117688 KB Output is correct
29 Correct 199 ms 117552 KB Output is correct
30 Correct 194 ms 117904 KB Output is correct
31 Correct 199 ms 118612 KB Output is correct
32 Correct 189 ms 117944 KB Output is correct
33 Correct 199 ms 118508 KB Output is correct
34 Correct 147 ms 117944 KB Output is correct
35 Correct 156 ms 119404 KB Output is correct
36 Correct 159 ms 118200 KB Output is correct
37 Correct 144 ms 118712 KB Output is correct
38 Correct 146 ms 118896 KB Output is correct
39 Correct 206 ms 119976 KB Output is correct
40 Correct 148 ms 110384 KB Output is correct
41 Correct 157 ms 109136 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 82520 KB Output is correct
2 Correct 21 ms 82776 KB Output is correct
3 Correct 22 ms 82624 KB Output is correct
4 Correct 21 ms 82520 KB Output is correct
5 Correct 22 ms 82520 KB Output is correct
6 Correct 21 ms 82776 KB Output is correct
7 Correct 23 ms 82776 KB Output is correct
8 Correct 22 ms 82776 KB Output is correct
9 Correct 23 ms 82520 KB Output is correct
10 Correct 21 ms 82624 KB Output is correct
11 Correct 24 ms 82776 KB Output is correct
12 Correct 25 ms 83288 KB Output is correct
13 Correct 25 ms 83416 KB Output is correct
14 Correct 27 ms 83288 KB Output is correct
15 Correct 26 ms 83460 KB Output is correct
16 Correct 26 ms 83280 KB Output is correct
17 Correct 26 ms 83036 KB Output is correct
18 Correct 24 ms 83036 KB Output is correct
19 Runtime error 2492 ms 262148 KB Memory limit exceeded
20 Halted 0 ms 0 KB -