oj.uz

Submission #941694

# Submission time Handle Problem Language Result Execution time Memory
941694 2024-03-09T09:54:59 Z Baizho Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
100 / 100
 1176 ms 105868 KB 
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
  
#define ordered_set tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>
 
// #pragma GCC optimize("Ofast,unroll-loops,fast-math")
// #pragma GCC target("popcnt,sse3,avx")
 
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll,ll> pll;
 
#define sz size()
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define pb push_back
 
const int mod = ll(1e9)+7; //(b + (a%b)) % b (to mod -1%(10^9+7) correctly in c++ its -1 but its suppose to be 10^9+6
const ll MOD = 998244353;  // (a%mod)*(binpow(b,mod-2,mod) = (a/b)%mod
const int N = ll(1e6)+100;
const int M = ll(2e5) + 100;
const long long inf = 5e18;
//const long double eps = 1e-15L;
 
ll lcm(ll a, ll b) { return (a / __gcd(a,b))*b; }
 
ll binpow(ll a, ll b, ll m) { ll res=1; a %= m; while(b>0){ if(b&1)res=(res * a) % m; a=(a * a) % m; b/=2; } return res%m;}
 
void Freopen(string Key){ freopen((Key+".in").c_str(), "r", stdin); freopen((Key+".out").c_str(), "w", stdout); }

int n, m, w[N], t[N * 4], ql[N], qr[N], qk[N], ans[N];
vector<int> qu[N];

void update(int v, int tl, int tr, int p, int x) {
	if(tl == tr) {
		t[v] = max(t[v], x);
		return;
	}
	int tm = (tl + tr) / 2;
	if(p <= tm) update(v + v, tl, tm, p, x);
	else update(v + v + 1, tm + 1, tr, p, x);
	t[v] = max(t[v + v], t[v + v + 1]);
} 

int get(int v, int tl, int tr, int l, int r) {
	if(tl > r || l > tr) return 0;
	if(l <= tl && tr <= r) return t[v];
	int tm = (tl + tr) / 2;
	return max(get(v + v, tl, tm, l, r), get(v + v + 1, tm + 1, tr, l, r));  
}

void Baizho() {
	cin>>n>>m;
	for(int i = 1; i <= n; i ++) cin>>w[i];
	for(int i = 1; i <= m; i ++) {
		cin>>ql[i]>>qr[i]>>qk[i];
		qu[qr[i]].pb(i);
	}
	vector<int> vec;
	for(int i = 1; i <= n; i ++) {
		while(!vec.empty() && w[vec.back()] <= w[i]) vec.pop_back();
		if(!vec.empty()) update(1, 1, n, vec.back(), w[vec.back()] + w[i]);
		for(auto j : qu[i]) {
			if(get(1, 1, n, ql[j], qr[j]) <= qk[j]) ans[j] = 1;
		}
		vec.pb(i);
	}
	for(int i = 1; i <= m; i ++) cout<<ans[i]<<"\n";
}
 
signed main() {		
// 	Freopen("nondec");
    ios_base::sync_with_stdio(false);   
    cin.tie(0);cout.tie(0); 
//   	precalc();
   	
    int ttt = 1;
//    cin>>ttt;
 
    for(int i=1; i<=ttt; i++) {Baizho(); }
}

Compilation message

sortbooks.cpp: In function 'void Freopen(std::string)':
sortbooks.cpp:35:34: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 | void Freopen(string Key){ freopen((Key+".in").c_str(), "r", stdin); freopen((Key+".out").c_str(), "w", stdout); }
      |                           ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:35:76: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 | void Freopen(string Key){ freopen((Key+".in").c_str(), "r", stdin); freopen((Key+".out").c_str(), "w", stdout); }
      |                                                                     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 33372 KB Output is correct
2 Correct 7 ms 33372 KB Output is correct
3 Correct 7 ms 33372 KB Output is correct
4 Correct 7 ms 33368 KB Output is correct
5 Correct 7 ms 33372 KB Output is correct
6 Correct 6 ms 33464 KB Output is correct
7 Correct 7 ms 33368 KB Output is correct
8 Correct 6 ms 33624 KB Output is correct
9 Correct 7 ms 33496 KB Output is correct
10 Correct 7 ms 33372 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 33372 KB Output is correct
2 Correct 7 ms 33372 KB Output is correct
3 Correct 7 ms 33372 KB Output is correct
4 Correct 7 ms 33368 KB Output is correct
5 Correct 7 ms 33372 KB Output is correct
6 Correct 6 ms 33464 KB Output is correct
7 Correct 7 ms 33368 KB Output is correct
8 Correct 6 ms 33624 KB Output is correct
9 Correct 7 ms 33496 KB Output is correct
10 Correct 7 ms 33372 KB Output is correct
11 Correct 8 ms 33372 KB Output is correct
12 Correct 9 ms 35700 KB Output is correct
13 Correct 9 ms 35676 KB Output is correct
14 Correct 10 ms 33628 KB Output is correct
15 Correct 10 ms 35784 KB Output is correct
16 Correct 10 ms 33628 KB Output is correct
17 Correct 10 ms 33628 KB Output is correct
18 Correct 9 ms 33628 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1110 ms 73220 KB Output is correct
2 Correct 1117 ms 105868 KB Output is correct
3 Correct 1140 ms 105752 KB Output is correct
4 Correct 1100 ms 105636 KB Output is correct
5 Correct 953 ms 97620 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 38288 KB Output is correct
2 Correct 71 ms 39456 KB Output is correct
3 Correct 68 ms 36832 KB Output is correct
4 Correct 70 ms 37140 KB Output is correct
5 Correct 70 ms 37204 KB Output is correct
6 Correct 57 ms 37972 KB Output is correct
7 Correct 56 ms 37972 KB Output is correct
8 Correct 61 ms 36760 KB Output is correct
9 Correct 33 ms 35304 KB Output is correct
10 Correct 58 ms 36868 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 33372 KB Output is correct
2 Correct 7 ms 33372 KB Output is correct
3 Correct 7 ms 33372 KB Output is correct
4 Correct 7 ms 33368 KB Output is correct
5 Correct 7 ms 33372 KB Output is correct
6 Correct 6 ms 33464 KB Output is correct
7 Correct 7 ms 33368 KB Output is correct
8 Correct 6 ms 33624 KB Output is correct
9 Correct 7 ms 33496 KB Output is correct
10 Correct 7 ms 33372 KB Output is correct
11 Correct 8 ms 33372 KB Output is correct
12 Correct 9 ms 35700 KB Output is correct
13 Correct 9 ms 35676 KB Output is correct
14 Correct 10 ms 33628 KB Output is correct
15 Correct 10 ms 35784 KB Output is correct
16 Correct 10 ms 33628 KB Output is correct
17 Correct 10 ms 33628 KB Output is correct
18 Correct 9 ms 33628 KB Output is correct
19 Correct 172 ms 47696 KB Output is correct
20 Correct 189 ms 47700 KB Output is correct
21 Correct 152 ms 45904 KB Output is correct
22 Correct 152 ms 45652 KB Output is correct
23 Correct 148 ms 45648 KB Output is correct
24 Correct 123 ms 41492 KB Output is correct
25 Correct 121 ms 41424 KB Output is correct
26 Correct 135 ms 42320 KB Output is correct
27 Correct 133 ms 42356 KB Output is correct
28 Correct 137 ms 42576 KB Output is correct
29 Correct 145 ms 43580 KB Output is correct
30 Correct 145 ms 43856 KB Output is correct
31 Correct 143 ms 43380 KB Output is correct
32 Correct 147 ms 43604 KB Output is correct
33 Correct 147 ms 43408 KB Output is correct
34 Correct 120 ms 43152 KB Output is correct
35 Correct 115 ms 43092 KB Output is correct
36 Correct 125 ms 42948 KB Output is correct
37 Correct 115 ms 42940 KB Output is correct
38 Correct 122 ms 43236 KB Output is correct
39 Correct 130 ms 42604 KB Output is correct
40 Correct 103 ms 40908 KB Output is correct
41 Correct 127 ms 41672 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 33372 KB Output is correct
2 Correct 7 ms 33372 KB Output is correct
3 Correct 7 ms 33372 KB Output is correct
4 Correct 7 ms 33368 KB Output is correct
5 Correct 7 ms 33372 KB Output is correct
6 Correct 6 ms 33464 KB Output is correct
7 Correct 7 ms 33368 KB Output is correct
8 Correct 6 ms 33624 KB Output is correct
9 Correct 7 ms 33496 KB Output is correct
10 Correct 7 ms 33372 KB Output is correct
11 Correct 8 ms 33372 KB Output is correct
12 Correct 9 ms 35700 KB Output is correct
13 Correct 9 ms 35676 KB Output is correct
14 Correct 10 ms 33628 KB Output is correct
15 Correct 10 ms 35784 KB Output is correct
16 Correct 10 ms 33628 KB Output is correct
17 Correct 10 ms 33628 KB Output is correct
18 Correct 9 ms 33628 KB Output is correct
19 Correct 1110 ms 73220 KB Output is correct
20 Correct 1117 ms 105868 KB Output is correct
21 Correct 1140 ms 105752 KB Output is correct
22 Correct 1100 ms 105636 KB Output is correct
23 Correct 953 ms 97620 KB Output is correct
24 Correct 79 ms 38288 KB Output is correct
25 Correct 71 ms 39456 KB Output is correct
26 Correct 68 ms 36832 KB Output is correct
27 Correct 70 ms 37140 KB Output is correct
28 Correct 70 ms 37204 KB Output is correct
29 Correct 57 ms 37972 KB Output is correct
30 Correct 56 ms 37972 KB Output is correct
31 Correct 61 ms 36760 KB Output is correct
32 Correct 33 ms 35304 KB Output is correct
33 Correct 58 ms 36868 KB Output is correct
34 Correct 172 ms 47696 KB Output is correct
35 Correct 189 ms 47700 KB Output is correct
36 Correct 152 ms 45904 KB Output is correct
37 Correct 152 ms 45652 KB Output is correct
38 Correct 148 ms 45648 KB Output is correct
39 Correct 123 ms 41492 KB Output is correct
40 Correct 121 ms 41424 KB Output is correct
41 Correct 135 ms 42320 KB Output is correct
42 Correct 133 ms 42356 KB Output is correct
43 Correct 137 ms 42576 KB Output is correct
44 Correct 145 ms 43580 KB Output is correct
45 Correct 145 ms 43856 KB Output is correct
46 Correct 143 ms 43380 KB Output is correct
47 Correct 147 ms 43604 KB Output is correct
48 Correct 147 ms 43408 KB Output is correct
49 Correct 120 ms 43152 KB Output is correct
50 Correct 115 ms 43092 KB Output is correct
51 Correct 125 ms 42948 KB Output is correct
52 Correct 115 ms 42940 KB Output is correct
53 Correct 122 ms 43236 KB Output is correct
54 Correct 130 ms 42604 KB Output is correct
55 Correct 103 ms 40908 KB Output is correct
56 Correct 127 ms 41672 KB Output is correct
57 Correct 1176 ms 104788 KB Output is correct
58 Correct 1168 ms 104780 KB Output is correct
59 Correct 1044 ms 100324 KB Output is correct
60 Correct 1038 ms 100324 KB Output is correct
61 Correct 1040 ms 100876 KB Output is correct
62 Correct 1049 ms 100448 KB Output is correct
63 Correct 670 ms 84560 KB Output is correct
64 Correct 707 ms 84624 KB Output is correct
65 Correct 865 ms 91992 KB Output is correct
66 Correct 868 ms 91988 KB Output is correct
67 Correct 874 ms 91924 KB Output is correct
68 Correct 964 ms 96656 KB Output is correct
69 Correct 951 ms 96620 KB Output is correct
70 Correct 942 ms 95748 KB Output is correct
71 Correct 953 ms 95800 KB Output is correct
72 Correct 985 ms 95592 KB Output is correct
73 Correct 618 ms 84564 KB Output is correct
74 Correct 663 ms 85596 KB Output is correct
75 Correct 642 ms 84508 KB Output is correct
76 Correct 641 ms 84656 KB Output is correct
77 Correct 632 ms 84524 KB Output is correct
78 Correct 865 ms 91404 KB Output is correct
79 Correct 594 ms 80452 KB Output is correct
80 Correct 802 ms 86280 KB Output is correct