oj.uz

답안 #533118

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
533118 2022-03-04T21:36:03 Z iliccmarko Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
100 / 100
 2467 ms 108344 KB 
#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);
            if(w<=k[x]) ans[x] = 1;
        }
    }
 
    for(int i = 1;i<=m;i++) cout<<ans[i]<<endl;
 
 
 
    return 0;
}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 23788 KB Output is correct
2 Correct 13 ms 23756 KB Output is correct
3 Correct 12 ms 23744 KB Output is correct
4 Correct 12 ms 23764 KB Output is correct
5 Correct 13 ms 23760 KB Output is correct
6 Correct 13 ms 23756 KB Output is correct
7 Correct 16 ms 23756 KB Output is correct
8 Correct 13 ms 23756 KB Output is correct
9 Correct 16 ms 23728 KB Output is correct
10 Correct 13 ms 23756 KB Output is correct

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 23788 KB Output is correct
2 Correct 13 ms 23756 KB Output is correct
3 Correct 12 ms 23744 KB Output is correct
4 Correct 12 ms 23764 KB Output is correct
5 Correct 13 ms 23760 KB Output is correct
6 Correct 13 ms 23756 KB Output is correct
7 Correct 16 ms 23756 KB Output is correct
8 Correct 13 ms 23756 KB Output is correct
9 Correct 16 ms 23728 KB Output is correct
10 Correct 13 ms 23756 KB Output is correct
11 Correct 16 ms 23944 KB Output is correct
12 Correct 20 ms 24016 KB Output is correct
13 Correct 19 ms 24068 KB Output is correct
14 Correct 21 ms 24140 KB Output is correct
15 Correct 21 ms 24012 KB Output is correct
16 Correct 20 ms 24032 KB Output is correct
17 Correct 20 ms 24020 KB Output is correct
18 Correct 21 ms 24012 KB Output is correct

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2401 ms 75436 KB Output is correct
2 Correct 2467 ms 84544 KB Output is correct
3 Correct 2381 ms 86048 KB Output is correct
4 Correct 2370 ms 108344 KB Output is correct
5 Correct 2257 ms 82604 KB Output is correct

Subtask #4
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 210 ms 29468 KB Output is correct
2 Correct 192 ms 28612 KB Output is correct
3 Correct 144 ms 28092 KB Output is correct
4 Correct 166 ms 28244 KB Output is correct
5 Correct 154 ms 28332 KB Output is correct
6 Correct 129 ms 26984 KB Output is correct
7 Correct 136 ms 26924 KB Output is correct
8 Correct 145 ms 28332 KB Output is correct
9 Correct 95 ms 26044 KB Output is correct
10 Correct 149 ms 28264 KB Output is correct

Subtask #5
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 23788 KB Output is correct
2 Correct 13 ms 23756 KB Output is correct
3 Correct 12 ms 23744 KB Output is correct
4 Correct 12 ms 23764 KB Output is correct
5 Correct 13 ms 23760 KB Output is correct
6 Correct 13 ms 23756 KB Output is correct
7 Correct 16 ms 23756 KB Output is correct
8 Correct 13 ms 23756 KB Output is correct
9 Correct 16 ms 23728 KB Output is correct
10 Correct 13 ms 23756 KB Output is correct
11 Correct 16 ms 23944 KB Output is correct
12 Correct 20 ms 24016 KB Output is correct
13 Correct 19 ms 24068 KB Output is correct
14 Correct 21 ms 24140 KB Output is correct
15 Correct 21 ms 24012 KB Output is correct
16 Correct 20 ms 24032 KB Output is correct
17 Correct 20 ms 24020 KB Output is correct
18 Correct 21 ms 24012 KB Output is correct
19 Correct 450 ms 34948 KB Output is correct
20 Correct 419 ms 34880 KB Output is correct
21 Correct 400 ms 33332 KB Output is correct
22 Correct 375 ms 33188 KB Output is correct
23 Correct 386 ms 33252 KB Output is correct
24 Correct 338 ms 31024 KB Output is correct
25 Correct 366 ms 31076 KB Output is correct
26 Correct 348 ms 31684 KB Output is correct
27 Correct 374 ms 31860 KB Output is correct
28 Correct 354 ms 32056 KB Output is correct
29 Correct 373 ms 33072 KB Output is correct
30 Correct 370 ms 32828 KB Output is correct
31 Correct 440 ms 32856 KB Output is correct
32 Correct 374 ms 32844 KB Output is correct
33 Correct 393 ms 32820 KB Output is correct
34 Correct 322 ms 30880 KB Output is correct
35 Correct 335 ms 30832 KB Output is correct
36 Correct 318 ms 30824 KB Output is correct
37 Correct 350 ms 30828 KB Output is correct
38 Correct 325 ms 30856 KB Output is correct
39 Correct 358 ms 33204 KB Output is correct
40 Correct 307 ms 31432 KB Output is correct
41 Correct 327 ms 32780 KB Output is correct

Subtask #6
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 23788 KB Output is correct
2 Correct 13 ms 23756 KB Output is correct
3 Correct 12 ms 23744 KB Output is correct
4 Correct 12 ms 23764 KB Output is correct
5 Correct 13 ms 23760 KB Output is correct
6 Correct 13 ms 23756 KB Output is correct
7 Correct 16 ms 23756 KB Output is correct
8 Correct 13 ms 23756 KB Output is correct
9 Correct 16 ms 23728 KB Output is correct
10 Correct 13 ms 23756 KB Output is correct
11 Correct 16 ms 23944 KB Output is correct
12 Correct 20 ms 24016 KB Output is correct
13 Correct 19 ms 24068 KB Output is correct
14 Correct 21 ms 24140 KB Output is correct
15 Correct 21 ms 24012 KB Output is correct
16 Correct 20 ms 24032 KB Output is correct
17 Correct 20 ms 24020 KB Output is correct
18 Correct 21 ms 24012 KB Output is correct
19 Correct 2401 ms 75436 KB Output is correct
20 Correct 2467 ms 84544 KB Output is correct
21 Correct 2381 ms 86048 KB Output is correct
22 Correct 2370 ms 108344 KB Output is correct
23 Correct 2257 ms 82604 KB Output is correct
24 Correct 210 ms 29468 KB Output is correct
25 Correct 192 ms 28612 KB Output is correct
26 Correct 144 ms 28092 KB Output is correct
27 Correct 166 ms 28244 KB Output is correct
28 Correct 154 ms 28332 KB Output is correct
29 Correct 129 ms 26984 KB Output is correct
30 Correct 136 ms 26924 KB Output is correct
31 Correct 145 ms 28332 KB Output is correct
32 Correct 95 ms 26044 KB Output is correct
33 Correct 149 ms 28264 KB Output is correct
34 Correct 450 ms 34948 KB Output is correct
35 Correct 419 ms 34880 KB Output is correct
36 Correct 400 ms 33332 KB Output is correct
37 Correct 375 ms 33188 KB Output is correct
38 Correct 386 ms 33252 KB Output is correct
39 Correct 338 ms 31024 KB Output is correct
40 Correct 366 ms 31076 KB Output is correct
41 Correct 348 ms 31684 KB Output is correct
42 Correct 374 ms 31860 KB Output is correct
43 Correct 354 ms 32056 KB Output is correct
44 Correct 373 ms 33072 KB Output is correct
45 Correct 370 ms 32828 KB Output is correct
46 Correct 440 ms 32856 KB Output is correct
47 Correct 374 ms 32844 KB Output is correct
48 Correct 393 ms 32820 KB Output is correct
49 Correct 322 ms 30880 KB Output is correct
50 Correct 335 ms 30832 KB Output is correct
51 Correct 318 ms 30824 KB Output is correct
52 Correct 350 ms 30828 KB Output is correct
53 Correct 325 ms 30856 KB Output is correct
54 Correct 358 ms 33204 KB Output is correct
55 Correct 307 ms 31432 KB Output is correct
56 Correct 327 ms 32780 KB Output is correct
57 Correct 2420 ms 89892 KB Output is correct
58 Correct 2410 ms 89932 KB Output is correct
59 Correct 2251 ms 86604 KB Output is correct
60 Correct 2224 ms 85572 KB Output is correct
61 Correct 2181 ms 86724 KB Output is correct
62 Correct 2208 ms 86404 KB Output is correct
63 Correct 1730 ms 72120 KB Output is correct
64 Correct 1694 ms 72036 KB Output is correct
65 Correct 1992 ms 77772 KB Output is correct
66 Correct 1960 ms 77692 KB Output is correct
67 Correct 1964 ms 78168 KB Output is correct
68 Correct 2049 ms 82360 KB Output is correct
69 Correct 2061 ms 82544 KB Output is correct
70 Correct 2056 ms 81508 KB Output is correct
71 Correct 2016 ms 81328 KB Output is correct
72 Correct 2084 ms 80340 KB Output is correct
73 Correct 1661 ms 70012 KB Output is correct
74 Correct 1701 ms 69844 KB Output is correct
75 Correct 1677 ms 69652 KB Output is correct
76 Correct 1669 ms 69360 KB Output is correct
77 Correct 1682 ms 68988 KB Output is correct
78 Correct 1764 ms 79964 KB Output is correct
79 Correct 1414 ms 82248 KB Output is correct
80 Correct 1677 ms 91332 KB Output is correct