(10810) 공 넣기

https://www.acmicpc.net/problem/10810

단계별로 풀어보기

4단계(1차원 배열) 5번째

 

 

 

알고리즘 공부를 하고 다시 푸니 정말 놀랍게도 느리게 갱신되는 세그먼트 트리나 오프라인 쿼리로 최적화가 가능하다는 것이 보인다.

(물론 N과 M의 범위가 워낙 작아서 그럴 필요는 없다.)

 

 

 

#include <iostream>
#include <vector>
using namespace std;

int main() 
{
  int n, m;
  
  cin >> n >> m;
  
  vector<int> v(n+1);
  
  while(m--){
    int i, j, k;
    
    cin >> i >> j >> k;
    
    for(int x=i;x<=j;x++)  v[x]= k;
  }
  
  for(int x=1;x<=n;x++)  cout << v[x] << " ";
  
  return 0;
}