ABC260 E - At Least One(双指针)

ABC260 E - At Least One(双指针)

ABC260 E - At Least One(双指针)

一开始想到two pointers 了，但是不知道怎么快速维护是否满足条件。

#include #include using namespace std;int main() { int N, M; cin >> N >> M; vector A(N), B(N); for (int i = 0; i < N; i++) cin >> A[i] >> B[i]; vector> inv(M + 1); for (int i = 0; i < N; i++) { inv[A[i]].push_back(i); inv[B[i]].push_back(i); } vector cnt(N), ans(M + 3); int cnt_zero = N; for (int i = 1, j = 1; i <= M;) { while (j <= M and cnt_zero != 0) { for (auto& x : inv[j]) { if (cnt[x] == 0) cnt_zero--; cnt[x]++; } j++; } if (cnt_zero != 0) break; ans[j - i]++, ans[M + 1 - i + 1]--; for (auto& x : inv[i]) { cnt[x]--; if (cnt[x] == 0) cnt_zero++; } i++; } for (int i = 1; i <= M; i++) { ans[i] += ans[i - 1]; cout << ans[i] << " \n"[i == M]; }}

// Problem: E - At Least One// Contest: AtCoder - AtCoder Beginner Contest 260// URL: Memory Limit: 1024 MB// Time Limit: 2000 ms// Date: 2022-07-30 23:13:40// --------by Herio--------#includeusing namespace std;typedef long long ll;typedef unsigned long long ull; const int N=2e5+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;const int hashmod[4] = {402653189,805306457,1610612741,998244353};#define mst(a,b) memset(a,b,sizeof a)#define db double#define PII pair#define PLL pair#define x first#define y second#define pb emplace_back#define SZ(a) (int)a.size()#define rep(i,a,b) for(int i=a;i<=b;++i)#define per(i,a,b) for(int i=a;i>=b;--i)#define IOS ios::sync_with_stdio(false),cin.tie(nullptr)void Print(int *a,int n){ for(int i=1;i //x=max(x,y) x=min(x,y)void cmx(T &x,T y){ if(xvoid cmn(T &x,T y){ if(x>y) x=y;}PII a[N];int left_mx[N];int is_right[N];ll pre[N];int n,m;bool ck(int x){ for(int i=1;i<=n;i++){ if(x>n>>m; rep(i,1,n){ cin>>a[i].x>>a[i].y; cmx(left_mx[a[i].x],a[i].y); cmn(mn,1LL*a[i].y); } int l=1,r=m,ans=0; while(l<=r){ int mid = l+r>>1; if(ck(mid)) ans=mid,r=mid-1; else l=mid+1; } //printf("%d %d\n",1,ans); for(int i=1,j=ans;i<=mn;cmx(j,left_mx[i++])){ pre[j-i+1]++,pre[m-i+2]--; } rep(i,1,m) pre[i]+=pre[i-1];; rep(i,1,m){ printf("%lld ",pre[i]); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。