글 읽기 - RTE....

race0630 6년 전 0

도대체 RTE가 왜 나는 걸까요?

-----풀이방법-----

segment tree를 이용했고, 정렬을 사용하여 각 선수들끼리의 평소실력 순위를 정한다.

그 후 지금 순위대로 순차적으로 탐색하며 방문할 시 값을 0에서 1로 바꾸어주면서 update하고

자신의 앞에 자신보다 잘하는 놈이 한명 있을때마다 순위가 1씩 내려가므로 지금위치+1 부터 끝까지 합한것+1이 최종순위가 된다.

(뭔소리지?)

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pi;

vector<ll> tr; //tree
vector<ll> kk; //visit-map
vector<pi> tp; //input
ll d;

ll _init(ll start, ll end, ll index) { //segment tree 생성
  if(start==end) return tr[index]=kk[start];
  else return tr[index]=_init(start, (start+end)/2, index*2)+_init(((start+end)/2+1), end, index*2+1);
}

ll _sum(ll start, ll end, ll left, ll right, ll index) { //합 구하기
  if(end<left || right<start) return 0;
  else if(left<=start && end<=right) return tr[index];
  else return _sum(start, (start+end)/2, left, right, index*2)+_sum(((start+end)/2+1),end, left, right, index*2+1);
}

void _modify(ll start, ll end, ll index, ll modnd, ll diff) { //변형하기
  if(modnd<start || end<modnd) return;
  tr[index]+=diff;
  if(start!=end){_modify(start, (start+end)/2, index*2, modnd, diff);_modify(((start+end)/2+1), end, index*2+1, modnd,  diff);}
  return;
}

int main() {
  ll N;
  cin>>N;
  for(ll i=0;i<N;i++) {
    ll k;
    cin>>k;
    tp.push_back(pi(k, i));
  } //input
  
  //평소 실력의 상대적 크기를 정함
  sort(tp.begin(),tp.end());
  for(ll i=0;i<N;i++) tp[i].first=i;
  for(ll i=0;i<N;i++) swap(tp[i].first, tp[i].second);
  sort(tp.begin(),tp.end());
  
  
  tr.resize(2*N+3);
  kk.resize(N+1);
  _init(0, N-1, 1); //segment tree 생성
  for(ll i=0;i<N;i++) {
    _modify(0, N-1,1,tp[i].second, 1); //자신의 위치에 해당하는 곳을 0->1로 체인지
    cout<<_sum(0,N-1, tp[i].second+1, N-1, 1)+1<<endl; //자신의 앞에 자신보다 잘하는 놈이 한명 있을때마다 순위가 1씩 내려감
  }

  return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

RTE....

race0630 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말