Submission #398845

#	Time	Username	Problem	Language	Result	Execution time	Memory
398845		definitelynotmee	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++98	64 / 100	1317 ms	262144 KiB

sortbooks

#include <bits/stdc++.h>
#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INFL = (1LL<<62)-1;
const int INF = (1<<30)-1;
const int MAXN = 1000001;
 
struct seg{
    int maxi = 0, best = 0;
    vector<int> v;
};
vector<seg> tree;
vector<vector<int>> sparse(25); // fiz com sparse table só pra n falar que eu fiz 2 segs
// guarda o primeiro indice a direita menor que v[i]
inline void merge(seg a, seg &b, seg&ret, bool type){
 
 
    
    
    ret.maxi = max(a.maxi, b.maxi);
    ret.best = max(a.best, b.best);
    auto it = lower_bound(b.v.begin(),b.v.end(),a.maxi);
    if(it!=b.v.begin()){
        it--;
        ret.best = max(ret.best, *it+a.maxi);
    }
    
    if(type){
        ret.v.resize(a.v.size() + b.v.size());
        merge(a.v.begin(),a.v.end(),b.v.begin(),b.v.end(),ret.v.begin());
    }
}
 
void build(int id, int l, int r, vector<int> & v){
    if(l==r){
        tree[id].maxi = v[l];
        tree[id].best = 0;
        tree[id].v.emplace_back(v[l]);
        return;
    }
    int e = 2*id+1;
    int d = 2*id+2;
    int m = (l+r)>>1;
    build(e,l,m,v);
    build(d,m+1,r,v);
    merge(tree[e],tree[d],tree[id],1);
}
 
void query(int id, int l, int r, int ql, int qr, seg&resp){
    if(l>qr || r < ql)
        return;
    if(ql<=l && r <= qr){
        merge(resp,tree[id],resp,0);
        return;
    }
    int e = 2*id+1;
    int d = 2*id+2;
    int m = (l+r)>>1;
    query(e,l,m,ql,qr,resp);
    query(d,m+1,r,ql,qr,resp);
}
 
int main(){
 
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n, m;
    cin >> n >> m;
    vector<int> v(n);
    for(int i = 0; i < n; i++)
        cin >> v[i];
    if(n<=2e5){
        tree.resize(4*n);
        build(0,0,n-1,v);
 
        for(int i = 0; i < m; i++){
            int a, b, c;
            cin >> a>> b >> c;
            a--, b--;
            seg cur;
            query(0,0,n-1,a,b,cur);
            cout <<  (cur.best <= c) << '\n';
        }
    } else {
        
        set<int,greater<int>> s;
        vector<int> order(n);
        iota(order.begin(),order.end(),0);
        sort(order.begin(),order.end(),[&](int a, int b){return v[a]<v[b];});
        sparse[0].resize(n);
        for(int i = 0; i < n; i++){
            
            auto aux = s.insert(order[i]);
            if(aux.first!=s.begin())
                aux.first--, sparse[0][order[i]] = *aux.first;
            else sparse[0][order[i]] = INF;
        }
        for(int i = 1; i < 25; i++){
            if(n - (1<<i-1) > 0)
                sparse[i].resize(n - (1<<i-1));
            for(int j = 0; j < n - (1<<i-1); j++){
                sparse[i][j] = min(sparse[i-1][j], sparse[i-1][j+(1<<i-1)]);
            }
        }
        for(int i = 0; i < m; i++){
            int a, b, c;
            cin >> a >> b >>c;
            a--;
            b--;
            int logg = log2(b-a);
            cout << (min(sparse[logg][a],sparse[logg][b-(1<<logg)+1]) > b) << '\n';
        }
    }
    return 0;
 
}

Compilation message (stderr)

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:106:25: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  106 |             if(n - (1<<i-1) > 0)
      |                        ~^~
sortbooks.cpp:107:43: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  107 |                 sparse[i].resize(n - (1<<i-1));
      |                                          ~^~
sortbooks.cpp:108:41: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  108 |             for(int j = 0; j < n - (1<<i-1); j++){
      |                                        ~^~
sortbooks.cpp:109:71: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  109 |                 sparse[i][j] = min(sparse[i-1][j], sparse[i-1][j+(1<<i-1)]);
      |                                                                      ~^~

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