Submission #524546

#	Time	Username	Problem	Language	Result	Execution time	Memory
524546		asliddinaif	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	64 / 100	134 ms	13756 KiB

sortbooks

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define IOS ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define all(x) (x).begin(), (x).end()
#define fp(a,i,c) for(int (a) = (i); (a) < (c); (a)++)
#define fpp(a,i,c) for(int (a) = (i); (a) <= (c); (a)++)
#define fm(a,i,c) for(int (a) = (i); (a) > (c); (a)--)
#define fmm(a,i,c) for(int (a) = (i); (a) >= (c); (a)--)
const int maxx = 2e5+5;
int tr[maxx], n, m, a[maxx], ans[maxx], k[maxx], x[maxx], y[maxx];
vector <int> g[maxx];
void ad(int x, int val){
	while(x > 0)
		tr[x] = max(tr[x], val), x -= x & -x;
}

int get(int x){
	int s = 0;
	while(x <= n)
		s = max(tr[x], s), x += x & -x;
	return s;
}
void S()
{
	cin >> n >> m;
	fpp(i,1,n)
		cin >> a[i];
	fpp(i,1,m){
		cin >> x[i] >> y[i] >> k[i];
		g[y[i]].push_back(i);
	}
	vector <int> v;
	fpp(i,1,n){
		while(!v.empty() && a[v.back()] <= a[i])
			v.pop_back();
		int xx = (v.size() == 0 ? 0 : v.back());
		ad(xx, a[xx]+a[i]);
		for(auto it : g[i])
			ans[it] = (get(x[it]) <= k[it]);//, cout << get(x[it]) << " " << i << " " << it << " ";
		v.push_back(i);
	//	cout << a[xx] << "\n";
	}
	fpp(i,1,m)
		cout << ans[i] << "\n";
}
int main()
{
	IOS;
	S();
}

Compilation message (stderr)

sortbooks.cpp: In function 'void S()':
sortbooks.cpp:7:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    7 | #define fpp(a,i,c) for(int (a) = (i); (a) <= (c); (a)++)
      |                            ^
sortbooks.cpp:27:2: note: in expansion of macro 'fpp'
   27 |  fpp(i,1,n)
      |  ^~~
sortbooks.cpp:7:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    7 | #define fpp(a,i,c) for(int (a) = (i); (a) <= (c); (a)++)
      |                            ^
sortbooks.cpp:29:2: note: in expansion of macro 'fpp'
   29 |  fpp(i,1,m){
      |  ^~~
sortbooks.cpp:7:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    7 | #define fpp(a,i,c) for(int (a) = (i); (a) <= (c); (a)++)
      |                            ^
sortbooks.cpp:34:2: note: in expansion of macro 'fpp'
   34 |  fpp(i,1,n){
      |  ^~~
sortbooks.cpp:7:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    7 | #define fpp(a,i,c) for(int (a) = (i); (a) <= (c); (a)++)
      |                            ^
sortbooks.cpp:44:2: note: in expansion of macro 'fpp'
   44 |  fpp(i,1,m)
      |  ^~~

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