Submission #699515

#	Time	Username	Problem	Language	Result	Execution time	Memory
699515		He_Huanglu	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	1552 ms	100568 KiB

sortbooks

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 5;
int n, m, ans[N], t[4 * N], a[N], _l[N], _k[N];
vector <int> que[N];
stack <int> st;

void upd(int i, int l, int r, int pos, int val)
{
    if(l == r)
    {
        t[i] = val;
        return ;
    }
    int mid = l + r >> 1;
    if(pos <= mid) upd(i << 1, l, mid, pos, val);
    else upd(i << 1 | 1, mid + 1, r, pos, val);
    t[i] = max(t[i << 1], t[i << 1 | 1]);
}

int get(int i, int l, int r, int u, int v)
{
    if(l > v || u > r) return 0;
    if(u <= l && r <= v) return t[i];
    int mid = l + r >> 1;
    return max(get(i << 1, l, mid, u, v), get(i << 1 | 1, mid + 1, r, u, v));
}

main ()
{
    cin.tie(0)->sync_with_stdio(0);
    if(fopen("task.inp", "r"))
    {
        freopen("task.inp", "r", stdin);
        freopen("wa.out", "w", stdout);
    }
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= m; i++)
    {
        int r; cin >> _l[i] >> r >> _k[i];
        que[r].push_back(i);
    }
    for(int i = 1; i <= n; i++)
    {
        while (!st.empty() && a[st.top()] <= a[i]) st.pop();
        if(!st.empty()) upd(1, 1, n, st.top(), a[st.top()] + a[i]);
        for(int j : que[i])
        {
            int l = _l[j], k = _k[j];
            ans[j] = (get(1, 1, n, l, i) <= k) ? 1 : 0;
        }
        st.push(i);
    }
    for(int i = 1; i <= m; i++) cout << ans[i] << "\n";
}

Compilation message (stderr)

sortbooks.cpp: In function 'void upd(int, int, int, int, int)':
sortbooks.cpp:16:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   16 |     int mid = l + r >> 1;
      |               ~~^~~
sortbooks.cpp: In function 'int get(int, int, int, int, int)':
sortbooks.cpp:26:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   26 |     int mid = l + r >> 1;
      |               ~~^~~
sortbooks.cpp: At global scope:
sortbooks.cpp:30:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   30 | main ()
      | ^~~~
sortbooks.cpp: In function 'int main()':
sortbooks.cpp:35:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |         freopen("task.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:36:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |         freopen("wa.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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