제출 #398989

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
398989		definitelynotmee	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++98	100 / 100	1689 ms	71660 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 resp{
    int l, r, v;
};
struct queries{
    int l, r, limit, v;
};

int tree[4*MAXN];

void update(int id, int l, int r, int q, int val){
    if(l > q || r < q)
        return;
    if(l == q && r == q){
        tree[id] = max(tree[id],val);
        return;
    }
    int e = id*2+1;
    int d = id*2+2;
    int m = (l+r)>>1;
    update(e,l,m,q,val);
    update(d,m+1,r,q,val);
    tree[id] = max(tree[e],tree[d]);
}

int query(int id, int l, int r, int ql, int qr){
    if(l > qr || r < ql)
        return 0;
    if(ql<=l && r <= qr){

        return tree[id];
    }
    int e = id*2+1;
    int d = id*2+2;
    int m = (l+r)>>1;
    return max(query(e,l,m,ql,qr), query(d,m+1,r,ql,qr));
}

int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n, m;
    cin >> n >> m;
    vector<int> v(n);
    vector<queries> q(m);
    for(int i = 0; i < n; i++) 
        cin >> v[i];
    for(int i = 0; i < m; i++)
        cin >> q[i].l >> q[i].r >> q[i].limit, q[i].l--, q[i].r--;

    vector<int> orderq(m);

    iota(orderq.begin(), orderq.end(), 0); 
    sort(orderq.begin(),orderq.end(), [&](int a, int b){
        return q[a].r < q[b].r;
    });

    vector<int> j(n,-1); // primeiro indice maior ou igual a v[i] à esquerda

    for(int i = 1; i < n; i++){
        j[i] = i-1;
        while(j[i] >= 0 && v[j[i]] <= v[i])
            j[i] = j[j[i]];

    }

    int ptr = 0;
    for(int i = 0; i < m; i++){
        queries &cur = q[orderq[i]];
        while(ptr <= cur.r){
            if(j[ptr]!=-1)
                update(0,0,n-1,j[ptr],v[ptr]+v[j[ptr]]);
            ptr++;
        }
        cur.v = (query(0,0,n-1, cur.l, cur.r) <= cur.limit);
    }
    for(queries i : q)
        cout << i.v << '\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: 23 / 23