oj.uz

Submission #588117

# Submission time Handle Problem Language Result Execution time Memory
588117 2022-07-02T17:42:29 Z Red_Inside Wall (IOI14_wall) C++17
100 / 100
 1002 ms 174320 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define f first
#define s second
#define all(v) v.begin(), v.end()
#define IOS ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define mp make_pair
#define o cout<<"BUG"<<endl;
#define FOR(i, j, n) for(int j = i; j < n; ++j)
#define forn(i, j, n) for(int j = i; j <= n; ++j)
#define nfor(i, j, n) for(int j = n; j >= i; --j)

const int maxn = 2e6+100;

int inf = 1e9;

int n, t[4*maxn][3], l[maxn], r[maxn], ty[maxn], x[maxn];
vector <int> start[maxn], fin[maxn];

void upd(int v, int tl, int tr, int pos, int val, int x)
{
	if(pos < tl || tr < pos) return;
	if(tl == tr)
	{
		t[v][x] = val;
		return;
	}
	upd(v * 2, tl, (tl + tr) / 2, pos, val, x);
	upd(v * 2 + 1, (tl + tr) / 2 + 1, tr, pos, val, x);
	t[v][1] = max(t[v * 2][1], t[v * 2 + 1][1]);
	t[v][2] = min(t[v * 2][2], t[v * 2 + 1][2]);
}

int get(int v, int tl, int tr, int lboun = 0, int rboun = inf)
{
//	cout << "GET " << tl << " " << tr << " " << t[v][1] << " " << t[v][2] << endl;
	if(tl == tr)
	{
		if(max(lboun, t[v][1]) <= min(rboun, t[v][2]))
		{
			return max(lboun, t[v][1]);
		}
//		cout << "!!! " << tl << endl;
		if(ty[tl] == 1)
			return min(rboun, t[v][2]);
		else
			return max(lboun, t[v][1]);
	}
	if(max(lboun, t[v * 2 + 1][1]) >= min(rboun, t[v * 2 + 1][2]))
		return get(v * 2 + 1, (tl + tr) / 2 + 1, tr, lboun, rboun);
	else
		return get(v * 2, tl, (tl + tr) / 2, max(lboun,t[v*2+1][1]), min(rboun, t[v*2+1][2]));
}

void build(int v, int tl, int tr)
{
	t[v][1] = 0;
	t[v][2] = inf;
	if(tl == tr)
	{
		return;
	}
	build(v * 2, tl, (tl + tr) / 2);
	build(v * 2 + 1, (tl + tr) / 2 + 1, tr);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
	forn(1, i, k)
	{
		ty[i] = op[i-1];
		l[i] = left[i-1]+1;
		r[i] = right[i-1]+1;
		x[i] = height[i-1];
	}
	build(1, 1, k);
	forn(1, i, k)
	{
		start[l[i]].pb(i);
		fin[r[i]].pb(i);
	}
	forn(1, iter, n)
	{
		for(auto i : start[iter])
		{
//			cout << "UPDATE " << i << " " << x[i] << " " << ty[i] << endl;
			upd(1, 1, k, i, x[i], ty[i]);
		}
//		cout << "LAUNCH GET FOR " << iter << endl;
		int go = get(1, 1, k);
		finalHeight[iter-1] = go;
		for(auto i : fin[iter])
		{
//			cout << "DELETE " << i << endl;
			upd(1, 1, k, i, (ty[i] == 1 ? 0 : inf), ty[i]);
		}
	}
}
/*int main()
{
  int n;
  int k;

  int i, j;  
  int status = 0;

  status = scanf("%d%d", &n, &k);
  assert(status == 2);

  int* op = (int*)calloc(sizeof(int), k);
  int* left = (int*)calloc(sizeof(int), k);
  int* right = (int*)calloc(sizeof(int), k);
  int* height = (int*)calloc(sizeof(int), k);
  int* finalHeight = (int*)calloc(sizeof(int), n);

  for (i = 0; i < k; i++){
    status = scanf("%d%d%d%d", &op[i], &left[i], &right[i], &height[i]);
    assert(status == 4);
  }

  buildWall(n, k, op, left, right, height, finalHeight);

  for (j = 0; j < n; j++)
    printf("%d\n", finalHeight[j]);
  
  return 0;
}*/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 94156 KB Output is correct
2 Correct 48 ms 94748 KB Output is correct
3 Correct 47 ms 94432 KB Output is correct
4 Correct 49 ms 95016 KB Output is correct
5 Correct 51 ms 94924 KB Output is correct
6 Correct 52 ms 94972 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 94244 KB Output is correct
2 Correct 386 ms 130608 KB Output is correct
3 Correct 291 ms 112424 KB Output is correct
4 Correct 769 ms 136512 KB Output is correct
5 Correct 504 ms 131584 KB Output is correct
6 Correct 452 ms 131340 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 94232 KB Output is correct
2 Correct 54 ms 94692 KB Output is correct
3 Correct 48 ms 94432 KB Output is correct
4 Correct 52 ms 95028 KB Output is correct
5 Correct 49 ms 94924 KB Output is correct
6 Correct 51 ms 94940 KB Output is correct
7 Correct 44 ms 94264 KB Output is correct
8 Correct 390 ms 130360 KB Output is correct
9 Correct 282 ms 113960 KB Output is correct
10 Correct 783 ms 136440 KB Output is correct
11 Correct 481 ms 132852 KB Output is correct
12 Correct 427 ms 132100 KB Output is correct
13 Correct 45 ms 94200 KB Output is correct
14 Correct 408 ms 130024 KB Output is correct
15 Correct 79 ms 97484 KB Output is correct
16 Correct 800 ms 138112 KB Output is correct
17 Correct 467 ms 135816 KB Output is correct
18 Correct 499 ms 135540 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 94160 KB Output is correct
2 Correct 60 ms 94748 KB Output is correct
3 Correct 64 ms 94420 KB Output is correct
4 Correct 71 ms 94964 KB Output is correct
5 Correct 57 ms 94956 KB Output is correct
6 Correct 57 ms 94968 KB Output is correct
7 Correct 48 ms 94228 KB Output is correct
8 Correct 421 ms 130352 KB Output is correct
9 Correct 296 ms 113968 KB Output is correct
10 Correct 788 ms 136600 KB Output is correct
11 Correct 480 ms 134344 KB Output is correct
12 Correct 537 ms 133996 KB Output is correct
13 Correct 48 ms 94148 KB Output is correct
14 Correct 442 ms 129792 KB Output is correct
15 Correct 76 ms 97444 KB Output is correct
16 Correct 787 ms 138136 KB Output is correct
17 Correct 440 ms 135880 KB Output is correct
18 Correct 471 ms 135680 KB Output is correct
19 Correct 902 ms 169080 KB Output is correct
20 Correct 733 ms 171800 KB Output is correct
21 Correct 778 ms 174256 KB Output is correct
22 Correct 802 ms 171780 KB Output is correct
23 Correct 784 ms 171696 KB Output is correct
24 Correct 1002 ms 171776 KB Output is correct
25 Correct 905 ms 171772 KB Output is correct
26 Correct 802 ms 174312 KB Output is correct
27 Correct 767 ms 174320 KB Output is correct
28 Correct 831 ms 171664 KB Output is correct
29 Correct 785 ms 171752 KB Output is correct
30 Correct 781 ms 171836 KB Output is correct