Submission #533117

#	Time	Username	Problem	Language	Result	Execution time	Memory
533117		iliccmarko	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	64 / 100	3044 ms	73924 KiB

sortbooks

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"
#define INF 1000000000
#define LINF 10000000000000000LL
#define pb push_back
#define all(x) x.begin(), x.end()
#define len(s) (int)s.size()
#define test_case { int t; cin>>t; while(t--)solve(); }
#define single_case solve();
#define line cerr<<"----------"<<endl;
#define ios { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);  }
#define mod 1000000007LL
const int N = 1e6 + 5;
int seg[4*N];
int a[N], n, m;
int k[N];
int l[N], r[N];
int ans[N];
vector<int> upit[N];
stack<pair<int, int> > s;
pair<int, int> veci[N];
 
void update(int node, int l, int r, int pos, int x)
{
    if(l==r)
    {
        seg[node] = max(seg[node], x);
        return;
    }
    int mid = (l+r)/2;
    if(pos>mid) update(node*2+2, mid+1, r, pos, x);
    else update(node*2+1, l, mid, pos, x);
    seg[node] = max(seg[node*2+1], seg[node*2+2]);
}
 
int get(int node, int l, int r, int i, int j)
{
    if(i>r||j<l) return 0;
    if(i>=l&&j<=r) return seg[node];
    int mid = (i+j)/2;
    return max(get(node*2+1, l, r, i, mid), get(node*2+2, l, r, mid+1, j));
}
 
 
int main()
{
    cin>>n>>m;
    for(int i = 1;i<=n;i++) cin>>a[i];
    for(int i = 1;i<=m;i++) cin>>l[i]>>r[i]>>k[i], upit[r[i]].pb(i);
    s.push(make_pair(INF+2, 0));
    for(int i = 1;i<=n;i++)
    {
        while(a[i]>=s.top().first)
        {
            s.pop();
        }
        veci[i] = s.top();
        s.push(make_pair(a[i], i));
    }
    for(int i = 1;i<=n;i++)
    {
        if(veci[i].first!=INF+2)
        {
            update(0, 1, n, veci[i].second, veci[i].first+a[i]);
        }
        for(int x : upit[i])
        {
            int le = l[x];
            int ri = r[x];
            int w = get(0, le, ri, 1, n);
            cerr<<x<<' '<<len(upit[i]);
            if(w<=k[x]) ans[x] = 1;
        }
    }
 
    for(int i = 1;i<=m;i++) cout<<ans[i]<<endl;
 
 
 
    return 0;
}

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