oj.uz

Submission #555058

# Submission time Handle Problem Language Result Execution time Memory
555058 2022-04-30T05:35:16 Z AriaH Wall (IOI14_wall) C++17
100 / 100
 711 ms 75596 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 8 ms 832 KB Output is correct
5 Correct 4 ms 852 KB Output is correct
6 Correct 5 ms 852 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 139 ms 8124 KB Output is correct
3 Correct 67 ms 4388 KB Output is correct
4 Correct 161 ms 11724 KB Output is correct
5 Correct 178 ms 12268 KB Output is correct
6 Correct 184 ms 12348 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 6 ms 828 KB Output is correct
5 Correct 5 ms 852 KB Output is correct
6 Correct 5 ms 852 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 137 ms 8156 KB Output is correct
9 Correct 71 ms 4400 KB Output is correct
10 Correct 163 ms 11724 KB Output is correct
11 Correct 164 ms 12328 KB Output is correct
12 Correct 180 ms 12252 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 137 ms 8152 KB Output is correct
15 Correct 30 ms 1716 KB Output is correct
16 Correct 516 ms 12080 KB Output is correct
17 Correct 258 ms 12088 KB Output is correct
18 Correct 257 ms 12044 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 6 ms 852 KB Output is correct
5 Correct 5 ms 852 KB Output is correct
6 Correct 5 ms 868 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 134 ms 8136 KB Output is correct
9 Correct 71 ms 4512 KB Output is correct
10 Correct 164 ms 11776 KB Output is correct
11 Correct 168 ms 12260 KB Output is correct
12 Correct 197 ms 12272 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 136 ms 8216 KB Output is correct
15 Correct 29 ms 1748 KB Output is correct
16 Correct 494 ms 12016 KB Output is correct
17 Correct 258 ms 12004 KB Output is correct
18 Correct 262 ms 11976 KB Output is correct
19 Correct 693 ms 75540 KB Output is correct
20 Correct 686 ms 73020 KB Output is correct
21 Correct 697 ms 75496 KB Output is correct
22 Correct 692 ms 73052 KB Output is correct
23 Correct 689 ms 73060 KB Output is correct
24 Correct 683 ms 73184 KB Output is correct
25 Correct 696 ms 72968 KB Output is correct
26 Correct 692 ms 75596 KB Output is correct
27 Correct 703 ms 75496 KB Output is correct
28 Correct 685 ms 72960 KB Output is correct
29 Correct 711 ms 73000 KB Output is correct
30 Correct 705 ms 73016 KB Output is correct