Submission #231338

#	Time	Username	Problem	Language	Result	Execution time	Memory
231338		maskoff	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	100 / 100	1512 ms	79188 KiB

sortbooks

#include <bits/stdc++.h>
#include <ext/rope>
#include <random>
#include <chrono>
#include <ext/pb_ds/assoc_container.hpp>
 
#define file ""
 
#define all(x) x.begin(), x.end()
 
#define sc second
#define fr first
 
#define pb push_back
#define mp make_pair

#define pss pair<line*, line*>
 
using namespace std;
using namespace __gnu_cxx;
 
typedef long long ll;
typedef pair <int, int> pii;
                                    
const int inf = 1e9;
const int MOD = 1e9 + 7;
                                          
const int dx[] = {+1, -1, 0, 0};
const int dy[] = {0, 0, +1, -1};

int const N = 1e6 + 1;

int n, q;

struct line {
 	int r;
 	int l;
 	int k;
 	int pos;
};
vector<line> all;
vector<int> t, a;
int pos[N];

bool cmp(line a, line b) {
 	return a.r < b.r;
}

void update (int u, int l, int r, int pos, int val) {
 	if (r == l) {
 	 	t[u] = val;
 	 	return;
 	}
 	int m = l + r >> 1;
 	if (pos <= m) update (u + u, l, m, pos, val);
 	else update (u + u + 1, m + 1, r, pos, val);
 	t[u] = max(t[u + u], t[u + u + 1]);
}

int get (int u, int ul, int ur, int l, int r) {
 	if (l > ur || ul > r)
 		return 0;
 	if (l <= ul && ur <= r)
 		return t[u];
 	int um = ul + ur >> 1;
 	return max(get(u + u, ul, um, l, r), get(u + u + 1, um + 1, ur, l, r));
}     

int main() { 
	ios_base :: sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n >> q;
  int g[q + 1];
  a.resize(n + 1);
  t.resize(4 * n);
  for (int i = 1; i <= n; i++)
  	cin >> a[i];
  for (int i = 1; i <= q; i++) {
   	int l, r, k;
   	cin >> l >> r >> k;
   	all.pb({r, l, k, i});
  }
  sort(all(all), cmp);
  stack<pair<int, int>> s;
  for (int i = 1; i <= n; i++) {
   	while (!s.empty() && s.top().fr <= a[i])
   		s.pop();	
   	if (!s.empty()) pos[i] = s.top().sc;
   	s.push({a[i], i});
  }
  int k = 0;
  for (int i = 1; i <= n; i++) {
		if (pos[i] != 0) {
			//cout << pos[i] << endl;
			update(1, 1, n, pos[i], a[i] + a[pos[i]]);
		}
		while (k < q && all[k].r == i) {
		 	int l = all[k].l;
		 	int r = all[k].r;
		 	int val = all[k].k;
		 	int id = all[k].pos;
		 	int ans = get(1, 1, n, l, r);
		 	// << l << " " << r << " " << ans << endl;
		 	if (ans > val) g[id] = 0;
		 	else g[id] = 1;
		 	k++;
		}
  }
  for (int i = 1; i <= q; i++)
  	cout << g[i] << "\n";
	return 0;
}

Compilation message (stderr)

sortbooks.cpp: In function 'void update(int, int, int, int, int)':
sortbooks.cpp:54:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = l + r >> 1;
           ~~^~~
sortbooks.cpp: In function 'int get(int, int, int, int, int)':
sortbooks.cpp:65:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int um = ul + ur >> 1;
            ~~~^~~~
sortbooks.cpp: In function 'int main()':
sortbooks.cpp:109:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for (int i = 1; i <= q; i++)
   ^~~
sortbooks.cpp:111:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  return 0;
  ^~~~~~

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