Submission #1057974

#	Time	Username	Problem	Language	Result	Execution time	Memory
1057974		_shr104	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	77 / 100	2231 ms	262148 KiB

sortbooks

#include <bits/stdc++.h>
using namespace std; 
#pragma GCC optimize ("Ofast")
        int const mxN = 1e6+5;
        int n, pw; 
        vector<int> seg [4*mxN];
        int ans[4*mxN], a[4*mxN];
         
        void build ( int node, int l, int r) {
           if(l==r-1) { seg[node].push_back(a[l]); return; }
           int m = (l+r)/2;
           build(node*2+1, l, m) , build(node*2+2, m, r);
         
           seg[node] = seg[node*2+1];
           int maxi = seg[node].back();
         
           for(auto it:seg[node*2+2]) seg[node].push_back(it);
           sort(seg[node].begin(),seg[node].end());
           
           int ind = lower_bound(seg[node*2+2].begin(), seg[node*2+2].end(), maxi) - seg[node*2+2].begin(); ind--;
           if(ind<0) ans[node] = 0;
           else { ans[node] = seg[node*2+2][ind] + maxi; }
           ans[node] = max ({ans[node], ans[node*2+1], ans[node*2+2]});
        }
         
        int fin = 0, maxi = 0;
         
        void get ( int node, int l_n, int r_n, int l, int r) {
           if(l_n>=r || r_n<=l) return;
           if(l<=l_n && r>=r_n) {
              fin = max (fin, ans[node]);
              int ind = lower_bound(seg[node].begin(), seg[node].end(), maxi) - seg[node].begin(); ind--;
              if(ind>=0) {
                 fin = max ( fin, maxi+seg[node][ind]);
              }
              maxi = max ( maxi, seg[node].back());
              return;
           }
           int m = (l_n+r_n) / 2;
           get(node*2+1, l_n, m, l, r), get(node*2+2, m ,r_n, l, r);
        }
         
        signed main() {
           ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
           
           cin>>n;       int q; cin>>q;
     
           for(int i=0; i<n; i++) cin>>a[i];
           pw = (1<<(__lg(n-1)+1));
           build(0,0,pw);
         
           while(q--) {
              int x,y; cin>>x>>y; int k; cin >> k;
              x--;
              fin = 0, maxi = 0;
              get(0,0,pw,x,y);
              cout<<(fin <= k)<<'\n';
           }
           return 0;}

• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 13 / 13
• Subtask 4: 17 / 17
• Subtask 5: 30 / 30
• Subtask 6: 0 / 23