Submission #978223

#	Time	Username	Problem	Language	Result	Execution time	Memory
978223		model_code	Card Collection (JOI24_collection)	C++17	100 / 100	2076 ms	100292 KiB

Main

#include <bits/stdc++.h>
using namespace std;

using ll=long long;

#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
#define pb push_back
#define eb emplace_back
#define a first
#define b second
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
#define si(x) int(x.size())
#ifdef LOCAL
#define dmp(x) cerr<<__LINE__<<" "<<#x<<" "<<x<<endl
#else
#define dmp(x) void(0)
#endif

template<class t,class u> bool chmax(t&a,u b){if(a<b){a=b;return true;}else return false;}
template<class t,class u> bool chmin(t&a,u b){if(b<a){a=b;return true;}else return false;}

template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;

const int INF = 1000000000;
using P=pair<int,int>;
using vi=vc<int>;

struct segtree{
    vc<int> smn,smx;
    int mum;

    void init(int n){
        mum=1;
        while(mum<n) mum<<=1;
        smn.resize(mum*2);
        smx.resize(mum*2);
        for(int i=0;i<mum*2;i++){
            smn[i]=INF;
            smx[i]=-INF;
        }
    }
    void add(int k,int x){
        k+=mum-1;
        smn[k]=smx[k]=x;
        while(k>0){
            k=(k-1)/2;
            smn[k]=min(smn[k*2+1],smn[k*2+2]);
            smx[k]=max(smx[k*2+1],smx[k*2+2]);
        }
    }
    int get_min(int a,int b,int k,int l,int r){
        if(b<=l||r<=a) return INF;
        if(a<=l&&r<=b) return smn[k];
        else{
            int vl=get_min(a,b,k*2+1,l,(l+r)/2);
            int vr=get_min(a,b,k*2+2,(l+r)/2,r);
            return min(vl,vr);
        }
    }
    int get_min(int a,int b){
        return get_min(a,b,0,0,mum);
    }
    int get_max(int a,int b,int k,int l,int r){
        if(b<=l||r<=a) return -INF;
        if(a<=l&&r<=b) return smx[k];
        else{
            int vl=get_max(a,b,k*2+1,l,(l+r)/2);
            int vr=get_max(a,b,k*2+2,(l+r)/2,r);
            return max(vl,vr);
        }
    }
    int get_max(int a,int b){
        return get_max(a,b,0,0,mum);
    }
    int query(int w){
        if(smn[0]>w) return INF;
        int k=0,l=0,r=mum;
        while(l+1<r){
            if(smn[k*2+1]<=w){
                k=k*2+1;
                r=(l+r)/2;
            } else{
                k=k*2+2;
                l=(l+r)/2;
            }
        }
        return l;
    }
};

vc<int> run(vc<int> S,vc<int> V,vc<int> T,vc<int> W){
    int n=S.size(),m=T.size();
    vc<int> vs=S;
    sort(vs.begin(),vs.end());
    vs.erase(unique(vs.begin(),vs.end()),vs.end());
    for(int i=0;i<n;i++) S[i]=lower_bound(vs.begin(),vs.end(),S[i])-vs.begin();
    vc<int> vv=V;
    sort(vv.begin(),vv.end());
    vv.erase(unique(vv.begin(),vv.end()),vv.end());
    for(int i=0;i<n;i++) V[i]=lower_bound(vv.begin(),vv.end(),V[i])-vv.begin();

    vc<int> ps(vs.size()),pv(vv.size());
    for(int i=n-1;i>=0;i--) ps[S[i]]=i;
    for(int i=0;i<n;i++) pv[V[i]]=i;

    vc<int> ng(m);
    vc<vc<P>> q1(vs.size()),q2(vv.size());
    vc<vc<P>> a1(vs.size()),a2(vv.size());
    for(int i=0;i<n;i++){
        a1[S[i]].pb(P(i,V[i]));
        a2[V[i]].pb(P(i,S[i]));
    }
    vc<int> x(m),y(m),z(m),w(m);
    for(int i=0;i<m;i++){
        ng[i]=1;
        int p=lower_bound(vs.begin(),vs.end(),T[i])-vs.begin();
        if(p==vs.size()||vs[p]!=T[i]) continue;
        T[i]=p;
        int q=lower_bound(vv.begin(),vv.end(),W[i])-vv.begin();
        if(q==vv.size()||vv[q]!=W[i]) continue;
        W[i]=q;
        ng[i]=0;
        x[i]=ps[T[i]];
        y[i]=pv[W[i]];
        q1[T[i]].pb(P(i,W[i]));
        q2[W[i]].pb(P(i,T[i]));
    }
    segtree ss,sv;
    ss.init(n);
    sv.init(n);
    for(int i=0;i<n;i++){
        ss.add(i,S[i]);
        sv.add(i,V[i]);
    }
    segtree s1;
    s1.init(n);
    for(int i=vs.size()-1;i>=0;i--){
        for(int j=0;j<a1[i].size();j++){
            P p=a1[i][j];
            s1.add(p.a,p.b);
        }
        for(int j=0;j<q1[i].size();j++){
            P p=q1[i][j];
            int r=s1.query(p.b);
            if(0<r&&r<n&&ss.get_max(0,r)<i&&sv.get_min(0,r)>p.b){
                s1.add(r,INF);
                int nr=s1.query(p.b);
                s1.add(r,V[r]);
                r=nr;
            }
            z[p.a]=r;
        }
    }
    segtree s2;
    s2.init(n);
    for(int i=vv.size()-1;i>=0;i--){
        for(int j=0;j<a2[i].size();j++){
            P p=a2[i][j];
            s2.add(n-p.a-1,p.b);
        }
        for(int j=0;j<q2[i].size();j++){
            P p=q2[i][j];
            int r=s2.query(p.b);
            if(0<r&&r<n&&sv.get_max(n-r,n)<i&&ss.get_min(n-r,n)>p.b){
                s2.add(r,INF);
                int nr=s2.query(p.b);
                s2.add(r,S[n-r-1]);
                r=nr;
            }
            w[p.a]=n-r-1;
        }
    }
    vc<int> ret;
    for(int i=0;i<m;i++){
        if(!ng[i]&&max(x[i],z[i])<min(y[i],w[i])){
            ret.pb(i);
        }
    }
    return ret;
}
void solve(){
    int n,m;
    cin>>n>>m;
    vc<int> S(n),V(n);
    for(int i=0;i<n;i++) cin>>S[i]>>V[i];
    vc<int> T(m),W(m);
    for(int i=0;i<m;i++) cin>>T[i]>>W[i];

    segtree ss,sv;
    ss.init(n);
    sv.init(n);
    for(int i=0;i<n;i++){
        ss.add(i,S[i]);
        sv.add(i,V[i]);
    }
    set<P> st;
    for(int i=0;i<n;i++){
        bool up=true;
        if(i>0&&ss.get_max(0,i)<S[i]&&sv.get_min(0,i)>V[i]) up=false;
        if(i>0&&ss.get_min(0,i)>S[i]&&sv.get_max(0,i)<V[i]) up=false;
        if(i<n-1&&ss.get_max(i+1,n)<S[i]&&sv.get_min(i+1,n)>V[i]) up=false;
        if(i<n-1&&ss.get_min(i+1,n)>S[i]&&sv.get_max(i+1,n)<V[i]) up=false;
        if(up) st.insert(P(S[i],V[i]));
    }
    vc<int> ret;
    for(int i=0;i<m;i++) if(st.find(P(T[i],W[i]))!=st.end()) ret.pb(i);
    vc<int> ret2=run(S,V,T,W);
    for(int i=0;i<ret2.size();i++) ret.pb(ret2[i]);

    for(int i=0;i<n;i++) swap(S[i],V[i]);
    for(int i=0;i<m;i++) swap(T[i],W[i]);
    ret2=run(S,V,T,W);
    for(int i=0;i<ret2.size();i++) ret.pb(ret2[i]);

    for(int i=0;i<n;i++) S[i]=-S[i],V[i]=-V[i];
    for(int i=0;i<m;i++) T[i]=-T[i],W[i]=-W[i];
    ret2=run(S,V,T,W);
    for(int i=0;i<ret2.size();i++) ret.pb(ret2[i]);

    for(int i=0;i<n;i++) swap(S[i],V[i]);
    for(int i=0;i<m;i++) swap(T[i],W[i]);
    ret2=run(S,V,T,W);
    for(int i=0;i<ret2.size();i++) ret.pb(ret2[i]);

    sort(ret.begin(),ret.end());
    ret.erase(unique(ret.begin(),ret.end()),ret.end());
    for(int i=0;i<ret.size();i++){
        if(i!=0) cout<<" ";
        cout<<ret[i]+1;
    }
    cout<<endl;
}
int main(){
	cin.tie(0);
	ios::sync_with_stdio(0);
	cout<<fixed<<setprecision(20);
    solve();
}

Compilation message (stderr)

Main.cpp: In function 'vc<int> run(vc<int>, vc<int>, vc<int>, vc<int>)':
Main.cpp:123:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |         if(p==vs.size()||vs[p]!=T[i]) continue;
      |            ~^~~~~~~~~~~
Main.cpp:126:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |         if(q==vv.size()||vv[q]!=W[i]) continue;
      |            ~^~~~~~~~~~~
Main.cpp:144:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  144 |         for(int j=0;j<a1[i].size();j++){
      |                     ~^~~~~~~~~~~~~
Main.cpp:148:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  148 |         for(int j=0;j<q1[i].size();j++){
      |                     ~^~~~~~~~~~~~~
Main.cpp:163:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  163 |         for(int j=0;j<a2[i].size();j++){
      |                     ~^~~~~~~~~~~~~
Main.cpp:167:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  167 |         for(int j=0;j<q2[i].size();j++){
      |                     ~^~~~~~~~~~~~~
Main.cpp: In function 'void solve()':
Main.cpp:214:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  214 |     for(int i=0;i<ret2.size();i++) ret.pb(ret2[i]);
      |                 ~^~~~~~~~~~~~
Main.cpp:219:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  219 |     for(int i=0;i<ret2.size();i++) ret.pb(ret2[i]);
      |                 ~^~~~~~~~~~~~
Main.cpp:224:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  224 |     for(int i=0;i<ret2.size();i++) ret.pb(ret2[i]);
      |                 ~^~~~~~~~~~~~
Main.cpp:229:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  229 |     for(int i=0;i<ret2.size();i++) ret.pb(ret2[i]);
      |                 ~^~~~~~~~~~~~
Main.cpp:233:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  233 |     for(int i=0;i<ret.size();i++){
      |                 ~^~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 38 / 38
• Subtask 3: 22 / 22
• Subtask 4: 29 / 29