oj.uz

Submission #332455

# Submission time Handle Problem Language Result Execution time Memory
332455 2020-12-02T15:55:00 Z mat_v Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
100 / 100
 1753 ms 86764 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>

#define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
#define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
#define mod 998244353
#define xx first
#define yy second
#define all(a) (a).begin(), (a).end()
#define pb push_back
#define ll long long
#define pii pair<int,int>
#define maxn 1000005

using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>,rb_tree_tag, tree_order_statistics_node_update> ordered_set;/// find_by_order(x)(x+1th) , order_of_key() (strictly less)
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());


int n,m;
int niz[maxn];
int ans[maxn];
struct kveri{
    int l;
    int w;
    int idx;
};

vector<kveri> upit[maxn];
int ri[maxn];
int li[maxn];

int seg[4 * maxn];

void init(int node, int l, int r){
    if(l == r){seg[node] = niz[l]; return;}
    int mid = (l + r) / 2;
    init(node * 2, l , mid);
    init(node * 2 + 1, mid + 1, r);
    seg[node] = max(seg[node * 2], seg[node * 2 + 1]);
}

int query(int node, int l, int r, int levo, int desno){
    if(r < levo || desno < l)return 0;
    if(l >= levo && r <= desno)return seg[node];
    int mid = (l + r) / 2;
    return max(query(node * 2, l, mid, levo, desno), query(node * 2 + 1, mid + 1, r, levo, desno));
}

int seg2[4 * maxn];

void update(int node, int l, int r, int poz, int val){
    if(l == r){
        seg2[node] = val;
        return;
    }
    int mid = (l + r) / 2;
    if(poz <= mid)update(node * 2, l, mid, poz, val);
    else update(node * 2 + 1, mid + 1, r, poz, val);
    seg2[node] = max(seg2[node * 2], seg2[node * 2 + 1]);
}
int query2(int node, int l, int r, int levo, int desno){
    if(r < levo || desno < l)return 0;
    if(l >= levo && r <= desno)return seg2[node];
    int mid = (l + r) / 2;
    return max(query2(node * 2, l, mid, levo, desno), query2(node * 2 + 1, mid + 1, r, levo, desno));
}

int val[maxn];
int main()
{

    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    ff(i,1,n)cin >> niz[i];
    init(1,1,n);
    ff(i,1,m){
        int x,y,z;
        cin >> x >> y >> z;
        upit[y].pb({x,z,i});
    }
    stack<pii> s;
    s.push({niz[1],1});
    ff(i,2,n){
        if(niz[i] < s.top().xx){
            li[i] = s.top().yy;
            s.push({niz[i],i});
            continue;
        }
        while(!s.empty() && s.top().xx <= niz[i])s.pop();
        if(!s.empty())li[i] = s.top().yy;
        s.push({niz[i], i});
    }
    ff(i,1,n){
        int gde = li[i];
        if(gde > 0){
            val[gde] = max(val[gde], niz[gde] + niz[i]);
            update(1,1,n,gde,val[gde]);
        }
        for(auto c:upit[i]){
            if(query2(1,1,n,c.l,i) <= c.w)ans[c.idx] = 1;
        }
    }
    ff(i,1,m)cout << ans[i] << "\n";
    return 0;
}

Compilation message

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
sortbooks.cpp:80:5: note: in expansion of macro 'ff'
   80 |     ff(i,1,n)cin >> niz[i];
      |     ^~
sortbooks.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
sortbooks.cpp:82:5: note: in expansion of macro 'ff'
   82 |     ff(i,1,m){
      |     ^~
sortbooks.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
sortbooks.cpp:89:5: note: in expansion of macro 'ff'
   89 |     ff(i,2,n){
      |     ^~
sortbooks.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
sortbooks.cpp:99:5: note: in expansion of macro 'ff'
   99 |     ff(i,1,n){
      |     ^~
sortbooks.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
sortbooks.cpp:109:5: note: in expansion of macro 'ff'
  109 |     ff(i,1,m)cout << ans[i] << "\n";
      |     ^~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23916 KB Output is correct
2 Correct 17 ms 23916 KB Output is correct
3 Correct 17 ms 23916 KB Output is correct
4 Correct 17 ms 23916 KB Output is correct
5 Correct 17 ms 23916 KB Output is correct
6 Correct 17 ms 23916 KB Output is correct
7 Correct 17 ms 23916 KB Output is correct
8 Correct 17 ms 23916 KB Output is correct
9 Correct 17 ms 23916 KB Output is correct
10 Correct 17 ms 23916 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23916 KB Output is correct
2 Correct 17 ms 23916 KB Output is correct
3 Correct 17 ms 23916 KB Output is correct
4 Correct 17 ms 23916 KB Output is correct
5 Correct 17 ms 23916 KB Output is correct
6 Correct 17 ms 23916 KB Output is correct
7 Correct 17 ms 23916 KB Output is correct
8 Correct 17 ms 23916 KB Output is correct
9 Correct 17 ms 23916 KB Output is correct
10 Correct 17 ms 23916 KB Output is correct
11 Correct 19 ms 24044 KB Output is correct
12 Correct 20 ms 24300 KB Output is correct
13 Correct 21 ms 24312 KB Output is correct
14 Correct 22 ms 24428 KB Output is correct
15 Correct 24 ms 24428 KB Output is correct
16 Correct 21 ms 24300 KB Output is correct
17 Correct 20 ms 24172 KB Output is correct
18 Correct 20 ms 24172 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1727 ms 75944 KB Output is correct
2 Correct 1753 ms 82028 KB Output is correct
3 Correct 1703 ms 82668 KB Output is correct
4 Correct 1746 ms 82560 KB Output is correct
5 Correct 1437 ms 73196 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 29804 KB Output is correct
2 Correct 128 ms 31596 KB Output is correct
3 Correct 118 ms 29932 KB Output is correct
4 Correct 136 ms 30060 KB Output is correct
5 Correct 122 ms 30056 KB Output is correct
6 Correct 98 ms 29164 KB Output is correct
7 Correct 96 ms 29164 KB Output is correct
8 Correct 110 ms 29860 KB Output is correct
9 Correct 63 ms 27300 KB Output is correct
10 Correct 113 ms 29860 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23916 KB Output is correct
2 Correct 17 ms 23916 KB Output is correct
3 Correct 17 ms 23916 KB Output is correct
4 Correct 17 ms 23916 KB Output is correct
5 Correct 17 ms 23916 KB Output is correct
6 Correct 17 ms 23916 KB Output is correct
7 Correct 17 ms 23916 KB Output is correct
8 Correct 17 ms 23916 KB Output is correct
9 Correct 17 ms 23916 KB Output is correct
10 Correct 17 ms 23916 KB Output is correct
11 Correct 19 ms 24044 KB Output is correct
12 Correct 20 ms 24300 KB Output is correct
13 Correct 21 ms 24312 KB Output is correct
14 Correct 22 ms 24428 KB Output is correct
15 Correct 24 ms 24428 KB Output is correct
16 Correct 21 ms 24300 KB Output is correct
17 Correct 20 ms 24172 KB Output is correct
18 Correct 20 ms 24172 KB Output is correct
19 Correct 319 ms 42348 KB Output is correct
20 Correct 322 ms 42348 KB Output is correct
21 Correct 270 ms 41708 KB Output is correct
22 Correct 272 ms 41708 KB Output is correct
23 Correct 269 ms 41708 KB Output is correct
24 Correct 224 ms 37996 KB Output is correct
25 Correct 229 ms 38068 KB Output is correct
26 Correct 253 ms 38380 KB Output is correct
27 Correct 250 ms 38252 KB Output is correct
28 Correct 270 ms 38380 KB Output is correct
29 Correct 262 ms 38764 KB Output is correct
30 Correct 265 ms 38784 KB Output is correct
31 Correct 263 ms 38764 KB Output is correct
32 Correct 281 ms 38764 KB Output is correct
33 Correct 264 ms 38764 KB Output is correct
34 Correct 206 ms 37484 KB Output is correct
35 Correct 214 ms 37484 KB Output is correct
36 Correct 201 ms 37356 KB Output is correct
37 Correct 197 ms 37356 KB Output is correct
38 Correct 207 ms 37516 KB Output is correct
39 Correct 240 ms 38180 KB Output is correct
40 Correct 215 ms 34848 KB Output is correct
41 Correct 229 ms 37028 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23916 KB Output is correct
2 Correct 17 ms 23916 KB Output is correct
3 Correct 17 ms 23916 KB Output is correct
4 Correct 17 ms 23916 KB Output is correct
5 Correct 17 ms 23916 KB Output is correct
6 Correct 17 ms 23916 KB Output is correct
7 Correct 17 ms 23916 KB Output is correct
8 Correct 17 ms 23916 KB Output is correct
9 Correct 17 ms 23916 KB Output is correct
10 Correct 17 ms 23916 KB Output is correct
11 Correct 19 ms 24044 KB Output is correct
12 Correct 20 ms 24300 KB Output is correct
13 Correct 21 ms 24312 KB Output is correct
14 Correct 22 ms 24428 KB Output is correct
15 Correct 24 ms 24428 KB Output is correct
16 Correct 21 ms 24300 KB Output is correct
17 Correct 20 ms 24172 KB Output is correct
18 Correct 20 ms 24172 KB Output is correct
19 Correct 1727 ms 75944 KB Output is correct
20 Correct 1753 ms 82028 KB Output is correct
21 Correct 1703 ms 82668 KB Output is correct
22 Correct 1746 ms 82560 KB Output is correct
23 Correct 1437 ms 73196 KB Output is correct
24 Correct 138 ms 29804 KB Output is correct
25 Correct 128 ms 31596 KB Output is correct
26 Correct 118 ms 29932 KB Output is correct
27 Correct 136 ms 30060 KB Output is correct
28 Correct 122 ms 30056 KB Output is correct
29 Correct 98 ms 29164 KB Output is correct
30 Correct 96 ms 29164 KB Output is correct
31 Correct 110 ms 29860 KB Output is correct
32 Correct 63 ms 27300 KB Output is correct
33 Correct 113 ms 29860 KB Output is correct
34 Correct 319 ms 42348 KB Output is correct
35 Correct 322 ms 42348 KB Output is correct
36 Correct 270 ms 41708 KB Output is correct
37 Correct 272 ms 41708 KB Output is correct
38 Correct 269 ms 41708 KB Output is correct
39 Correct 224 ms 37996 KB Output is correct
40 Correct 229 ms 38068 KB Output is correct
41 Correct 253 ms 38380 KB Output is correct
42 Correct 250 ms 38252 KB Output is correct
43 Correct 270 ms 38380 KB Output is correct
44 Correct 262 ms 38764 KB Output is correct
45 Correct 265 ms 38784 KB Output is correct
46 Correct 263 ms 38764 KB Output is correct
47 Correct 281 ms 38764 KB Output is correct
48 Correct 264 ms 38764 KB Output is correct
49 Correct 206 ms 37484 KB Output is correct
50 Correct 214 ms 37484 KB Output is correct
51 Correct 201 ms 37356 KB Output is correct
52 Correct 197 ms 37356 KB Output is correct
53 Correct 207 ms 37516 KB Output is correct
54 Correct 240 ms 38180 KB Output is correct
55 Correct 215 ms 34848 KB Output is correct
56 Correct 229 ms 37028 KB Output is correct
57 Correct 1752 ms 86404 KB Output is correct
58 Correct 1734 ms 86764 KB Output is correct
59 Correct 1621 ms 85100 KB Output is correct
60 Correct 1655 ms 85100 KB Output is correct
61 Correct 1677 ms 84900 KB Output is correct
62 Correct 1645 ms 85212 KB Output is correct
63 Correct 1157 ms 67380 KB Output is correct
64 Correct 1176 ms 67436 KB Output is correct
65 Correct 1402 ms 68332 KB Output is correct
66 Correct 1380 ms 68332 KB Output is correct
67 Correct 1448 ms 69100 KB Output is correct
68 Correct 1443 ms 70492 KB Output is correct
69 Correct 1436 ms 70396 KB Output is correct
70 Correct 1445 ms 69740 KB Output is correct
71 Correct 1435 ms 76396 KB Output is correct
72 Correct 1455 ms 70124 KB Output is correct
73 Correct 979 ms 64400 KB Output is correct
74 Correct 999 ms 64824 KB Output is correct
75 Correct 963 ms 64876 KB Output is correct
76 Correct 950 ms 64636 KB Output is correct
77 Correct 958 ms 64324 KB Output is correct
78 Correct 1247 ms 73116 KB Output is correct
79 Correct 909 ms 76380 KB Output is correct
80 Correct 1242 ms 81836 KB Output is correct