Submission #166806

#	Time	Username	Problem	Language	Result	Execution time	Memory
166806		Yaroslaff	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	100 / 100	1143 ms	67948 KiB

sortbooks

#include <chrono>
#include <random>
#include <iostream>
#include <string>
#include <unordered_map>
#include <cstring>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <math.h>
#include <cstdio>
#include <stdio.h>
#include <queue>
#include <bitset>
#include <cstdlib>
#include <deque>
#include <cassert>
#include <stack>
using namespace std;
 
#define max3(a, b, c) max(a, max(b, c))
#define min3(a, b, c) min(a, min(b, c))
#define mp make_pair
#define f first
#define se second
#define pb push_back
#define ppb pop_back
#define ll long long
#define ull unsigned long long
#define cntbit(x) __builtin_popcount(x)
#define endl '\n'
#define uset unordered_set
#define umap unordered_map
#define pii pair<int, int>
#define ld long double
#define pll pair<long long, long long>
#define tm abc
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
const int mod = 1e9 + 7;
const int inf = 1e9;
const int N = 1e6 + 15;
int n, m, sz, a[N], st[N], ans[N], t[N << 1];
bool output[N];
 
struct query {
    int l, r, k, ind;
    bool operator < (const query &b) const {
        return r < b.r;
    }
} qs[N];
 
inline void update(int i, int val) {
    i += n;
    for(t[i] = max(t[i], val); i > 1; i >>= 1)
        t[i >> 1] = max(t[i >> 1], val);
}
 
inline int get(int l, int r) {
    int res = 0;
    for(l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
        if(l & 1)
            res = max(res, t[l++]);
        if(r & 1)
            res = max(res, t[--r]);
    }
    return res;
}
 
main() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    for(int i = 1; i <= m; ++i) {
        scanf("%d%d%d", &qs[i].l, &qs[i].r, &qs[i].k);
        qs[i].ind = i;
    }
    sort(qs + 1, qs + 1 + m);
    int i = 1, j = 1;
    for(; i <= n; ++i) {
        while(sz && a[st[sz - 1]] <= a[i])
            --sz;
        if(sz) {
            int ind_nearest = st[sz - 1];
            int sum = a[ind_nearest] + a[i];
 
            while(j <= m && qs[j].r < i) {
                ans[qs[j].ind] = max(ans[qs[j].ind], get(qs[j].l, n));
                ++j;
            }
            update(ind_nearest, sum);
        }
        st[sz++] = i;
    }
    while(j <= m) {
        ans[qs[j].ind] = max(ans[qs[j].ind], get(qs[j].l, n));
        ++j;
    }
    for(int i = 1; i <= m; ++i)
        if(ans[qs[i].ind] <= qs[i].k)
            output[qs[i].ind] = true;
    for(int i = 1; i <= m; ++i)
        puts(output[i] ? "1" : "0");
    return 0;
}

Compilation message (stderr)

sortbooks.cpp:72:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
sortbooks.cpp: In function 'int main()':
sortbooks.cpp:73:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~
sortbooks.cpp:75:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a[i]);
         ~~~~~^~~~~~~~~~~~~
sortbooks.cpp:77:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &qs[i].l, &qs[i].r, &qs[i].k);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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