Submission #1280553

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280553		jcelin	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	1046 ms	46556 KiB

sortbooks

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define piii pair<int,pii>
#define ppii pair<pii,pii>
#define F first
#define S second
#define pb push_back
const int N=1e6+10,off=(1<<20);
int n,q,a[N],b[N],tour[2*off+5];
ppii qq[N];
vector<piii>intervali;
bool ans[N];
 
void inpt(){
    cin >> n >> q;
    
    for(int i=0;i<n;i++)cin >> a[i];
    
    for(int i=0;i<q;i++){
        cin >> qq[i].F.F >> qq[i].F.S >> qq[i].S.F, 
        
        qq[i].S.S = i, qq[i].F.F--, qq[i].F.S--;
    }
    
    return;
}
 
void precompute(){
    vector<int>v;
    
    for(int i=0;i<n;i++){
        while(!v.empty() and a[v.back()] <= a[i])
            v.pop_back();
            
        if(!v.empty())
            intervali.pb({v.back(), {i, a[v.back()] + a[i]}});
        
        v.pb(i);
    }
    
    return;
}
 
void update(int node,int val){
    tour[node]=val;
    while(node /= 2)tour[node] = min(tour[node*2], tour[node*2+1]);
    return;
}
 
int query(int x,int y,int l,int r,int node){
    if(r<x or l>y)return 1e9;
    if(x <= l and r <= y)return tour[node];
    return min(query(x,y,l,(l+r)/2,node*2), query(x,y,(l+r)/2+1,r,node*2+1));
}
 
bool cmp3(piii x,piii y){
    return x.S.S < y.S.S;
}
 
bool cmp4(ppii x,ppii y){
    return x.S.F > y.S.F;
}
 
void calc(){
    sort(qq, qq+q, cmp4);
    sort(intervali.begin(), intervali.end(), cmp3);
    for(int i=0;i<q;i++){
        
        while(!intervali.empty() and intervali.back().S.S > qq[i].S.F){
            
            int ind = intervali.back().F;
            b[ind] = min(b[ind], intervali.back().S.F);
            update(ind+off, b[ind]);
            intervali.pop_back();
        }
        if(query(qq[i].F.F, qq[i].F.S, 0, off-1, 1) > qq[i].F.S)ans[qq[i].S.S] = 1;
    }
    return;
}
 
void Print(){
    for(int i=0;i<q;i++)cout << ans[i] << '\n';
    return;
}
 
void Reset(){
    intervali.clear();
    for(int i=0;i<n;i++)b[i]=1e9, update(i+off,1e9);
    return;
}
 
void solve(){
    inpt();
    Reset();
    precompute();
    calc();
    Print();
    return;
}
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t=1;
    //cin>>t;
    while(t--)solve();
    return 0;
}

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