제출 #1156481

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1156481		MuhammadSaram	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	100 / 100	2192 ms	185628 KiB

sortbooks

#include <bits/stdc++.h>

using namespace std;

const int M = 1e6 + 1;

int seg[M*2];

void modify(int p,int x,int v=0,int s=0,int e=M)
{
	if (s+1==e)
	{
		seg[v]=x;
		return;
	}
	int mid=(s+e)/2,lc=v+1,rc=v+(mid-s)*2;
	if (p<mid)
		modify(p,x,lc,s,mid);
	else
		modify(p,x,rc,mid,e);
	seg[v]=max(seg[lc],seg[rc]);
}

int get(int l,int r,int v=0,int s=0,int e=M)
{
	if (l>=e or r<=s)
		return 0;
	if (l<=s && e<=r)
		return seg[v];
	int mid=(s+e)/2,lc=v+1,rc=v+(mid-s)*2;
	return max(get(l,r,lc,s,mid),get(l,r,rc,mid,e));
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(NULL), cout.tie(NULL);

	int n,m,x;
	cin>>n>>m;
	stack<int> q;
	map<int,int> lt;
	vector<int> v[n];
	for (int i=0;i<n;i++)
	{
		cin>>x;
		while (!q.empty() && q.top()<=x)
			q.pop();
		if (q.empty())
			modify(i,0);
		else
			modify(i,q.top()+x),v[lt[q.top()]].push_back(i);
		q.push(x);
		lt[x]=i;
	}
	vector<vector<int>> qu[n];
	bool ans[m]={};
	for (int i=0;i<m;i++)
	{
		int l,r,k;
		cin>>l>>r>>k;l--;
		qu[l].push_back({r,k,i});
	}
	for (int i=0;i<n;i++)
	{
		for (auto j:qu[i])
		{
			if (get(i,j[0])<=j[1])
				ans[j[2]]=1;
		}
		for (int j:v[i])
			modify(j,0);
	}
	for (int i=0;i<m;i++)
		cout<<ans[i]<<'\n';
	
	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