Submission #1209633

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209633		lighton	Card Collection (JOI24_collection)	C++20	0 / 100	0 ms	460 KiB

Main

#include<bits/stdc++.h>
#define pb push_back
#define all(v) v.begin(),v.end()
#define forf(i,s,e) for(int i = s; i<=e; i++)
#define forb(i,s,e) for(int i = s; i>=e; i--)
#define idx(i,v) lower_bound(all(v),i)-v.begin()
#define comp(v) v.erase(unique(all(v)),v.end())
#define sz(v) (int)v.size()
#define fs first
#define se second
#define SP << " " <<
#define LN << "\n"
#define IO cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false);
using namespace std;
typedef long long ll;
int inf = 2e9;
int N,M;
bool dp[2001][2001][3][3];
int AA[200001], BB[200001];
int A[200001],B[200001];
int pA[2][200005], sA[2][200005], pB[2][200005], sB[2][200005];

int cmp(int a, int b){
    if(a<b) return -1;
    if(a==b) return 0;
    return 1;
}

int solve(){
    int f = 0, s1 = N+1, s2 = N+1;

    forf(i,1,N){
        if(!((A[i] == 1) && (B[i] == -1))) f = 1;
        if(A[i] == 0) s1 = min(s1, i);
        if((f || i == 1) && A[i] <= 0 && B[i] >= 0) s2 = min(s2,i);
    }
    int s = max(s1,s2);

    int e1 = 0, e2 = 0; f = 0;
    forb(i,N,1){
        if(!((A[i] == -1) && (B[i] == 1))) f = 1;
        if(B[i] == 0) e1 = max(e1,i);
        if((f || i == N) && A[i] >= 0 && B[i] <= 0) e2 = max(e2,i);
    }

    int e = min(e1,e2);
    if(s<e) return 1;
    return 0;
}

int main(){
    cin>>N>>M;
    forf(i,1,N) cin>>AA[i]>>BB[i];
    pA[0][0] = pB[0][0] = sA[0][N+1] = sB[0][N+1] = inf;
    pA[1][0] = pB[1][0] = sA[1][N+1] = sB[1][N+1] = -inf;
    forf(i,1,N) pA[0][i] = min(pA[0][i-1], AA[i]), pB[0][i] = min(pB[0][i-1], BB[i]),
                pA[1][i] = max(pA[1][i-1], AA[i]), pB[1][i] = max(pB[1][i-1], BB[i]);
    forb(i,N,1) sA[0][i] = min(sA[0][i+1], AA[i]), sB[0][i] = min(sB[0][i+1], BB[i]),
                sA[1][i] = max(sA[1][i+1], AA[i]), sB[1][i] = max(sB[1][i+1], BB[i]);


    forf(q,1,M){
        int X,Y; cin>>X>>Y;
        int f = 0;
        forf(i,1,N) A[i] = cmp(AA[i],X), B[i] = cmp(BB[i],Y);
        forf(i,1,N) if(A[i] == 0 && B[i] == 0){
            int c = 1;
            if(i!=1 && (pA[1][i-1] < X && pB[0][i-1] > Y) || (pA[0][i-1] > X && pB[1][i-1] < Y)) c = 0;
            if(i!=N && (sA[1][i+1] < X && sB[0][i+1] > Y) || (sA[0][i+1] > X && sB[1][i+1] < Y)) c = 0;
            if(c) f = 1;
        }
        if(solve()) f = 1;
        forf(i,1,N) A[i] = -A[i], B[i] = -B[i];
        if(solve()) f = 1;
        forf(i,1,N) swap(A[i],B[i]);
        if(solve()) f = 1;
        forf(i,1,N) A[i] = -A[i], B[i] = -B[i];
        if(solve()) f = 1;
        if(f) cout<<q<< " ";
    }
}

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