백준 2336 : 굉장한 학생

문제 링크

이 문제는 여기의 d번 문제와 비슷하다 라는 생각을 가지고 대단한 학생인 집합들을 union-find해주면서 해결할 수 있을꺼라는 생각을 하고 접근했지만, n이 7000이하인 D번 문제와는 달리 n이 50만 이하이기 때문에 그런 접근 자체가 불가능했다. 끝없는 삽질 끝에 결국 풀이를 보고 해결하였다.

세그먼트 트리를 이용하여 해결할 수 있는데, 먼저 첫 시험을 기준으로 정렬을 해준 다음, 차례대로 보면서 해결하게 된다. k번째 원소를 보게 될 때, 첫 시험에서 k등보다 낮은 등수를 받은 사람들은 이미 대단한 학생일 수가 없으니, 그 전 원소들 중 k번째 원소보다 두번째, 세번째 시험의 등수가 모두 높은 사람이 있는지 확인해 주면 된다. 최소 세그먼트 트리를 이용하여 해결하는데, 초기값을 모두 INF로 두고, 원소를 순회할 때마다, vec[2번째 시험 등수] = 3번째 시험 등수 로 업데이트를 해준다. 그 뒤 k번째 원소를 볼 때는, 0~원소의 두번째 시험 등수 에서 최솟값을 찾아 원소의 3번째 시험 점수와 비교하면 대단한 학생의 유무를 알아낼 수 있다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
#include <string>
#include <stack>

using namespace std;

typedef pair<int,int> pii;
typedef long long ll;

const int INF = 987654321;
const int mod = 1e9 + 7;

struct test{   
   int x,y,z;

   test(int _x =0,int _y = 0,int _z = 0) : x(_x),y(_y),z(_z)
   {}

   bool operator<(const test& rhs)
   {
       return x < rhs.x;
   }    
};

int n;
vector<test> vec;
vector<int> segtree;

int update(int newidx,int k,int idx,int s,int e)
{

   if(!(s <= newidx && newidx <= e)) return INF;

   if(s == e) return segtree[idx] = k;

   int m = (s+e)/2;
   update(newidx,k,2*idx,s,m);
   update(newidx,k,2*idx+1,m+1,e);

   return segtree[idx] = min(segtree[2*idx],segtree[2*idx+1]);
}

int get(int qs,int qe,int idx,int s,int e)
{
   if(qe < s || e < qs) return INF;

   if(qs <= s && e <= qe) return segtree[idx];

   int m = (s+e)/2;

   return min(get(qs,qe,2*idx,s,m),get(qs,qe,2*idx+1,m+1,e));
}

int main(int argc, char** argv) {
	ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

   cin>>n;
   vec = vector<test>(n);
   segtree = vector<int>(4*n,INF);
   for(int j = 0;j<3;j++)
   {
       for(int i = 0;i<n;i++)
       {
           int stu;
           cin>>stu;
           stu--;

           if(j == 0)
           {
               vec[stu].x = i;
           } 
           if(j == 1)
           {
               vec[stu].y = i;
           } 
           if(j == 2)
           {
               vec[stu].z = i;
           } 
       }
   }

   sort(vec.begin(),vec.end());

   int ans = 1;
   update(vec[0].y,vec[0].z,1,0,n-1);

   for(int i = 1;i<n;i++)
   {        
       int minz = get(0,vec[i].y,1,0,n-1);

       //cout<<minz<<" "<<vec[i].z<<endl;

       if(minz > vec[i].z) 
       {
           
           ans++;
       }

       update(vec[i].y,vec[i].z,1,0,n-1);
   }

   cout<<ans;
	return 0;
}
​