Submission #1077975

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077975		azberjibiou	Card Collection (JOI24_collection)	C++17	100 / 100	2736 ms	188836 KiB

Main

//Info1 fix code (fix 0707 2255)
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define pb push_back
#define lb lower_bound
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
typedef long long ll;
using namespace std;
const int mxN=200005;
const int mxM=99999;
const int mxK=60;
struct info{
    int plu[2], minu[2], notp, notm;
    info(){
        plu[0]=plu[1]=minu[0]=minu[1]=notp=notm=0;
    }
};
struct segtree{
    int seg[4*mxN]={};
    int typ;
    int f(int a, int b){
        if(a==0 || b==0) return a+b;
        if(typ==1) return max(a, b);
        if(typ==2) return min(a, b);
        // warning 방지용
        return 0;
    }
    void init(int n, int t){
        for(int i=0;i<4*n;i++) seg[i]=0;
        typ=t;
    }
    void upd(int idx, int s, int e, int pos, int x){
        if(s==e){
            seg[idx]=x;
            return;
        }
        int mid=(s+e)/2;
        if(pos<=mid) upd(2*idx, s, mid, pos, x);
        else upd(2*idx+1, mid+1, e, pos, x);
        seg[idx]=f(seg[2*idx], seg[2*idx+1]);
    }
    int solv(int idx, int s1, int e1, int s2, int e2){
        if(s2>e1 || s1>e2) return 0;
        if(s2<=s1 && e1<=e2) return seg[idx];
        int mid=(s1+e1)/2;
        return f(solv(2*idx, s1, mid, s2, e2), solv(2*idx+1, mid+1, e1, s2, e2));
    }
    int bin_search1l(int idx, int s1, int e1, int s2, int e2, int x){
        if(s1==e1){
            return (f(seg[idx], x)==seg[idx] ? s1 : 0);
        }
        if(s2>e1 || s1>e2) return 0;
        if(s2<=s1 && e1<=e2){
            if(f(seg[idx], x)==seg[idx]){
                int mid=(s1+e1)/2;
                int lres=bin_search1l(2*idx, s1, mid, s2, e2, x);
                if(lres!=0) return lres;
                return bin_search1l(2*idx+1, mid+1, e1, s2, e2, x);
            }
            else return 0;
        }
        int mid=(s1+e1)/2;
        if(s2<=mid){
            int lres=bin_search1l(2*idx, s1, mid, s2, e2, x);
            if(lres!=0) return lres;
        }
        return bin_search1l(2*idx+1, mid+1, e1, s2, e2, x);
    }
    int bin_search1r(int idx, int s1, int e1, int s2, int e2, int x){
        if(s1==e1){
            return (f(seg[idx], x)==seg[idx] ? s1 : 0);
        }
        if(s2>e1 || s1>e2) return 0;
        if(s2<=s1 && e1<=e2){
            if(f(seg[idx], x)==seg[idx]){
                int mid=(s1+e1)/2;
                int rres=bin_search1r(2*idx+1, mid+1, e1, s2, e2, x);
                if(rres!=0) return rres;
                return bin_search1r(2*idx, s1, mid, s2, e2, x);
            }
            else return 0;
        }
        int mid=(s1+e1)/2;
        if(s2<=mid){
            int lres=bin_search1r(2*idx+1, mid+1, e1, s2, e2, x);
            if(lres!=0) return lres;
        }
        return bin_search1r(2*idx, s1, mid, s2, e2, x);
    }
    int bin_search2l(segtree &Tp, int idx, int s1, int e1, int s2, int e2, int x1, int x2){
        if(s1==e1){
            return ((f(seg[idx], x1)==seg[idx] || Tp.f(Tp.seg[idx], x2)==Tp.seg[idx]) ? s1 : 0);
        }
        if(s2>e1 || s1>e2) return 0;
        if(s2<=s1 && e1<=e2){
            if(f(seg[idx], x1)==seg[idx] || Tp.f(Tp.seg[idx], x2)==Tp.seg[idx]){
                int mid=(s1+e1)/2;
                int lres=bin_search2l(Tp, 2*idx, s1, mid, s2, e2, x1, x2);
                if(lres!=0) return lres;
                return bin_search2l(Tp, 2*idx+1, mid+1, e1, s2, e2, x1, x2);
            }
            else return 0;
        }
        int mid=(s1+e1)/2;
        if(s2<=mid){
            int lres=bin_search2l(Tp, 2*idx, s1, mid, s2, e2, x1, x2);
            if(lres!=0) return lres;
        }
        return bin_search2l(Tp, 2*idx+1, mid+1, e1, s2, e2, x1, x2);
    }
    int bin_search2r(segtree &Tp, int idx, int s1, int e1, int s2, int e2, int x1, int x2){
        if(s1==e1){
            return ((f(seg[idx], x1)==seg[idx] || Tp.f(Tp.seg[idx], x2)==Tp.seg[idx]) ? s1 : 0);
        }
        if(s2>e1 || s1>e2) return 0;
        if(s2<=s1 && e1<=e2){
            if(f(seg[idx], x1)==seg[idx] || Tp.f(Tp.seg[idx], x2)==Tp.seg[idx]){
                int mid=(s1+e1)/2;
                int rres=bin_search2r(Tp, 2*idx+1, mid+1, e1, s2, e2, x1, x2);
                if(rres!=0) return rres;
                return bin_search2r(Tp, 2*idx, s1, mid, s2, e2, x1, x2);
            }
            else return 0;
        }
        int mid=(s1+e1)/2;
        if(s2<=mid){
            int rres=bin_search2r(Tp, 2*idx+1, mid+1, e1, s2, e2, x1, x2);
            if(rres!=0) return rres;
        }
        return bin_search2r(Tp, 2*idx, s1, mid, s2, e2, x1, x2);
    }
};
segtree Tp, Tm, Tmax1, Tmin1, Tmax2, Tmin2;
int N, Q;
pii A[mxN];
pii qry[mxN];
vector <array<int, 3>> v1;
vector <array<int, 3>> ct1;
info I[mxN][2]; // left info, right info
int lim[mxN][2][3]; // left limit, right limit, 각각 plu/ minu/ neutral

int zero[mxN][2][3][4];
// zero[i][j][k][l] = i번째 쿼리에 대해, (j=0: 왼쪽, j=1: 오른쪽)에서 봤을 때 (k=0: left, k=1: right, k=2: neutral limit의 오른쪽/왼쪽)에 (l=0: 0+, l=1: 0-, l=2: +0, l=3: -0)를 만족하는 가장 (왼쪽/오른쪽) 위치
int ans[mxN];
bool cmpp(pii a, pii b){return (a.fi<=b.fi && a.se>=b.se);} // a.fi<=b.fi인 a의 max(a.se)를 관리
bool cmpm(pii a, pii b){return (a.fi>=b.fi && a.se<=b.se);} // a.fi>=b.fi인 a의 min(a.se)를 관리
bool cmpnp(pii a, pii b){return (a.fi>=b.fi || a.se<=b.se);}// max(a.fi), min(a.se)를 관리
bool cmpnm(pii a, pii b){return (a.fi<=b.fi || a.se>=b.se);}// min(a.fi), max(a.se)를 관리
bool chkdir(pii a, pii b, int typ){
    if(typ==0 && a.fi==b.fi && a.se>=b.se) return true;
    if(typ==1 && a.fi==b.fi && a.se<=b.se) return true;
    if(typ==2 && a.fi>=b.fi && a.se==b.se) return true;
    if(typ==3 && a.fi<=b.fi && a.se==b.se) return true;
    return false;
}
void input(){
    cin >> N >> Q;
    for(int i=1;i<=N;i++) cin >> A[i].fi >> A[i].se;
    for(int i=1;i<=Q;i++) cin >> qry[i].fi >> qry[i].se;
}
void make_cr(){
    vector <int> cx, cy;
    for(int i=1;i<=N;i++) cx.push_back(A[i].fi), cy.push_back(A[i].se);
    sort(all(cx)), sort(all(cy));
    cx.erase(unique(all(cx)), cx.end());
    cy.erase(unique(all(cy)), cy.end());
    for(int i=1;i<=N;i++) A[i].fi=lower_bound(all(cx), A[i].fi)-cx.begin()+1, A[i].se=lower_bound(all(cy), A[i].se)-cy.begin()+1;
    for(int i=1;i<=Q;i++){
        int i1=lower_bound(all(cx), qry[i].fi)-cx.begin(), i2=lower_bound(all(cy), qry[i].se)-cy.begin();
        if(i1==cx.size() || i2==cy.size() || cx[i1]!=qry[i].fi || cy[i2]!=qry[i].se) qry[i]=pii(N+1, N+1);
        else qry[i]=pii(i1+1, i2+1);
    }
}
void make_segtree(){
    Tmin1.init(N, 2); Tmax1.init(N, 1); Tmin2.init(N, 2); Tmax2.init(N, 1);
    for(int i=1;i<=N;i++){
        Tmin1.upd(1, 1, N, i, A[i].fi);
        Tmax1.upd(1, 1, N, i, A[i].fi);
        Tmax2.upd(1, 1, N, i, A[i].se);
        Tmin2.upd(1, 1, N, i, A[i].se);
    }
}
void make_ct1(){
    for(int i=1;i<=N;i++) v1.push_back({A[i].fi, A[i].se, i});
    for(int i=1;i<=Q;i++) ct1.push_back({qry[i].fi, qry[i].se, i});
    sort(all(v1), [](array<int, 3> a, array<int, 3> b){return a[0]<b[0];});
}
int bin_search1(segtree &T, int l, int r, int val, bool lr){
    int allres=T.solv(1, 1, N, l, r);
    if(T.f(allres, val)!=allres) return 0;
    if(lr) return T.bin_search1l(1, 1, N, l, r, val);
    else return T.bin_search1r(1, 1, N, l, r, val);
}
int bin_search2(segtree &T1, segtree &T2, int l, int r, pii val, bool lr){ // left면 lr이 true
    pii allres=pii(T1.solv(1, 1, N, l, r), T2.solv(1, 1, N, l, r));
    if(T1.f(allres.fi, val.fi)!=allres.fi && T2.f(allres.se, val.se)!=allres.se) return 0;
    if(lr) return T1.bin_search2l(T2, 1, 1, N, l, r, val.fi, val.se);
    else return T1.bin_search2r(T2, 1, 1, N, l, r, val.fi, val.se);
}
void make_info1(){
    int vi;
    
    sort(all(ct1), [](array<int, 3> a, array<int, 3> b){return a[0]<b[0];});
    vi=0;
    Tp.init(N, 1), Tm.init(N, 2);
    for(auto [val1, val2, idx] : ct1){
        while(vi!=v1.size() && v1[vi][0]<=val1){
            Tp.upd(1, 1, N, v1[vi][2], v1[vi][1]);
            vi++;
        }
        I[idx][0].plu[0]=bin_search1(Tp, 1, N, val2, 1);
        if(I[idx][0].plu[0]!=0 && I[idx][0].plu[0]!=N) I[idx][0].plu[1]=bin_search1(Tp, I[idx][0].plu[0]+1, N, val2, 1);
        I[idx][0].notp=bin_search2(Tmax1, Tmin2, 1, N, pii(val1, val2), 1);
        I[idx][0].notm=bin_search2(Tmin1, Tmax2, 1, N, pii(val1, val2), 1);

        I[idx][1].plu[0]=bin_search1(Tp, 1, N, val2, 0);
        if(I[idx][1].plu[0]!=0 && I[idx][1].plu[0]!=1) I[idx][1].plu[1]=bin_search1(Tp, 1, I[idx][0].plu[0]-1, val2, 0);
        I[idx][1].notp=bin_search2(Tmax1, Tmin2, 1, N, pii(val1, val2), 0);
        I[idx][1].notm=bin_search2(Tmin1, Tmax2, 1, N, pii(val1, val2), 0);
    }
    reverse(all(ct1));
    vi=N-1;
    for(auto [val1, val2, idx] : ct1){
        while(vi!=-1 && v1[vi][0]>=val1){
            Tm.upd(1, 1, N, v1[vi][2], v1[vi][1]);
            vi--;
        }
        I[idx][0].minu[0]=bin_search1(Tm, 1, N, val2, 1);
        if(I[idx][0].minu[0]!=0 && I[idx][0].minu[0]!=N) I[idx][0].minu[1]=bin_search1(Tm, I[idx][0].minu[0]+1, N, val2, 1);
        I[idx][1].minu[0]=bin_search1(Tm, 1, N, val2, 0);
        if(I[idx][1].minu[0]!=0 && I[idx][1].minu[0]!=1) I[idx][1].minu[1]=bin_search1(Tm, 1, I[idx][0].minu[0]-1, val2, 0);
    }
}
void make_lim(){
    for(int i=1;i<=Q;i++){
        info li=I[i][0], ri=I[i][1];

        //-- left limit
        if(li.plu[0]!=0 && (li.plu[0]==1 || (li.notm!=0 && li.plu[0]>li.notm))) lim[i][0][0]=li.plu[0];
        else if(li.plu[1]!=0) lim[i][0][0]=li.plu[1];
        if(li.minu[0]!=0 && (li.minu[0]==1 || (li.notp!=0 && li.minu[0]>li.notp))) lim[i][0][1]=li.minu[0];
        else if(li.minu[1]!=0) lim[i][0][1]=li.minu[1];
        if(li.notp!=0 && li.notm!=0) lim[i][0][2]=max(li.notp, li.notm);

        //-- right limit
        if(ri.plu[0]!=0 && (ri.plu[0]==N || (ri.notm!=0 && ri.plu[0]<ri.notm))) lim[i][1][0]=ri.plu[0];
        else if(ri.plu[1]!=0) lim[i][1][0]=ri.plu[1];
        if(ri.minu[0]!=0 && (ri.minu[0]==N || (ri.notp!=0 && ri.minu[0]<ri.notp))) lim[i][1][1]=ri.minu[0];
        else if(ri.minu[1]!=0) lim[i][1][1]=ri.minu[1];
        if(ri.notp!=0 && ri.notm!=0) lim[i][1][2]=min(ri.notp, ri.notm);
    }
}
vector <pii> v2[2][mxN];
vector <array<int, 4>> ct2[2][2][mxN];
segtree T0max, T0min;
// ct2[i][j][k]: (a[0], N] /i/ [1, a[0])에 있는 값들 중 (k, a[1]+), (k, a[1]-) /j/ (a[1]+, k), (a[1]-, k)인 값 찾아서 zero[a[2]][j][a[3]]에 넣기 (ct2[0]: left, ct2[1]: right)
void make_zero(){
    T0max.init(N, 1), T0min.init(N, 2);
    for(int i=1;i<=N;i++) v2[0][A[i].fi].emplace_back(A[i].se, i), v2[1][A[i].se].emplace_back(A[i].fi, i);

    for(int i=1;i<=Q;i++){
        for(int j=0;j<2;j++) for(int k=0;k<3;k++) if(lim[i][j][k]!=0){
            ct2[j][0][qry[i].fi].push_back({lim[i][j][k], qry[i].se, i, k});
            ct2[j][1][qry[i].se].push_back({lim[i][j][k], qry[i].fi, i, k});
        } 
    }
    for(int i=1;i<=N;i++){
        for(int j=0;j<2;j++){
            for(auto [y, idx] : v2[j][i]){
                T0max.upd(1, 1, N, idx, y);
                T0min.upd(1, 1, N, idx, y);
            }
            for(int dir=0;dir<=1;dir++){
                for(auto [pos, val, idx1, idx2] : ct2[dir][j][i]){
                    if(j==0 && dir==0 && pos!=N) zero[idx1][dir][idx2][0]=bin_search1(T0max, pos+1, N, val, 1);
                    if(j==0 && dir==1 && pos!=1) zero[idx1][dir][idx2][0]=bin_search1(T0max, 1, pos-1, val, 0);
                    if(j==0 && dir==0 && pos!=N) zero[idx1][dir][idx2][1]=bin_search1(T0min, pos+1, N, val, 1);
                    if(j==0 && dir==1 && pos!=1) zero[idx1][dir][idx2][1]=bin_search1(T0min, 1, pos-1, val, 0);
                    if(j==1 && dir==0 && pos!=N) zero[idx1][dir][idx2][2]=bin_search1(T0max, pos+1, N, val, 1);
                    if(j==1 && dir==1 && pos!=1) zero[idx1][dir][idx2][2]=bin_search1(T0max, 1, pos-1, val, 0);
                    if(j==1 && dir==0 && pos!=N) zero[idx1][dir][idx2][3]=bin_search1(T0min, pos+1, N, val, 1);
                    if(j==1 && dir==1 && pos!=1) zero[idx1][dir][idx2][3]=bin_search1(T0min, 1, pos-1, val, 0);
                }
            }
            for(auto [y, idx] : v2[j][i]){
                T0max.upd(1, 1, N, idx, 0);
                T0min.upd(1, 1, N, idx, 0);
            }
        }
    }
}
vector <pair<pii, int>> v00, vq;
segtree T3max, T3min;
bool possible(array<bool, 3> lcond, array<bool, 3> rcond, array<bool, 3> mcond, bool dir1, bool dir2){ // dir: (0+) or (-0), cond: + - 0
    if(mcond[0] && mcond[1]) return true;
    bool lp=(lcond[0] || (dir1 && lcond[2])), lm=(lcond[1] || (!dir1 && lcond[2]));
    bool rp=(rcond[0] || (dir2 && rcond[2])), rm=(rcond[1] || (!dir2 && rcond[2]));
    if(mcond[0] && (lm || rm)) return true;
    if(mcond[1] && (lp || rp)) return true;
    if((lp && rm) || (rp && lm)) return true;
    return false;
}
bool f(int idx, int lpos, int rpos, bool dir1, bool dir2){
    if(lpos==0 || rpos==0 || lpos>=rpos) return false;
    array<bool, 3> lcond, rcond, mcond={0, 0, 1};
    for(int j=0;j<3;j++) lcond[j]=(lim[idx][0][j]!=0 && lpos>lim[idx][0][j]);
    for(int j=0;j<3;j++) rcond[j]=(lim[idx][1][j]!=0 && rpos<lim[idx][1][j]);
    if(lpos==1) lcond[2]=1;
    if(rpos==N) rcond[2]=1;
    if(lpos==rpos-1){
        mcond[0]=mcond[1]=0;
    }
    else{
        int resp=T3max.solv(1, 1, N, lpos+1, rpos-1);
        mcond[0]=(resp!=0 && resp>=qry[idx].se);
        int resm=T3min.solv(1, 1, N, lpos+1, rpos-1);
        mcond[1]=(resm!=0 && resm<=qry[idx].se);
    }
    return possible(lcond, rcond, mcond, dir1, dir2);
}
void solv(){ // 나중에 sweeping으로 교체
    for(int i=1;i<=N;i++) v00.emplace_back(A[i], i);
    for(int i=1;i<=Q;i++) vq.emplace_back(qry[i], i);
    sort(all(v00)), sort(all(vq));
    T3max.init(N, 1), T3min.init(N, 2);
    int ulc=0, urc=0;
    for(int i=1;i<=N;i++) T3min.upd(1, 1, N, i, A[i].se);
    pii lqry[16], rqry[16];
    int lqi, rqi;
    int lc=0, rc=0;
    for(auto [qval, i] : vq){
        //-- segtree upd
        while(ulc!=N && v00[ulc].fi.fi<qval.fi){
            T3min.upd(1, 1, N, v00[ulc].se, 0);
            ulc++;
        }
        while(urc!=N && v00[urc].fi.fi<=qval.fi){
            T3max.upd(1, 1, N, v00[urc].se, v00[urc].fi.se);
            urc++;
        }
        // -- 00 case
        while(lc!=N && v00[lc].fi<qval) lc++;
        while(rc!=N && (v00[rc].fi<qval || v00[rc].fi==qval)) rc++;
        if(rc>=lc+3){
            ans[i]=1;
            continue;
        }
        for(int j=lc;j<rc;j++){
            int pos=v00[j].se;
            bool lnotp=(I[i][0].notp!=0 && I[i][0].notp<pos), lnotm=(I[i][0].notm!=0 && I[i][0].notm<pos);
            bool rnotp=(I[i][1].notp!=0 && I[i][1].notp>pos), rnotm=(I[i][1].notm!=0 && I[i][1].notm>pos);
            if(pos==1) lnotp=true, lnotm=true;
            if(pos==N) rnotp=true, rnotm=true;
            if(lnotp && lnotm && rnotp && rnotm) ans[i]=1;
        }
        if(ans[i]==1) continue;

        //-- 0x, x0 case 
        for(int j=0;j<16;j++) lqry[j]=rqry[j]=pii();
        lqi=0, rqi=0;
        for(int llvl=0;llvl<3;llvl++) for(int dir1=0;dir1<4;dir1++){
            int lpos=zero[i][0][llvl][dir1];
            if(lpos!=0) lqry[lqi++]={lpos, dir1};
        }
        if(A[1].fi==qry[i].fi || A[1].se==qry[i].se){
            for(int j=0;j<4;j++) if(chkdir(A[1], qry[i], j)){
                lqry[lqi++]={1, j};
            } 
        }
        for(int rlvl=0;rlvl<3;rlvl++) for(int dir2=0;dir2<4;dir2++){
            int rpos=zero[i][1][rlvl][dir2];
            if(rpos!=0) rqry[rqi++]={rpos, dir2};
        }
        if(A[N].fi==qry[i].fi || A[N].se==qry[i].se){
            for(int j=0;j<4;j++) if(chkdir(A[N], qry[i], j)){
                rqry[rqi++]={N, j};
            }
        }
        for(int j=0;j<lqi;j++) for(int k=0;k<rqi;k++){
            if(ans[i]==1) break;
            auto [lpos, dir1]=lqry[j];
            auto [rpos, dir2]=rqry[k];
            if((dir1<2 && dir2<2) || (dir1>=2 && dir2>=2)) continue;
            if(f(i, lpos, rpos, (dir1==0 || dir1==3), (dir2==0 || dir2==3))) ans[i]=1;
        }

    }
}
int main(){
    gibon
    input();
    make_cr();
    make_segtree();
    make_ct1();
    make_info1();
    make_lim();
    make_zero();
    solv();
    for(int i=1;i<=Q;i++) if(ans[i]) cout << i << " ";
}

Compilation message (stderr)

Main.cpp: In function 'void make_cr()':
Main.cpp:176:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  176 |         if(i1==cx.size() || i2==cy.size() || cx[i1]!=qry[i].fi || cy[i2]!=qry[i].se) qry[i]=pii(N+1, N+1);
      |            ~~^~~~~~~~~~~
Main.cpp:176:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  176 |         if(i1==cx.size() || i2==cy.size() || cx[i1]!=qry[i].fi || cy[i2]!=qry[i].se) qry[i]=pii(N+1, N+1);
      |                             ~~^~~~~~~~~~~
Main.cpp: In function 'void make_info1()':
Main.cpp:213:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  213 |         while(vi!=v1.size() && v1[vi][0]<=val1){
      |               ~~^~~~~~~~~~~

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