QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#250630#6391. AirplaneWorld_Creater0 46ms47224kbC++142.3kb2023-11-13 14:34:062023-11-13 14:34:07

Judging History

你现在查看的是最新测评结果

  • [2023-11-13 14:34:07]
  • 评测
  • 测评结果:0
  • 用时:46ms
  • 内存:47224kb
  • [2023-11-13 14:34:06]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
struct node{
	int mn,cnt,sec;
	node operator +(const node &b) const
	{
		node t=*this;
		if(t.mn==b.mn)
		{
			t.cnt+=b.cnt;
			t.sec=min(t.sec,b.sec);
		}
		else if(t.mn>b.mn)
		{
			t.sec=min(t.mn,b.sec);
			t.mn=b.mn;
			t.sec=b.sec;
		}
		else if(t.mn<b.mn)
		{
			t.sec=min(t.sec,b.mn);
		}
		return t;
	}
};
struct segtree{
	node tree[2000005];
	int tag[2000005];
	#define lc(x) (x<<1)
	#define rc(x) (x<<1|1)
	#define M(l,r) ((l+r)>>1)
	void pushup(int p)
	{
		tree[p]=tree[lc(p)]+tree[rc(p)];
	}
	void maketag(int p,int k)
	{
		tree[p].mn=max(tree[p].mn,k);
		tag[p]=max(tag[p],k);
	}
	void pushdown(int p)
	{
		maketag(lc(p),tag[p]);
		maketag(rc(p),tag[p]);
		tag[p]=0;
	}
	void build(int p,int l,int r)
	{
		if(l==r)
		{
			tree[p]={0,1,10000000};
			return ;
		}
		int mid=M(l,r);
		build(lc(p),l,mid);
		build(rc(p),mid+1,r);
		pushup(p);
	}
	void modify(int p,int l,int r,int L,int R,int k)
	{
		if(tree[p].mn>=k) return ;
		if(L<=l&&r<=R&&tree[p].sec>k)
		{
			maketag(p,k);
			return ;
		}
		pushdown(p);
		int mid=M(l,r);
		if(L<=mid) modify(lc(p),l,mid,L,R,k);
		if(mid<R) modify(rc(p),mid+1,r,L,R,k);
		pushup(p);
	}
	node query(int p,int l,int r,int L,int R)
	{
		if(L<=l&&r<=R) return tree[p];
		pushdown(p);
		int mid=M(l,r);
		if(L<=mid&&mid<R) return query(lc(p),l,mid,L,R)+query(rc(p),mid+1,r,L,R);
		if(L<=mid) return query(lc(p),l,mid,L,R);
		if(mid<R) return query(rc(p),mid+1,r,L,R);
	}
}T;
int n,m,q,ans[500005];
vector<int> rid[500005],qid[500005];
pair<int,int> range[500005],qu[500005];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>q;
	for(int i=1;i<=m;i++)
	{
		int l,r;
		cin>>l>>r;
		range[i]={l,r};
		rid[r].emplace_back(i);
	}
	T.build(1,1,n);
	for(int i=1;i<=q;i++)
	{
		int l,r;
		cin>>l>>r;
		qu[i]={l,r};
		qid[r].emplace_back(i);
	}
	for(int i=1;i<=n;i++)
	{
		for(auto j:rid[i])
		{
			auto [l,r]=range[j];
			T.modify(1,1,n,l,r,l);
		}
		for(auto j:qid[i])
		{
			auto [l,r]=qu[j];
			auto res=T.query(1,1,n,l,r);
			// cerr<<l<<" "<<r<<" "<<res.mn<<" "<<res.cnt<<" "<<res.sec<<"\n";
			if(res.mn>=l) ans[j]=1;
		}
	}
	for(int i=1;i<=q;i++)
	{
		cout<<(ans[i]?"YES":"NO")<<"\n";
	}
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 46ms
memory: 47224kb

input:

200000 199999
0 199 58 60 83 5 10 182 87 65 104 153 197 137 80 143 34 181 62 48 10 57 86 58 117 10 171 188 95 52 95 140 126 0 196 85 87 14 10 139 177 92 31 18 102 146 68 9 91 124 156 38 41 121 183 10 32 174 171 29 49 26 118 1 69 185 57 168 54 159 195 95 9 32 195 70 85 174 158 82 33 197 66 189 198 11...

output:


result:

wrong answer 1st lines differ - expected: '200378', found: ''

Subtask #2:

score: 0
Wrong Answer

Test #8:

score: 0
Wrong Answer
time: 3ms
memory: 34356kb

input:

6 10
0 0 6 1 8 0
5 6
2 3
5 4
6 4
3 5
6 2
3 6
3 4
3 1
6 1

output:


result:

wrong answer 1st lines differ - expected: '1', found: ''

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Skipped

Dependency #1:

0%