Submission #55090914

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
using ui = unsigned;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define rep(i,l,r) for(int i=(l);i<=(r);++i)
#define per(i,l,r) for(int i=(l);i>=(r);--i)
#define repn(i,n)  for(int i=0;i<(n);++i)
#define sizc(x) ((int)x.size())
#define allc(x) x.begin(),x.end()
#define fir first
#define sec second
namespace KnownError_{
    constexpr int N = 4e5+5;
    int n,l[N],r[N];
    int a[N],tot;
    int epc[N];
    vector<int> vc[N];
    int get(int x){return lower_bound(a+1,a+tot+1,x)-a;}
    pair<int,int> t[N<<1];
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <bits/stdc++.h>
using namespace std;
using ui = unsigned;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define rep(i,l,r) for(int i=(l);i<=(r);++i)
#define per(i,l,r) for(int i=(l);i>=(r);--i)
#define repn(i,n)  for(int i=0;i<(n);++i)
#define sizc(x) ((int)x.size())
#define allc(x) x.begin(),x.end()
#define fir first
#define sec second
namespace KnownError_{
    constexpr int N = 4e5+5;
    int n,l[N],r[N];
    int a[N],tot;
    int epc[N];
    vector<int> vc[N];
    int get(int x){return lower_bound(a+1,a+tot+1,x)-a;}
    pair<int,int> t[N<<1];
    int tg[N<<1];
    pair<int,int> mg(pair<int,int> x,pair<int,int> y){
        if(x.fir!=y.fir)return max(x,y);
        return min(x,y);
    }
    pair<int,int> operator+(pair<int,int> x,int y){return {x.fir+y,x.sec};}
    void bd(int u,int L,int R){
        if(L==R){t[u]={epc[L-1],L};return;}
        int M=L+R>>1,ls=M<<1,rs=M<<1|1;
        bd(ls,L,M),bd(rs,M+1,R);
        t[u]=mg(t[ls],t[rs]);
    }
    void add(int u,int L,int R,int l,int r,int x){
        if(r<L||R<l||r<l)return;
        if(l<=L&&R<=r){t[u]=t[u]+x;tg[u]+=x;return;}
        int M=L+R>>1,ls=M<<1,rs=M<<1|1;
        add(ls,L,M,l,r,x),add(rs,M+1,R,l,r,x);
        t[u]=mg(t[ls],t[rs])+tg[u];
    }
    pair<int,int> qry(int u,int L,int R,int l,int r){
        if(r<L||R<l||r<l)return {(int)-1e9,0};
        if(l<=L&&R<=r)return t[u];
        int M=L+R>>1,ls=M<<1,rs=M<<1|1;
        return mg(qry(ls,L,M,l,r),qry(rs,M+1,R,l,r))+tg[u];
    }
    pair<int,int> ans={0,1};int mx=0;
    void main(){
    	cin>>n;
        a[tot=1]=0;
        rep(i,1,n)cin>>l[i]>>r[i],a[++tot]=l[i],a[++tot]=r[i],a[++tot]=l[i]+1,a[++tot]=r[i]+1;
        sort(a+1,a+tot+1),tot=unique(a+1,a+tot+1)-a-1;
        while(a[tot]>1e9)--tot;
        rep(i,1,n){
            int L=get(l[i]),R=get(r[i]);
            ++epc[L],++epc[R],vc[L].push_back(R);
        }
        rep(i,1,tot)epc[i]+=epc[i-1];
        bd(1,1,tot);
        per(i,tot,1){
            for(auto j:vc[i])add(1,1,tot,j+1,tot,-1);
            auto res=qry(1,1,tot,i+1,tot)+-epc[i];
            for(auto j:vc[i])add(1,1,tot,j+1,tot,1);
            if(res.fir>mx)mx=res.fir,ans={a[i],a[res.sec]};
            else if(res.fir==mx)ans=min(ans,pair<int,int>{a[i],a[res.sec]});
            for(auto j:vc[i])add(1,1,tot,j,j,-1),add(1,1,tot,j+1,tot,-2);
        }
        cout<<ans.fir<<' '<<ans.sec<<'\n';
    }
}
signed main(){
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    KnownError_::main();
}

Submission Info

Compile Error

Main.cpp: In function ‘void KnownError_::bd(int, int, int)’:
Main.cpp:30:16: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
   30 |         int M=L+R>>1,ls=M<<1,rs=M<<1|1;
      |               ~^~
Main.cpp: In function ‘void KnownError_::add(int, int, int, int, int, int)’:
Main.cpp:37:16: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
   37 |         int M=L+R>>1,ls=M<<1,rs=M<<1|1;
      |               ~^~
Main.cpp: In function ‘std::pair<int, int> KnownError_::qry(int, int, int, int, int)’:
Main.cpp:44:16: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
   44 |         int M=L+R>>1,ls=M<<1,rs=M<<1|1;
      |               ~^~

Judge Result