Submission #396420

#	Time	Username	Problem	Language	Result	Execution time	Memory
396420		peuch	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	2201 ms	87268 KiB

sortbooks

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 1e6 + 10;

int n, m;
int v[MAXN];

int l[MAXN];

int ans[MAXN];

struct event{
	int a, b, c, id;
	event(int _a = 0, int _b = 0, int _c = 0, int _id = 0){
		a = _a, b = _b, c = _c, id = _id;
	}
	void scan(int _id){
		scanf("%d %d %d", &a, &b, &c);
		id = _id;
	}
	bool operator < (event x) const{
		if(c == x.c) return a > x.a;
		return c > x.c;
	}
};

vector<event> line;

int seg[4 * MAXN];
void update(int pos, int ini, int fim, int id, int val);
int query(int pos, int ini, int fim, int p, int q);

int main(){
	scanf("%d %d", &n, &m);
	for(int i = 1; i <= n; i++){
		scanf("%d", &v[i]);
		l[i] = i - 1;
		while(l[i] > 0 && v[l[i]] <= v[i]) l[i] = l[l[i]];
		line.push_back(event(-1, i, v[i] + v[l[i]], -1));
	}
	for(int i = 1; i <= m; i++){
		event aux;
		aux.scan(i);
		line.push_back(aux);
	}
	sort(line.begin(), line.end());
	for(int i = 0; i < line.size(); i++){
		if(line[i].a == -1) update(1, 1, n, line[i].b, l[line[i].b]);
		else ans[line[i].id] = query(1, 1, n, line[i].a, line[i].b) < line[i].a;
	}
	for(int i = 1; i <= m; i++)
		printf("%d\n", ans[i]);
}

void update(int pos, int ini, int fim, int id, int val){
	if(ini > id || fim < id) return;
	if(ini == fim){
		seg[pos] = max(seg[pos], val);
		return;
	}
	int mid = (ini + fim) >> 1, e = pos << 1, d = e | 1;
	update(e, ini, mid, id, val);
	update(d, mid + 1, fim, id, val);
	seg[pos] = max(seg[e], seg[d]);
}

int query(int pos, int ini, int fim, int p, int q){
	if(ini > q || fim < p) return 0;
	if(ini >= p && fim <= q) return seg[pos];
	int mid = (ini + fim) >> 1, e = pos << 1, d = e | 1;
	return max(query(e, ini, mid, p, q), query(d, mid + 1, fim, p, q));
	
}

Compilation message (stderr)

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:48:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |  for(int i = 0; i < line.size(); i++){
      |                 ~~^~~~~~~~~~~~~
sortbooks.cpp:35:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   35 |  scanf("%d %d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~
sortbooks.cpp:37:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   37 |   scanf("%d", &v[i]);
      |   ~~~~~^~~~~~~~~~~~~
sortbooks.cpp: In member function 'void event::scan(int)':
sortbooks.cpp:19:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   19 |   scanf("%d %d %d", &a, &b, &c);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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