제출 #1281250

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1281250		repmann	벽 (IOI14_wall)	C++20	32 / 100	150 ms	21212 KiB

wall

#include <bits/stdc++.h>
using namespace std;
int N, Q;
vector <pair <int, int>> V[100000];
void buildWall(int n, int q, int t[], int l[], int r[], int x[], int O[])
{
  N = n;
  Q = q;
  for(int i = 0; i < N; i++) O[i] = 0;
  if(N <= 10000)
  {
    for(int i = 0; i < N; i++) O[i] = 0;
    for(int i = 0; i < Q; i++)
    {
      if(t[i] == 1) for(int j = l[i]; j <= r[i]; j++) O[j] = max(x[i], O[j]);
      if(t[i] == 2) for(int j = l[i]; j <= r[i]; j++) O[j] = min(x[i], O[j]);
    }
    return;
  }
  for(int i = 0; i < Q; i++) if(t[i] == 1) V[l[i]].push_back({x[i], r[i]});
  priority_queue <pair <int, int>> H;
  H.push({0, INT_MAX});
  for(int i = 0; i < N; i++)
  {
    for(pair <int, int> p : V[i]) H.push(p);
    while(H.top().second < i) H.pop();
    O[i] = H.top().first;
  }
  for(int i = 0; i < N; i++) V[i] = vector <pair <int, int>>();
  for(int i = 0; i < Q; i++) if(t[i] == 2) V[l[i]].push_back({x[i], r[i]});
  while(H.size()) H.pop();
  for(int i = 0; i < N; i++)
  {
    for(pair <int, int> p : V[i]) H.push({-p.first, p.second});
    while(H.size() && (H.top().second < i)) H.pop();
    if(H.size()) O[i] = min(-H.top().first, O[i]);
  }
  return;
}

• Subtask 1: 8 / 8
• Subtask 2: 24 / 24
• Subtask 3: 0 / 29
• Subtask 4: 0 / 39