社区讨论

《不放弃人》

灌水区参与者 8已保存回复 11

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
11 条
当前快照
1 份
快照标识符
@lobfivj3
此快照首次捕获于
2023/10/29 20:10
2 年前
此快照最后确认于
2023/11/04 01:41
2 年前
查看原帖
@ 花开一心相惜
本来看着看着您写的SD S组整活全集看的起劲,结果竟然发现了自己的代码/kx/kx/kx
喜提“不放弃人”称号。
当时考场上我一开始读错题然后写了个树状数组假了于是改成树状数组 n^2logn 的暴力。最后的时候我想出来了正解但是只有 30min 了,但是我不想放弃于是死命调调调,并在最后 5min 和暴力拍上了,然后愉快写上文件绑上暴力出了考场。当晚默写下来自己的正解部分过了所有的民间测试和加强数据,觉得没问题了。然后代码下发交到洛谷上发现只有5分...定睛一看原来我前面数据分治的暴力树状数组没注意值域数组开小了,后面的正解部分有一行调试之后改错了复杂度假了。。。
CPP
now=1
应该改成
CPP
now=tmp
于是做好了爆零的准备。。。
但是!!1 But!!1 在CCF的迷之数据下,最后我的考场代码还跑了75分/kx/kx/kx
不放弃人
放个考场代码改完的AC code
CPP
#include <unordered_map>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <cstdio>
#include <cmath>
using namespace std;

#define int long long

/***** Fast_IO *****/

using std::cin;
using std::cout;
using vii = std::vector<int> ;
using pii = std::pair<int,int> ;

namespace IO{
	char buf[(1<<21)],*p1=buf,*p2=buf,buf1[(1<<21)]; int _=0;

	inline char gc (){
		return p1==p2&&(p2=(p1=buf)+fread(buf,1,(1<<21),stdin),p1==p2)?EOF:*p1++;
	}

	#define gc getchar
	#define pc putchar
	#define ONLINE_JUDGE OJ

	template<class I>
	inline I read(I &x){
		x=0; I f=1; char c=gc(); if(c==EOF){ return -1; }
		while(c<'0'||c>'9'){ if(c=='-'){ f=f*(-1); } c=gc(); }
		while(c>='0'&&c<='9'){ x=(x<<1)+(x<<3)+(c^48); c=gc(); }
		return x=x*f;
	}

	template<typename I,typename ...Args>
	inline void read(I &a, Args &...args){
		read(a),read(args...);
	}

	template<class I>
	inline void write(I x){
		if(x==0){ pc('0'); return; }
		int tmp=x>0?x:(-x),cnt=0;
		if(x<0){ pc('-'); }
		while(tmp){ buf[cnt++]=(tmp%10)+'0'; tmp/=10; }
		while(cnt){ pc(buf[--cnt]); }
		return;
	}

	void _FILE(){
		#ifdef ONLINE_JUDGE
			freopen("airport.in","r",stdin);
			freopen("airport.out","w",stdout);
		#endif
	}

	#define out(x) write(x),pc(' ')
	#define outn(x) write(x),pc('\n')
	#define assi() pc('\t')
	#define FOR(i,a,b) for(int i(a);i<=(b);++i)
	#define ROF(i,a,b) for(int i(a);i>=(b);--i)
	#define FORs(i,a,b,s) for(int i(a);i<=(b);i+=(s))
	#define ROFs(i,a,b,s) for(int i(a);i>=(b);i-=(s))
	#define next(i,now) for(int i(link[now]);i;i=edge[i].nexty)
	#define each(i,v) for(auto &i:v)
	#define all(v) v.begin(),v.end()
	#define pb push_back
	#define mp make_pair
	#define fir first
	#define sec second
}using namespace IO;

/***** Fast_IO *****/

#define maxn 1000010
#define SIZE 5010

struct Bridge{
	int u,v,cnt;

	bool operator <(Bridge p) const {
		return u<p.u;
	}
}bri[maxn],bri2[maxn];

int lim;

class Bit{
	#define lowbit(k) ((k)&(-k))

	private:
		unordered_map<int,int> tree;

	public:
		void add(int x,int k){
			for(;x<=lim;x+=lowbit(x)){
				tree[x]+=k;
			}
		}

		int query(int x){
			int res=0;
			for(;x>0;x-=lowbit(x)){
				res+=tree[x];
			}
			return res;
		}
}ta,ta2;

int n,m_1,m_2;

::vector<int> vis1,vis2;

bool Use[maxn],Use2[maxn];
int ans[maxn],ans2[maxn];

signed main(){
	_FILE();
	read(n,m_1,m_2);
	if(n>=m_1+m_2){ outn(m_1+m_2); return 0; }
	FOR(i,1,m_1){ read(bri[i].u,bri[i].v); lim=::max(lim,bri[i].v); }
	FOR(i,1,m_2){ read(bri2[i].u,bri2[i].v); lim=::max(lim,bri2[i].v); }
	::sort(bri+1,bri+m_1+1);
	::sort(bri2+1,bri2+m_2+1);
	int res=0;
	FOR(i,1,n){
		int now=i;
		while(Use[now]&&now<=m_1){ now++; }
		if(now>m_1){ ans[now]=res; continue; }
		Use[now]=1; ++res;
		while(1){
			int k=-1;
			int l=now,r=m_1;
			while(l<=r){
				int mid=(l+r)>>1;
				if(bri[now].v<bri[mid].u){
					k=mid; r=mid-1;
				} else{ l=mid+1; }
			}
			if(k==-1){ ans[i]=res; break; }
			while(Use[k]&&k<=m_1){ ++k; }
			if(k>m_1){ ans[i]=res; break; }
			Use[k]=1; ++res; now=k;
		}
	}
	// FOR(i,0,n){ outn(ans[i]); }
	res=0;
	FOR(i,1,n){
		int now=i;
		while(Use2[now]&&now<=m_2){ now++; }
		if(now>m_2){ ans2[now]=res; continue; }
		Use2[now]=1; ++res;
		while(1){
			int k=-1;
			int l=now,r=m_2;
			while(l<=r){
				int mid=(l+r)>>1;
				if(bri2[now].v<bri2[mid].u){
					k=mid; r=mid-1;
				} else{ l=mid+1; }
			}
			if(k==-1){ ans2[i]=res; break; }
			while(Use2[k]&&k<=m_2){ ++k; }
			if(k>m_2){ ans2[i]=res; break; }
			Use2[k]=1; ++res; now=k;
		}
	}
	int answer=0;
	FOR(i,0,n){ answer=::max(answer,ans[i]+ans2[n-i]); }
	outn(answer);
	// int ans=0;
	// FOR(i,0,n){
	// 	int tmp=i,tmp2=n-i;
	// 	int cnt=0;
	// 	FOR(j,1,m_1){
	// 		bri[j].cnt=(j-1-cnt)-ta.query(bri[j].u);
	// 		if(bri[j].cnt<tmp){ ta.add(bri[j].v,1); vis1.pb(bri[j].v); }
	// 		else{ ++cnt; }
	// 	}
	// 	cnt=0;
	// 	FOR(j,1,m_2){
	// 		bri2[j].cnt=(j-1-cnt)-ta2.query(bri2[j].u);
	// 		if(bri2[j].cnt<tmp2){ ta2.add(bri2[j].v,1); vis2.pb(bri2[j].v); }
	// 		else{ ++cnt; }
	// 	}
	// 	ans=::max(ans,(int)vis1.size()+(int)vis2.size());
	// 	FOR(j,0,(int)vis1.size()-1){ ta.add(vis1[j],-1); }
	// 	FOR(j,0,(int)vis2.size()-1){ ta2.add(vis2[j],-1); }
	// 	// ta.clear(),ta2.clear();
	// 	vis1.clear(),vis2.clear();
	// }
	// outn(ans);
	return 0;
}
感谢您赠与我的“不放弃人”称号,我觉得还挺贴切的/kx

回复

11 条回复,欢迎继续交流。

正在加载回复...