Submission #555058

#	Time	Username	Problem	Language	Result	Execution time	Memory
555058		AriaH	Wall (IOI14_wall)	C++17	100 / 100	711 ms	75596 KiB

wall

#include "wall.h"

#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair < int, int > pii;
typedef pair < ll, ll > pll;

#define F first
#define S second
#define all(x) x.begin(),x.end()
#define Mp make_pair
#define point complex
#define endl '\n'
#define SZ(x) (int)x.size()
#define fast_io ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define file_io freopen("input.txt", "r+", stdin); freopen("output.txt", "w+", stdout);
#define mashtali return cout << "Hello, World!", 0;

const int N = 2e6 + 10;
const int LOG = 20;
const ll mod = 1e9 + 7;
const ll inf = 8e18;
const double pi = acos(-1);
const ld eps = 1e-18;
const ld one = 1.;

ll pw(ll a, ll b, ll M, ll ret = 1) { if(a == 0) return 0; a %= M; while(b) { ret = (b & 1? ret * a % M : ret), a = a * a % M, b >>= 1; } return ret % M; }

mt19937 rng(time(nullptr));

int n, k, Mn[N << 2], Mx[N << 2], lz[N << 2];

void S(int v, int tl, int tr)
{
  if(lz[v] == -1 || tl == tr) return;
  Mn[v << 1] = Mx[v << 1] = Mn[v << 1 | 1] = Mx[v << 1 | 1] = lz[v << 1] = lz[v << 1 | 1] = lz[v];
  lz[v] = -1;
}

void upd(int l, int r, int x, int v = 1, int tl = 0, int tr = n - 1) /// baraye min
{
  S(v, tl, tr);
  if(l > tr || r < tl || Mx[v] <= x) return;
  if(l <= tl && tr <= r && Mn[v] == Mx[v])
  {
    Mx[v] = Mn[v] = lz[v] = x;
    return;
  }
  int mid = (tl + tr) >> 1;
  upd(l, r, x, v << 1, tl, mid), upd(l, r, x, v << 1 | 1, mid + 1, tr);
  Mn[v] = min(Mn[v << 1], Mn[v << 1 | 1]);
  Mx[v] = max(Mx[v << 1], Mx[v << 1 | 1]);
}

void UPD(int l, int r, int x, int v = 1, int tl = 0, int tr = n - 1)
{
  S(v, tl, tr);
  if(l > tr || r < tl || Mn[v] >= x) return;
  if(l <= tl && tr <= r && Mx[v] == Mn[v])
  {
    Mn[v] = Mx[v] = lz[v] = x;
    return;
  }
  int mid = (tl + tr) >> 1;
  UPD(l, r, x, v << 1, tl, mid), UPD(l, r, x, v << 1 | 1, mid + 1, tr);
  Mx[v] = max(Mx[v << 1], Mx[v << 1 | 1]);
  Mn[v] = min(Mn[v << 1], Mn[v << 1 | 1]);
}

int get(int p, int v = 1, int tl = 0, int tr = n - 1)
{
  S(v, tl, tr);
  if(tl == tr) return Mx[v];
  int mid = (tl + tr) >> 1;
  if(p <= mid) return get(p, v << 1, tl, mid);
  else return get(p, v << 1 | 1, mid + 1, tr);
}

void buildWall(int _n, int _k, int op[], int left[], int right[], int height[], int finalHeight[])
{
  n = _n;
  k = _k;
  for(int i = 0; i < k; i ++)
  {
    if(op[i] == 1)
    {
      UPD(left[i], right[i], height[i]);
    }
    else
    {
      upd(left[i], right[i], height[i]);
    }
  }
  for(int i = 0; i < n; i ++)
  {
    finalHeight[i] = get(i);
  }
}

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