Submission #1282291

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282291		repmann	Wall (IOI14_wall)	C++20	100 / 100	535 ms	59184 KiB

wall

#include <bits/stdc++.h>
using namespace std;
int N, K, Q;
struct Node
{
  int l, r;
}ST[8000001];
inline void Setup()
{
  K = 1;
  while(K < N) K <<= 1;
  for(int i = 1; i <= (N + K - 1); i++) {ST[i].l = 0; ST[i].r = 0;}
  return;
}
inline void Merge(int i)
{
  ST[i].l = min(ST[i << 1].l, ST[i << 1 | 1].l);
  ST[i].r = max(ST[i << 1].r, ST[i << 1 | 1].r);
  return;
}
inline void Propagate(int i)
{
  if(i >= K) return;
  ST[i << 1].l = max(ST[i].l, ST[i << 1].l);
  ST[i << 1].r = min(ST[i].r, ST[i << 1].r);
  if(ST[i << 1].l > ST[i << 1].r)
  {
    if((ST[i].l <= ST[i << 1].l) && (ST[i << 1].l <= ST[i].r)) ST[i << 1].r = ST[i << 1].l;
    else ST[i << 1].l = ST[i << 1].r;
  }
  ST[i << 1 | 1].l = max(ST[i].l, ST[i << 1 | 1].l);
  ST[i << 1 | 1].r = min(ST[i].r, ST[i << 1 | 1].r);
  if(ST[i << 1 | 1].l > ST[i << 1 | 1].r)
  {
    if((ST[i].l <= ST[i << 1 | 1].l) && (ST[i << 1 | 1].l <= ST[i].r)) ST[i << 1 | 1].r = ST[i << 1 | 1].l;
    else ST[i << 1 | 1].l = ST[i << 1 | 1].r;
  }
  return;
}
inline void Finish()
{
  for(int i = 1; i < K; i++) Propagate(i);
  return;
}
inline void Update(int L, int R, int T, int X, int i = 1, int LC = 1, int RC = K)
{
  Propagate(i);
  if((LC > R) || (L > RC)) return;
  if((L <= LC) && (RC <= R))
  {
    if(T == 1) {ST[i].l = max(X, ST[i].l); ST[i].r = max(X, ST[i].r);}
    if(T == 2) {ST[i].l = min(X, ST[i].l); ST[i].r = min(X, ST[i].r);}
    Propagate(i);
    return;
  }
  int S = (LC + RC) >> 1;
  Update(L, R, T, X, i << 1, LC, S);
  Update(L, R, T, X, i << 1 | 1, S + 1, RC);
  Merge(i);
  return;
}
void buildWall(int n, int q, int t[], int l[], int r[], int x[], int O[])
{
  N = n;
  Q = q;
  Setup();
  for(int i = 0; i < Q; i++) Update(l[i] + 1, r[i] + 1, t[i], x[i]);
  Finish();
  for(int i = 0; i < N; i++) O[i] = ST[i + K].l;
  return;
}
//int main()
//{
//  int n, q;
//  cin >> n >> q;
//  int t[q], l[q], r[q], x[q], o[n];
//  for(int i = 0; i < q; i++) cin >> t[i] >> l[i] >> r[i] >> x[i];
//  buildWall(n, q, t, l, r, x, o);
//  for(int i = 0; i < n; i++) cout << o[i] << " \n"[i == (n - 1)];
//  return 0;
//}

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