Submission #249877

#	Time	Username	Problem	Language	Result	Execution time	Memory
249877		hohohaha	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	64 / 100	3107 ms	259960 KiB

sortbooks

//	ZapZu's code hohoho
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
using namespace std;

#define mp make_pair
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define dfs_black 1
#define dfs_white -1
#define pr pair
#define vt vector
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

#define ln 2*id
#define rn 2*id+1

mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count());

typedef double db;
typedef long long li;
typedef long double ld;

typedef pr<int, int> ii;
typedef pr<ld,ld> dd;

typedef vt<int> vi;
typedef vt<li> vli;
typedef vt<ld> vld;
typedef vt<ii> vii;

typedef map<int, int> mii;
typedef map<int, bool> mib;
typedef map<int, char> mic;

typedef set<int> s_i;
typedef set<char> s_c;

const int MOD = 1e9+7;
const li INF = 1e18;
const ld PI = 4*atan((ld)1);
int a[1000005];
struct it
{
	vi mx, mx_inv; vt<vi> arr; int n, re, cur_mx;
	it(int _n): n(_n)
	{
		mx.assign(4*n+5, 0);
		mx_inv.assign(4*n+5, 0);
		arr.assign(4*n+5, vi());
	}
	void build(int id, int l, int r)
	{
		if(l==r)
		{
			mx[id] = a[l];
			mx_inv[id] = 0;
			arr[id].eb(a[l]);
			return;
		}
		build(ln, l, (l+r)/2);
		build(rn, (l+r)/2+1, r);
		mx[id] = max(mx[ln], mx[rn]); arr[id].resize(r-l+1); mx_inv[id] = max(mx_inv[2*id], mx_inv[2*id+1]);
		for(int i=0; i<arr[rn].size(); i++) if(arr[rn][i]<mx[ln])mx_inv[id] = max(mx_inv[id],mx[ln]+arr[rn][i]);
		int p1=-1, p2=-1;
		while(p1+1<arr[ln].size() || p2+1<arr[rn].size())
		{
			if(p2+1>=arr[rn].size()) 
			{
				arr[id][p1+p2+2] = arr[ln][p1+1]; //w?
				p1++;
			}
			else if(p1+1>=arr[ln].size())
			{
				arr[id][p1+p2+2] = arr[rn][p2+1];
				p2++;
			}
			else if(arr[ln][p1+1]<arr[rn][p2+1])
			{
				arr[id][p1+p2+2] = arr[ln][p1+1]; //w?
				p1++;
			}
			else 
			{
				arr[id][p1+p2+2] = arr[rn][p2+1];
				p2++;
			}
		}
	}
	void g(int id, int l, int r, int ll, int rr)
	{
		if(ll>r or l>rr) return;
		if(ll<=l and r<=rr)
		{
			re = max(re, mx_inv[id]);
			int lb = 0, rb = arr[id].size()-1;
			while(lb<rb)
			{
				int mid = (lb+rb+1)/2;
				if(arr[id][mid]<cur_mx) lb=mid;
				else rb=mid-1;
			}
			if(arr[id][lb]<cur_mx) re = max(re, cur_mx+arr[id][lb]);
			cur_mx = max(cur_mx, mx[id]);
		}
		else 
		{
			g(ln, l, (l+r)/2, ll, rr);
			g(rn, (l+r)/2+1, r, ll, rr);
		}
	}
	int query(int l, int r)
	{
		re=0; cur_mx=0;
		g(1, 1, n, l, r);
		return re;
	}
} IT(1);
signed main()
{
//	freopen(".inp", "r", stdin);
//	freopen(".out", "w", stdout);
	fastio;
	int n, q; cin>>n>>q; IT = it(n);
	for(int i=1; i<=n; i++)	cin>>a[i];
	IT.build(1, 1, n);
	while(q--)
	{
		int l, r, k;
		cin>>l>>r>>k;
		if(IT.query(l, r)>k) cout<<0;
		else cout<<1;
		cout<<endl;
	}
}

Compilation message (stderr)

sortbooks.cpp: In member function 'void it::build(int, int, int)':
sortbooks.cpp:68:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<arr[rn].size(); i++) if(arr[rn][i]<mx[ln])mx_inv[id] = max(mx_inv[id],mx[ln]+arr[rn][i]);
                ~^~~~~~~~~~~~~~~
sortbooks.cpp:70:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(p1+1<arr[ln].size() || p2+1<arr[rn].size())
         ~~~~^~~~~~~~~~~~~~~
sortbooks.cpp:70:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(p1+1<arr[ln].size() || p2+1<arr[rn].size())
                                ~~~~^~~~~~~~~~~~~~~
sortbooks.cpp:72:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(p2+1>=arr[rn].size()) 
       ~~~~^~~~~~~~~~~~~~~~
sortbooks.cpp:77:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    else if(p1+1>=arr[ln].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