oj.uz

Submission #486759

# Submission time Handle Problem Language Result Execution time Memory
486759 2021-11-12T17:57:40 Z Urvuk3 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
100 / 100
 1243 ms 101024 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long
const ll MAXN=1e6+3,MAXA=5e6+5,INF=1e9,LINF=1e18;
#define fi first
#define se second
#define pll pair<ll,ll>
#define pii pair<int,int>
#define mid (l+r)/2
#define sz(a) int((a).size())
#define all(a) a.begin(),a.end()
#define mod 1000000007LL
#define pb push_back
#define endl "\n"
#define PRINT(x) cerr<<#x<<'-'<<x<<endl<<flush;
#define getunique(v) {sort(all(v)); v.erase(unique(all(v)), v.end());}
#define pb push_back
#define pf push_front
#define ppf pop_front
#define ppb pop_back
#define PRINTvec(x) { cerr<<#x<<"-"; for(auto xi:x) cerr<<xi<<" "; cerr<<endl; }

ll n,m,k,x,y,z,res=0,l,r,idx;
vector<int> a;
ifstream input;
ofstream output;
int seg[4*MAXN];

#ifdef ONLINE_JUDGE
    #define input cin
    #define output cout
#endif

struct kveri{
    int l,r,idx,k;
    void input(){
        cin>>l>>r>>k;
    }
    kveri(int l1,int r1,int idx1,int k1){
        l=l1; r=r1; idx=idx1; k=k1;
    }
};

vector<kveri> q[MAXN];

void update(int node,int l,int r,int idx,int val){
    if(l==r){
        seg[node]=val;
        return;
    }
    if(idx<=mid) update(2*node,l,mid,idx,val);
    else update(2*node+1,mid+1,r,idx,val);
    seg[node]=max(seg[2*node],seg[2*node+1]);
}

int query(int node,int l,int r,int L,int R){
    if(L<=l && r<=R) return seg[node];
    int ret=0;
    if(L<=mid) ret=max(ret,query(2*node,l,mid,L,R));
    if(R>mid) ret=max(ret,query(2*node+1,mid+1,r,L,R));
    return ret;
}

void solve(){
    cin>>n>>m;
    a.resize(n+1);
    vector<int> ans(m+1);
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=m;i++){
        cin>>l>>r>>k;
        idx=i;
        q[r].pb(kveri(l,r,idx,k));
    }
    stack<int> s;
    for(int i=1;i<=n;i++){
        while(!s.empty() && a[s.top()]<=a[i]){
            s.pop();
        }
        if(!s.empty()){
            update(1,1,n,s.top(),a[s.top()]+a[i]);
        }
        for(kveri kv:q[i]){
            if(query(1,1,n,kv.l,i)<=kv.k){
                ans[kv.idx]=1;
            }
        }
        s.push(i);
    }
    for(int i=1;i<=m;i++){
        cout<<ans[i]<<endl;
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    #ifndef ONLINE_JUDGE
        input.open("D:\\UROS\\Programiranje\\input.in",ios::in);
	output.open("D:\\UROS\\Programiranje\\output.out",ios::out|ios::trunc);
    #endif
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    int t;
    //cin>>t;
    t=1;
    while(t--){
        solve();
    }
    return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23792 KB Output is correct
2 Correct 14 ms 23812 KB Output is correct
3 Correct 12 ms 23816 KB Output is correct
4 Correct 13 ms 23756 KB Output is correct
5 Correct 12 ms 23816 KB Output is correct
6 Correct 13 ms 23816 KB Output is correct
7 Correct 13 ms 23800 KB Output is correct
8 Correct 16 ms 23780 KB Output is correct
9 Correct 13 ms 23820 KB Output is correct
10 Correct 13 ms 23720 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23792 KB Output is correct
2 Correct 14 ms 23812 KB Output is correct
3 Correct 12 ms 23816 KB Output is correct
4 Correct 13 ms 23756 KB Output is correct
5 Correct 12 ms 23816 KB Output is correct
6 Correct 13 ms 23816 KB Output is correct
7 Correct 13 ms 23800 KB Output is correct
8 Correct 16 ms 23780 KB Output is correct
9 Correct 13 ms 23820 KB Output is correct
10 Correct 13 ms 23720 KB Output is correct
11 Correct 15 ms 23948 KB Output is correct
12 Correct 15 ms 24012 KB Output is correct
13 Correct 14 ms 24012 KB Output is correct
14 Correct 16 ms 24088 KB Output is correct
15 Correct 15 ms 24204 KB Output is correct
16 Correct 15 ms 24056 KB Output is correct
17 Correct 15 ms 24076 KB Output is correct
18 Correct 17 ms 24012 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1239 ms 68124 KB Output is correct
2 Correct 1188 ms 68688 KB Output is correct
3 Correct 1217 ms 68632 KB Output is correct
4 Correct 1223 ms 68640 KB Output is correct
5 Correct 995 ms 60472 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 29320 KB Output is correct
2 Correct 86 ms 29192 KB Output is correct
3 Correct 82 ms 28220 KB Output is correct
4 Correct 90 ms 28336 KB Output is correct
5 Correct 94 ms 28376 KB Output is correct
6 Correct 69 ms 28056 KB Output is correct
7 Correct 70 ms 28100 KB Output is correct
8 Correct 95 ms 28328 KB Output is correct
9 Correct 45 ms 27172 KB Output is correct
10 Correct 73 ms 29060 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23792 KB Output is correct
2 Correct 14 ms 23812 KB Output is correct
3 Correct 12 ms 23816 KB Output is correct
4 Correct 13 ms 23756 KB Output is correct
5 Correct 12 ms 23816 KB Output is correct
6 Correct 13 ms 23816 KB Output is correct
7 Correct 13 ms 23800 KB Output is correct
8 Correct 16 ms 23780 KB Output is correct
9 Correct 13 ms 23820 KB Output is correct
10 Correct 13 ms 23720 KB Output is correct
11 Correct 15 ms 23948 KB Output is correct
12 Correct 15 ms 24012 KB Output is correct
13 Correct 14 ms 24012 KB Output is correct
14 Correct 16 ms 24088 KB Output is correct
15 Correct 15 ms 24204 KB Output is correct
16 Correct 15 ms 24056 KB Output is correct
17 Correct 15 ms 24076 KB Output is correct
18 Correct 17 ms 24012 KB Output is correct
19 Correct 221 ms 39504 KB Output is correct
20 Correct 198 ms 39536 KB Output is correct
21 Correct 196 ms 39124 KB Output is correct
22 Correct 226 ms 39012 KB Output is correct
23 Correct 177 ms 39008 KB Output is correct
24 Correct 157 ms 37060 KB Output is correct
25 Correct 149 ms 36972 KB Output is correct
26 Correct 172 ms 37224 KB Output is correct
27 Correct 169 ms 37280 KB Output is correct
28 Correct 163 ms 37220 KB Output is correct
29 Correct 176 ms 37404 KB Output is correct
30 Correct 177 ms 37444 KB Output is correct
31 Correct 174 ms 37608 KB Output is correct
32 Correct 170 ms 37412 KB Output is correct
33 Correct 227 ms 37484 KB Output is correct
34 Correct 153 ms 36492 KB Output is correct
35 Correct 147 ms 36496 KB Output is correct
36 Correct 141 ms 36252 KB Output is correct
37 Correct 141 ms 36260 KB Output is correct
38 Correct 155 ms 36556 KB Output is correct
39 Correct 171 ms 36372 KB Output is correct
40 Correct 123 ms 34300 KB Output is correct
41 Correct 157 ms 35612 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23792 KB Output is correct
2 Correct 14 ms 23812 KB Output is correct
3 Correct 12 ms 23816 KB Output is correct
4 Correct 13 ms 23756 KB Output is correct
5 Correct 12 ms 23816 KB Output is correct
6 Correct 13 ms 23816 KB Output is correct
7 Correct 13 ms 23800 KB Output is correct
8 Correct 16 ms 23780 KB Output is correct
9 Correct 13 ms 23820 KB Output is correct
10 Correct 13 ms 23720 KB Output is correct
11 Correct 15 ms 23948 KB Output is correct
12 Correct 15 ms 24012 KB Output is correct
13 Correct 14 ms 24012 KB Output is correct
14 Correct 16 ms 24088 KB Output is correct
15 Correct 15 ms 24204 KB Output is correct
16 Correct 15 ms 24056 KB Output is correct
17 Correct 15 ms 24076 KB Output is correct
18 Correct 17 ms 24012 KB Output is correct
19 Correct 1239 ms 68124 KB Output is correct
20 Correct 1188 ms 68688 KB Output is correct
21 Correct 1217 ms 68632 KB Output is correct
22 Correct 1223 ms 68640 KB Output is correct
23 Correct 995 ms 60472 KB Output is correct
24 Correct 108 ms 29320 KB Output is correct
25 Correct 86 ms 29192 KB Output is correct
26 Correct 82 ms 28220 KB Output is correct
27 Correct 90 ms 28336 KB Output is correct
28 Correct 94 ms 28376 KB Output is correct
29 Correct 69 ms 28056 KB Output is correct
30 Correct 70 ms 28100 KB Output is correct
31 Correct 95 ms 28328 KB Output is correct
32 Correct 45 ms 27172 KB Output is correct
33 Correct 73 ms 29060 KB Output is correct
34 Correct 221 ms 39504 KB Output is correct
35 Correct 198 ms 39536 KB Output is correct
36 Correct 196 ms 39124 KB Output is correct
37 Correct 226 ms 39012 KB Output is correct
38 Correct 177 ms 39008 KB Output is correct
39 Correct 157 ms 37060 KB Output is correct
40 Correct 149 ms 36972 KB Output is correct
41 Correct 172 ms 37224 KB Output is correct
42 Correct 169 ms 37280 KB Output is correct
43 Correct 163 ms 37220 KB Output is correct
44 Correct 176 ms 37404 KB Output is correct
45 Correct 177 ms 37444 KB Output is correct
46 Correct 174 ms 37608 KB Output is correct
47 Correct 170 ms 37412 KB Output is correct
48 Correct 227 ms 37484 KB Output is correct
49 Correct 153 ms 36492 KB Output is correct
50 Correct 147 ms 36496 KB Output is correct
51 Correct 141 ms 36252 KB Output is correct
52 Correct 141 ms 36260 KB Output is correct
53 Correct 155 ms 36556 KB Output is correct
54 Correct 171 ms 36372 KB Output is correct
55 Correct 123 ms 34300 KB Output is correct
56 Correct 157 ms 35612 KB Output is correct
57 Correct 1214 ms 101024 KB Output is correct
58 Correct 1200 ms 100928 KB Output is correct
59 Correct 1164 ms 100116 KB Output is correct
60 Correct 1198 ms 99208 KB Output is correct
61 Correct 1146 ms 99108 KB Output is correct
62 Correct 1243 ms 98960 KB Output is correct
63 Correct 845 ms 88916 KB Output is correct
64 Correct 1014 ms 88880 KB Output is correct
65 Correct 1228 ms 91012 KB Output is correct
66 Correct 1072 ms 91068 KB Output is correct
67 Correct 1088 ms 90904 KB Output is correct
68 Correct 1094 ms 91748 KB Output is correct
69 Correct 1047 ms 91772 KB Output is correct
70 Correct 1206 ms 91632 KB Output is correct
71 Correct 1154 ms 91592 KB Output is correct
72 Correct 1074 ms 91620 KB Output is correct
73 Correct 731 ms 84032 KB Output is correct
74 Correct 751 ms 84828 KB Output is correct
75 Correct 747 ms 84264 KB Output is correct
76 Correct 766 ms 84540 KB Output is correct
77 Correct 710 ms 84204 KB Output is correct
78 Correct 914 ms 86968 KB Output is correct
79 Correct 719 ms 75556 KB Output is correct
80 Correct 911 ms 81436 KB Output is correct