Submission #171565

#	Time	Username	Problem	Language	Result	Execution time	Memory
171565		davitmarg	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	64 / 100	1233 ms	262148 KiB

sortbooks

/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <unordered_map>
#include <set>
#include <queue>
#include <iomanip>
#include <stack>
#include <cassert>
#include <iterator>
#include <bitset>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(),v.end()
using namespace std;
char readchar() {
	char c = getchar();
	while (c <= 33) {
		c = getchar();
	}
	return c;
}


int readint() {
	char c = getchar();
	while (c <= 33) {
		c = getchar();
	}
	bool sign = false;
	if (c == '-') {
		sign = true;
		c = getchar();
	}
	int t = 0;
	while (c >= '0' && c <= '9') {
		t = (t << 3) + (t << 1) + c - '0';
		c = getchar();
	}
	return (sign ? -t : t);
}



int n, m, a[1000006],K[1000006],ANS[1000006], wmin,ind;
int ans;
vector<int> g[4 * 1000006];
vector<pair<int,int>> query[4 * 1000006];
int t[4 * 1000006], mn[4 * 1000006], mx[4 * 1000006];

int mergeSerge(vector<int>& a, vector<int>& b, vector<int>& c)
{
	int p = 0, q = 0, d = 0;
	for (int i = 0; i < b.size(); i++)
		if (b[i] < a.back())
			d = a.back() + b[i];
	while (p < a.size())
	{
		while (q < b.size() && b[q] < a[p])
			c.PB(b[q++]);
		c.PB(a[p++]);
	}
	while (q < b.size())
		c.PB(b[q++]);
	return d;
}

void build(int v, int l, int r)
{
	if (l == r)
	{
		t[v] = a[l];
		mn[v] = a[l];
		g[v].PB(a[l]);
		return;
	}
	int m = (l + r) / 2;
	build(v * 2, l, m);
	build(v * 2 + 1, m + 1, r);
	mx[v]=mergeSerge(g[v * 2], g[v * 2 + 1],g[v]);
	mx[v] = max(max(mx[v],mx[v * 2]), mx[v * 2 + 1]);
	t[v] = max(t[v * 2], t[v * 2 + 1]);
	mn[v] = min(mn[v * 2], mn[v * 2 + 1]);
}

int get(int v, int l, int r, int i, int j, int lmax)
{
	if (i > j)
		return -1;
	if (l == i && r == j)
	{
		//cout<<"["<<l<<":"<<r<<"]"<<" "<<lmax<<endl;
		if (g[v][0] < lmax)
			query[v].PB(MP(lmax,ind));
		ANS[ind] = max(ANS[ind], mx[v]);
		return t[v];
	}
	int m = (l + r) >> 1;

	int p1, p2;

	p1 = get(v * 2, l, m, i, min(j, m), lmax);
	lmax = max(lmax, p1);

	p2 = get(v * 2 + 1, m + 1, r, max(m + 1, i), j, lmax);
	lmax = max(lmax, p2);

	return lmax;
}

void solve(int v, int l, int r)
{
	sort(all(query[v]));
	while (!query[v].empty())
	{
		while (!g[v].empty() && g[v].back() >= query[v].back().first)
			g[v].pop_back();
		if(!g[v].empty())
			ANS[query[v].back().second] = max(query[v].back().first + g[v].back(),ANS[query[v].back().second]);
		//cout << query[v].back().first << " : " << g[v].back()<<" : "<< ANS[query[v].back().second] << endl;
		query[v].pop_back();
	}
	if (l == r)
		return;
	int m = (l + r) / 2;
	solve(v * 2, l, m);
	solve(v * 2 + 1, m + 1, r);
}

int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		a[i] = readint();
	build(1, 1, n);

	while (m--)
	{
		ind++;
		int l, r, k;
		ans = 0;
		// scanf("%d%d%d",&l,&r,&k);
		l = readint();
		r = readint();
		k = readint();
		K[ind] = k;
		get(1, 1, n, l, r, -1);
	}

	solve(1,1,n);
	for (int i = 1; i <= ind; i++)
	{
		//cout << ANS[i] << endl;
		printf("%c", '0' + (K[i] >= ANS[i]));
		putchar(10);
	}

	return 0;
}



/*


5 5
2 1 1 1 2
1 5 0
2 5 0
1 4 0
2 4 0
1 5 3

*/

Compilation message (stderr)

sortbooks.cpp: In function 'int mergeSerge(std::vector<int>&, std::vector<int>&, std::vector<int>&)':
sortbooks.cpp:63:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < b.size(); i++)
                  ~~^~~~~~~~~~
sortbooks.cpp:66:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (p < a.size())
         ~~^~~~~~~~~~
sortbooks.cpp:68:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (q < b.size() && b[q] < a[p])
          ~~^~~~~~~~~~
sortbooks.cpp:72:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (q < b.size())
         ~~^~~~~~~~~~

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