oj.uz

Submission #363917

# Submission time Handle Problem Language Result Execution time Memory
363917 2021-02-07T14:01:40 Z ogibogi2004 Cambridge (info1cup18_cambridge) C++14
100 / 100
 239 ms 13156 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAXN=1e5+6;
const ll INF=2e9;
struct SegmentTree
{
	ll node[4*MAXN];
	ll lazy[4*MAXN];
	bool lz[4*MAXN];
	void init()
	{
		memset(lz,0,sizeof(lz));
		memset(lazy,0,sizeof(lazy));
		memset(node,0,sizeof(node));
	}
	ll merge(ll n1,ll n2)
	{
		return max(n1,n2);
	}
	void push(ll idx,ll l,ll r)
	{
		if(lz[idx]==0)return;
		node[idx]+=lazy[idx];
		if(l!=r)
		{
			lz[idx*2]=1;
			lz[idx*2+1]=1;
			lazy[idx*2]+=lazy[idx];
			lazy[idx*2+1]+=lazy[idx];
		}
		lazy[idx]=0;
		lz[idx]=0;
	}
	void update(ll idx,ll l,ll r,ll ql,ll qr,ll val)
	{
		push(idx,l,r);
		if(l>qr||r<ql||l>r)return;
		if(l>=ql&&r<=qr)
		{
			lz[idx]=1;
			lazy[idx]+=val;
			push(idx,l,r);
			return;
		}
		ll mid=(l+r)/2;
		update(idx*2,l,mid,ql,qr,val);
		update(idx*2+1,mid+1,r,ql,qr,val);
		node[idx]=merge(node[idx*2],node[idx*2+1]);
	}
	ll query(ll idx,ll l,ll r,ll ql,ll qr)
	{
		push(idx,l,r);
		if(l>qr||r<ql||l>r)return -INF;
		if(l>=ql&&r<=qr)return node[idx];
		ll mid=(l+r)/2;
		return merge(query(idx*2,l,mid,ql,qr),query(idx*2+1,mid+1,r,ql,qr));
	}
}tree;
ll n,m;
ll t[MAXN],d[MAXN];
ll maxright[MAXN];
ll where[MAXN];
void add(ll idx)
{
	tree.update(1,1,n,where[idx],where[idx],INF-d[idx]);
	tree.update(1,1,n,where[idx],n,t[idx]);
}
void remove(ll idx)
{
	tree.update(1,1,n,where[idx],where[idx],-INF+d[idx]);
	tree.update(1,1,n,where[idx],n,-t[idx]);
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n>>m;
	vector<pair<ll,ll> >v;
	for(ll i=1;i<=n;i++)
	{
		cin>>t[i]>>d[i];
		v.push_back({d[i],i});
	}
	sort(v.begin(),v.end());
	for(ll i=0;i<v.size();++i)
	{
		where[v[i].second]=i+1;
	}
	ll r=0;
	//tree.init();
	//cout<<tree.query(1,1,n,1,n)<<endl;
	tree.update(1,1,n,1,n,-INF);
	//cout<<tree.query(1,1,n,1,n)<<endl;
	for(ll l=1;l<=n;l++)
	{
		while(r<=n&&tree.query(1,1,n,1,n)<0)
		{
			r++;
			if(r<=n)add(r);
		}
		remove(l);
		maxright[l]=r-1;
	}
	//for(ll i=1;i<=n;i++)cout<<maxright[i]<<" ";
	//cout<<endl;
	for(ll i=0;i<m;i++)
	{
		ll ez,dp;
		cin>>ez>>dp;
		if(maxright[ez]>=dp)
		{
			cout<<"1\n";
		}
		else cout<<"0\n";
	}
return 0;
}

Compilation message

cambridge.cpp: In function 'int main()':
cambridge.cpp:87:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |  for(ll i=0;i<v.size();++i)
      |             ~^~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 192 ms 9572 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 14 ms 1648 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 11 ms 620 KB Output is correct
4 Correct 21 ms 620 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 192 ms 9572 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 14 ms 1648 KB Output is correct
6 Correct 11 ms 620 KB Output is correct
7 Correct 21 ms 620 KB Output is correct
8 Correct 228 ms 12644 KB Output is correct
9 Correct 231 ms 12644 KB Output is correct
10 Correct 239 ms 12716 KB Output is correct
11 Correct 153 ms 13156 KB Output is correct
12 Correct 162 ms 12696 KB Output is correct
13 Correct 2 ms 492 KB Output is correct