Submission #1224717

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224717		noyancanturk	Card Collection (JOI24_collection)	C++20	0 / 100	0 ms	328 KiB

Main

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

#define pb push_back

int main(){
  int n,q;
  cin>>n>>q;
  int a[n],b[n];
  vector<int>v;
  for(int i=0;i<n;i++){
    cin>>a[i]>>b[i];
    v.pb(a[i]);
    v.pb(b[i]);
  }
  sort(v.begin(),v.end());
  int m=v.size();
  map<int,int>tr;
  for(int i=0;i<m;i++){
    tr[v[i]]=i;
  }
  int have1[m]{},have2[m]{};
  for(int i=0;i<n;i++){
    have1[a[i]=tr[a[i]]]++;
    have2[b[i]=tr[b[i]]]++;
  }
  int mini1[m]{},maxi1[m]{},mini2[m]{},maxi2[m]{};
  for(int i=0;i<m;i++){
    mini1[i]=mini2[i]=INT_MAX;
  }
  for(int i=0;i<n;i++){
    mini1[a[i]]=min(mini1[a[i]],b[i]);
    maxi1[a[i]]=max(maxi1[a[i]],b[i]);
    mini2[b[i]]=min(mini2[b[i]],a[i]);
    maxi2[b[i]]=max(maxi2[b[i]],a[i]);
  }
  int mn1[m]{},mx1[m]{},mn2[m]{},mx2[m]{};
  mn1[m-1]=mini1[m-1];
  mx1[0]=maxi1[0];
  mn2[m-1]=mini2[m-1];
  mx2[0]=maxi2[0];
  for(int i=1;i<m;i++){
    mn1[m-i-1]=min(mini1[m-i-1],mn1[m-i]);
    mx1[i]=min(maxi1[i],mx1[i-1]);
    mn2[m-i-1]=min(mini2[m-i-1],mn2[m-i]);
    mx2[i]=min(maxi2[i],mx2[i-1]);
  }
  sort(a,a+n);
  sort(b,b+n);
  for(int ind=1;ind<=q;ind++){
    int x,y;
    cin>>x>>y;
    if(!tr.count(x)||!tr.count(y))continue;
    x=tr[x],y=tr[y];
    if(!have1[x]||!have2[y])continue;
    if(have1[x]==1&&have2[y]==1&&mini1[x]==y){
      if((x==a[0]&&y==b[n-1])||(x==a[n-1]&&y==b[0])){
        
      }else{
        cout<<ind<<' ';
      }
      continue;
    }
    if((mn1[x]<=y&&mn2[y]<=x)||(y<=mx1[x]&&x<=mx2[y])){
      cout<<ind<<' ';
    }
  }
}

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