Submission #651213

#	Time	Username	Problem	Language	Result	Execution time	Memory
651213		ck_platypus	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	13 / 100	2942 ms	127604 KiB

sortbooks

#include <iostream>
#include <string>
#include <cmath>
#include <vector>
#include <algorithm>
#include <utility>
#include <bitset>
#include <climits>
#include <set>
#include <map>
#include <iomanip>
#include <queue>
#include <cstring>
#include <fstream>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define pll pair<ll, ll>
#define plpll pair<ll, pll>
#define pii pair<int, int>
#define f first
#define s second
#define inf 1000000000000000000
#define endl '\n'

struct q{
    ll l, r, k, ind;
};
bool cmp(q a, q b){
    return a.r<b.r;
}
struct node{
	ll val;
	node *l, *r;
	node(){
		val=0;
		l=NULL;
		r=NULL;
	}
	void pull(){
		if(l==NULL && r==NULL){
			val=0;
		}else if(l==NULL){
			val=r->val;
		}else if(r==NULL){
			val=l->val;
		}else{
			val=max(l->val,r->val);
		}
	}
};
void modify(node* cur, ll l, ll r, ll ind, ll num){
	if(ind<l || ind>=r || l>=r) return;
	if(l==ind && r-l==1){
		cur->val=num;
		return;
	}
	ll mid=(l+r)/2;
	if(ind<mid){
		if(cur->l==NULL) cur->l=new node();
		modify(cur->l, l, mid, ind, num);
	}else{
		if(cur->r==NULL) cur->r=new node();
		modify(cur->r, mid, r, ind, num);
	}
	cur->pull();
	return;
}
ll query(node* cur, ll l, ll r, ll ql, ll qr){
	if(qr<=l || ql>=r || l>=r) return 0;
	if(ql<=l && qr>=r) return cur->val;
	ll mid=(l+r)/2;
	ll ret=0;
	if(cur->l!=NULL) ret=max(ret, query(cur->l, l, mid, ql, qr));
	if(cur->r!=NULL) ret=max(ret, query(cur->r, mid, r, ql, qr));
	return ret;
}
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    ll n, m;
    cin >> n >> m;
    node *root=new node();
    ll w[n];
    for(int i=0;i<n;i++) cin >> w[i];
    q qs[m];
    for(int i=0;i<m;i++) cin >> qs[i].l >> qs[i].r >> qs[i].k, qs[i].ind=i;
    sort(qs, qs+m, cmp);
    ll rr=0;
    ll stk[n], top=0, ttop=0;
    ll cool[n], ans[m];
    memset(ans, 0, sizeof(ans));
    memset(cool, 0, sizeof(cool));
    for(int i=0;i<n;i++){
        top=ttop;
        while(top>0 && w[i]<w[stk[top-1]]){
            top--;
            cool[stk[top]]=max(cool[stk[top]], w[i]+w[stk[top]]);
            modify(root, 0, n, stk[top], cool[stk[top]]);
        }
        stk[ttop++]=i;
        while(rr<m && qs[rr].r<=i+1){
            /*cout << rr << " " << i << endl;
            for(int j=0;j<n;j++) cout << cool[j] << " ";cout << endl;*/
            if(query(root, 0, n, qs[rr].l-1, qs[rr].r)<=qs[rr].k) ans[qs[rr].ind]=1;
            rr++;
        }
    }
    for(int i=0;i<m;i++) cout << ans[i] << endl;
    return 0;
}

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