oj.uz

답안 #539322

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
539322 2022-03-18T17:32:09 Z Evang Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
100 / 100
 1194 ms 95308 KB 
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;

#ifdef _DEBUG
#define dout(x) clog << "Line " << __LINE__ << ": " << #x << "=" << (x) << el
#else
#define dout(x)
#endif

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define uid(a,b) uniform_int_distribution<int>(a,b)(rng)

#define ins insert
#define ssize(x) (int((x).size()))
#define bs(args...) binary_search(args)
#define lb(args...) lower_bound(args)
#define ub(args...) upper_bound(args)
#define all(x) (x).begin(),(x).end()
#define mp(a, b) make_pair(a, b)
#define mt(args...) make_tuple(args)
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second
#define die exit(0)

template<typename T>
using vc = vector<T>;
template<typename T>
using uset = unordered_set<T>;
template<typename A, typename B>
using umap = unordered_map<A, B>;
template<typename T, typename Comp>
using pq = std::priority_queue<T, vc<T>, Comp>;
template<typename T>
using maxpq = pq<T, less<T>>;
template<typename T>
using minpq = pq<T, greater<T>>;
template<typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

using db = double;
using ld = long double;
using ll = long long;
using ull = unsigned long long;
using pi = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vc<int>;
using vll = vc<ll>;
using vpi = vc<pi>;
using vpll = vc<pll>;
using str = string;

constexpr char el = '\n';
constexpr char sp = ' ';
constexpr int inf = 0x3f3f3f3f;
constexpr ll llinf = 0x3f3f3f3f3f3f3f3fLL;
// ---------------------------------------------------------------------


const int N = 1e6+5;
const int Q = N;
int n, q, a[N], bit[N];
vi qs[N];
bitset<N> ans;
struct evan {
    int l, r, k;
} query[Q];

void upd(int i, int x){
    while(i>0){
        bit[i] = max(bit[i], x);
        i -= i&-i;
    }
}

int qry(int i){
    int ans = 0;
    while(i<=n){
        ans = max(ans, bit[i]);
        i += i&-i;
    }
    return ans;
}

signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cout << fixed; clog << fixed; clog << unitbuf;
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    freopen("debug.txt", "w", stderr);
#else
    //freopen(".in", "r", stdin);
    //freopen(".out", "w", stdout);
#endif

    cin >> n >> q;
    a[0] = inf;
    for(int i = 1; i <= n; ++i)
        cin >> a[i];
    for(int i = 0; i < q; ++i){
        cin >> query[i].l >> query[i].r >> query[i].k;
        qs[query[i].r].pb(i);
    }

    vi st{0};
    for(int i = 1; i <= n; ++i){
        while(a[st.back()]<=a[i])
            st.pop_back();
        upd(st.back(), a[i]+a[st.back()]);
        st.pb(i);
        for(int j: qs[i])
            ans[j] = qry(query[j].l) <= query[j].k;
    }
    for(int i = 0; i < q; ++i)
        cout << ans[i] << el;
}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 23728 KB Output is correct
2 Correct 12 ms 23832 KB Output is correct
3 Correct 13 ms 23764 KB Output is correct
4 Correct 13 ms 23764 KB Output is correct
5 Correct 13 ms 23836 KB Output is correct
6 Correct 14 ms 23752 KB Output is correct
7 Correct 14 ms 23792 KB Output is correct
8 Correct 14 ms 23764 KB Output is correct
9 Correct 14 ms 23764 KB Output is correct
10 Correct 15 ms 23812 KB Output is correct

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 23728 KB Output is correct
2 Correct 12 ms 23832 KB Output is correct
3 Correct 13 ms 23764 KB Output is correct
4 Correct 13 ms 23764 KB Output is correct
5 Correct 13 ms 23836 KB Output is correct
6 Correct 14 ms 23752 KB Output is correct
7 Correct 14 ms 23792 KB Output is correct
8 Correct 14 ms 23764 KB Output is correct
9 Correct 14 ms 23764 KB Output is correct
10 Correct 15 ms 23812 KB Output is correct
11 Correct 15 ms 23960 KB Output is correct
12 Correct 16 ms 23968 KB Output is correct
13 Correct 15 ms 24096 KB Output is correct
14 Correct 17 ms 24068 KB Output is correct
15 Correct 18 ms 24352 KB Output is correct
16 Correct 16 ms 24100 KB Output is correct
17 Correct 15 ms 24088 KB Output is correct
18 Correct 17 ms 24020 KB Output is correct

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 977 ms 63348 KB Output is correct
2 Correct 1058 ms 63432 KB Output is correct
3 Correct 1025 ms 63440 KB Output is correct
4 Correct 1194 ms 63448 KB Output is correct
5 Correct 1178 ms 59440 KB Output is correct

Subtask #4
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 91 ms 27588 KB Output is correct
2 Correct 62 ms 26884 KB Output is correct
3 Correct 77 ms 26940 KB Output is correct
4 Correct 75 ms 27148 KB Output is correct
5 Correct 87 ms 27196 KB Output is correct
6 Correct 63 ms 26124 KB Output is correct
7 Correct 58 ms 26092 KB Output is correct
8 Correct 73 ms 27036 KB Output is correct
9 Correct 50 ms 26944 KB Output is correct
10 Correct 75 ms 28768 KB Output is correct

Subtask #5
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 23728 KB Output is correct
2 Correct 12 ms 23832 KB Output is correct
3 Correct 13 ms 23764 KB Output is correct
4 Correct 13 ms 23764 KB Output is correct
5 Correct 13 ms 23836 KB Output is correct
6 Correct 14 ms 23752 KB Output is correct
7 Correct 14 ms 23792 KB Output is correct
8 Correct 14 ms 23764 KB Output is correct
9 Correct 14 ms 23764 KB Output is correct
10 Correct 15 ms 23812 KB Output is correct
11 Correct 15 ms 23960 KB Output is correct
12 Correct 16 ms 23968 KB Output is correct
13 Correct 15 ms 24096 KB Output is correct
14 Correct 17 ms 24068 KB Output is correct
15 Correct 18 ms 24352 KB Output is correct
16 Correct 16 ms 24100 KB Output is correct
17 Correct 15 ms 24088 KB Output is correct
18 Correct 17 ms 24020 KB Output is correct
19 Correct 205 ms 37920 KB Output is correct
20 Correct 190 ms 37880 KB Output is correct
21 Correct 196 ms 36032 KB Output is correct
22 Correct 160 ms 36084 KB Output is correct
23 Correct 168 ms 35984 KB Output is correct
24 Correct 149 ms 35020 KB Output is correct
25 Correct 143 ms 35012 KB Output is correct
26 Correct 158 ms 35944 KB Output is correct
27 Correct 172 ms 35948 KB Output is correct
28 Correct 186 ms 36256 KB Output is correct
29 Correct 179 ms 37192 KB Output is correct
30 Correct 214 ms 37188 KB Output is correct
31 Correct 167 ms 37056 KB Output is correct
32 Correct 168 ms 37072 KB Output is correct
33 Correct 175 ms 37012 KB Output is correct
34 Correct 145 ms 34712 KB Output is correct
35 Correct 142 ms 34744 KB Output is correct
36 Correct 139 ms 34504 KB Output is correct
37 Correct 134 ms 34516 KB Output is correct
38 Correct 147 ms 34736 KB Output is correct
39 Correct 176 ms 35620 KB Output is correct
40 Correct 148 ms 34060 KB Output is correct
41 Correct 182 ms 35064 KB Output is correct

Subtask #6
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 23728 KB Output is correct
2 Correct 12 ms 23832 KB Output is correct
3 Correct 13 ms 23764 KB Output is correct
4 Correct 13 ms 23764 KB Output is correct
5 Correct 13 ms 23836 KB Output is correct
6 Correct 14 ms 23752 KB Output is correct
7 Correct 14 ms 23792 KB Output is correct
8 Correct 14 ms 23764 KB Output is correct
9 Correct 14 ms 23764 KB Output is correct
10 Correct 15 ms 23812 KB Output is correct
11 Correct 15 ms 23960 KB Output is correct
12 Correct 16 ms 23968 KB Output is correct
13 Correct 15 ms 24096 KB Output is correct
14 Correct 17 ms 24068 KB Output is correct
15 Correct 18 ms 24352 KB Output is correct
16 Correct 16 ms 24100 KB Output is correct
17 Correct 15 ms 24088 KB Output is correct
18 Correct 17 ms 24020 KB Output is correct
19 Correct 977 ms 63348 KB Output is correct
20 Correct 1058 ms 63432 KB Output is correct
21 Correct 1025 ms 63440 KB Output is correct
22 Correct 1194 ms 63448 KB Output is correct
23 Correct 1178 ms 59440 KB Output is correct
24 Correct 91 ms 27588 KB Output is correct
25 Correct 62 ms 26884 KB Output is correct
26 Correct 77 ms 26940 KB Output is correct
27 Correct 75 ms 27148 KB Output is correct
28 Correct 87 ms 27196 KB Output is correct
29 Correct 63 ms 26124 KB Output is correct
30 Correct 58 ms 26092 KB Output is correct
31 Correct 73 ms 27036 KB Output is correct
32 Correct 50 ms 26944 KB Output is correct
33 Correct 75 ms 28768 KB Output is correct
34 Correct 205 ms 37920 KB Output is correct
35 Correct 190 ms 37880 KB Output is correct
36 Correct 196 ms 36032 KB Output is correct
37 Correct 160 ms 36084 KB Output is correct
38 Correct 168 ms 35984 KB Output is correct
39 Correct 149 ms 35020 KB Output is correct
40 Correct 143 ms 35012 KB Output is correct
41 Correct 158 ms 35944 KB Output is correct
42 Correct 172 ms 35948 KB Output is correct
43 Correct 186 ms 36256 KB Output is correct
44 Correct 179 ms 37192 KB Output is correct
45 Correct 214 ms 37188 KB Output is correct
46 Correct 167 ms 37056 KB Output is correct
47 Correct 168 ms 37072 KB Output is correct
48 Correct 175 ms 37012 KB Output is correct
49 Correct 145 ms 34712 KB Output is correct
50 Correct 142 ms 34744 KB Output is correct
51 Correct 139 ms 34504 KB Output is correct
52 Correct 134 ms 34516 KB Output is correct
53 Correct 147 ms 34736 KB Output is correct
54 Correct 176 ms 35620 KB Output is correct
55 Correct 148 ms 34060 KB Output is correct
56 Correct 182 ms 35064 KB Output is correct
57 Correct 1043 ms 95256 KB Output is correct
58 Correct 1132 ms 95308 KB Output is correct
59 Correct 1034 ms 91032 KB Output is correct
60 Correct 997 ms 91068 KB Output is correct
61 Correct 1062 ms 91072 KB Output is correct
62 Correct 983 ms 91080 KB Output is correct
63 Correct 677 ms 79456 KB Output is correct
64 Correct 806 ms 79448 KB Output is correct
65 Correct 940 ms 86564 KB Output is correct
66 Correct 955 ms 86740 KB Output is correct
67 Correct 992 ms 87004 KB Output is correct
68 Correct 981 ms 91308 KB Output is correct
69 Correct 1012 ms 91520 KB Output is correct
70 Correct 1044 ms 90600 KB Output is correct
71 Correct 1006 ms 90648 KB Output is correct
72 Correct 1086 ms 90620 KB Output is correct
73 Correct 746 ms 77436 KB Output is correct
74 Correct 749 ms 78416 KB Output is correct
75 Correct 720 ms 77456 KB Output is correct
76 Correct 708 ms 77480 KB Output is correct
77 Correct 742 ms 77380 KB Output is correct
78 Correct 990 ms 84680 KB Output is correct
79 Correct 763 ms 74388 KB Output is correct
80 Correct 992 ms 81276 KB Output is correct