Submission #392399

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
392399	2021-04-21T04:09:52 Z	arwaeystoamneg	Wall (IOI14_wall)	C++17	100 / 100	1112 ms	102356 KB

wall

// EXPLOSION!
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
#include<chrono>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pair<int, int>> vpi;
typedef vector<pair<ll, ll>> vpll;

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

#define pb push_back
#define mp make_pair
#define rsz resize
#define sz(x) int(x.size())
#define all(x) x.begin(),x.end()
#define f first
#define s second
#define cont continue
#define endl '\n'
//#define ednl '\n'
#define test int testc;cin>>testc;while(testc--)
#define pr(a, b) trav(x,a)cerr << x << b; cerr << endl;
#define message cout << "Hello World" << endl;
const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 }; // for every grid problem!!
const ll linf = 4000000000000000000LL;
const ll inf = 1000000007;//998244353    

void pv(vi a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vll a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vector<vi>a) {
	F0R(i, sz(a)) { cout << i << endl; pv(a[i]); cout << endl; }
}void pv(vector<vll>a) { F0R(i, sz(a)) { cout << i << endl; pv(a[i]); }cout << endl; }void pv(vector<string>a) { trav(x, a)cout << x << endl; cout << endl; }
void setIO(string s) {
	ios_base::sync_with_stdio(0); cin.tie(0);
	if (sz(s))
	{
		freopen((s + ".in").c_str(), "r", stdin);
		if (s != "test1")
			freopen((s + ".out").c_str(), "w", stdout);
	}
}
#ifndef arwaeystoamneg
#include "wall.h";
#endif
const int SZ = 22;
const int MAX = 1 << SZ, MAX_H = 100000;
struct T
{
	int l, r, d;
	T()
	{
		l = 0, r = MAX_H, d = 0;
	}
	void left(int x)
	{
		if (d == 0)
		{
			if (x > l)
			{
				d = 1;
				l = x;
			}
			else
			{
				if (r < x)
				{
					l = r = x;
					d = 0;
				}
			}
		}
		else
		{
			l = max(l, x);
		}
	}
	void right(int x)
	{
		if (d == 1)
		{
			if (x < r)
			{
				d = 0;
				r = x;
			}
			else
			{
				if (l > x)
				{
					l = r = x;
					d = 0;
				}
			}
		}
		else
		{
			r = min(r, x);
		}
	}
	int Do(int x)
	{
		if (d == 0)
		{
			x = max(x, l);
			x = min(x, r);
		}
		else
		{
			x = min(x, r);
			x = max(x, l);
		}
		return x;
	}
};
int get(int i)
{
	return i - MAX + 1;
}
T tree[MAX];
int ans[MAX];
void push(int i, int tl, int tr)
{
	if (tl == tr)
	{
		return;
	}
	else
	{
		if (tl + 1 == tr)
		{
			ans[get(2 * i + 1)] = tree[i].Do(ans[get(2 * i + 1)]);
			ans[get(2 * i + 2)] = tree[i].Do(ans[get(2 * i + 2)]);
			tree[i] = T();
		}
		else
		{
			if (tree[i].d == 0)
			{
				tree[2 * i + 1].left(tree[i].l);
				tree[2 * i + 1].right(tree[i].r);
				tree[2 * i + 2].left(tree[i].l);
				tree[2 * i + 2].right(tree[i].r);
			}
			else
			{
				tree[2 * i + 1].right(tree[i].r);
				tree[2 * i + 1].left(tree[i].l);
				tree[2 * i + 2].right(tree[i].r);
				tree[2 * i + 2].left(tree[i].l);
			}
			tree[i] = T();
		}
	}
}
void add(int i, int tl, int tr, int l, int r, int v, int type)
{
	if (tl > r || tr < l)return;
	push(i, tl, tr);
	if (tl >= l && tr <= r)
	{
		if (tl == tr)
		{
			if (type == 0)
				ans[get(i)] = max(ans[get(i)], v);
			else
				ans[get(i)] = min(ans[get(i)], v);
			return;
		}
		if (type == 0)
		{
			tree[i].left(v);
		}
		else
		{
			tree[i].right(v);
		}
		return;
	}
	int mid = (tl + tr) / 2;
	add(2 * i + 1, tl, mid, l, r, v, type);
	add(2 * i + 2, mid + 1, tr, l, r, v, type);
}
void p(int i, int tl, int tr)
{
	if (tl != tr)
	{
		push(i, tl, tr);
		int mid = (tl + tr) / 2;
		p(2 * i + 1, tl, mid);
		p(2 * i + 2, mid + 1, tr);
	}
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) 
{
	F0R(i, k)
	{
		op[i]--;
		add(0, 0, MAX - 1, left[i], right[i], height[i], op[i]);// I thought it was 1 indexed... 
	}
	p(0, 0, MAX - 1);
	F0R(i, n)
	{
		finalHeight[i] = ans[i];
	}
}


#ifdef arwaeystoamneg
int main()
{
	setIO("");
	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;
}


#endif

Compilation message

wall.cpp:54:18: warning: extra tokens at end of #include directive
   54 | #include "wall.h";
      |                  ^
wall.cpp: In function 'void setIO(std::string)':
wall.cpp:48:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   48 |   freopen((s + ".in").c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
wall.cpp:50:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   50 |    freopen((s + ".out").c_str(), "w", stdout);
      |    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	92 ms	65860 KB	Output is correct
2	Correct	95 ms	65980 KB	Output is correct
3	Correct	92 ms	65988 KB	Output is correct
4	Correct	97 ms	66180 KB	Output is correct
5	Correct	95 ms	66196 KB	Output is correct
6	Correct	95 ms	66156 KB	Output is correct

Subtask #2

24.0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	87 ms	65844 KB	Output is correct
2	Correct	392 ms	73964 KB	Output is correct
3	Correct	391 ms	69520 KB	Output is correct
4	Correct	863 ms	74492 KB	Output is correct
5	Correct	474 ms	75008 KB	Output is correct
6	Correct	486 ms	74980 KB	Output is correct

Subtask #3

29.0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	89 ms	65860 KB	Output is correct
2	Correct	92 ms	66056 KB	Output is correct
3	Correct	92 ms	65948 KB	Output is correct
4	Correct	100 ms	66204 KB	Output is correct
5	Correct	95 ms	66180 KB	Output is correct
6	Correct	104 ms	66200 KB	Output is correct
7	Correct	100 ms	65988 KB	Output is correct
8	Correct	403 ms	73976 KB	Output is correct
9	Correct	363 ms	69428 KB	Output is correct
10	Correct	826 ms	74488 KB	Output is correct
11	Correct	479 ms	75080 KB	Output is correct
12	Correct	482 ms	75076 KB	Output is correct
13	Correct	89 ms	65932 KB	Output is correct
14	Correct	402 ms	73988 KB	Output is correct
15	Correct	147 ms	66756 KB	Output is correct
16	Correct	1112 ms	74820 KB	Output is correct
17	Correct	481 ms	74808 KB	Output is correct
18	Correct	485 ms	74796 KB	Output is correct

Subtask #4

39.0 / 39.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	95 ms	65908 KB	Output is correct
2	Correct	93 ms	65984 KB	Output is correct
3	Correct	92 ms	66004 KB	Output is correct
4	Correct	99 ms	66180 KB	Output is correct
5	Correct	96 ms	66204 KB	Output is correct
6	Correct	97 ms	66172 KB	Output is correct
7	Correct	106 ms	65860 KB	Output is correct
8	Correct	396 ms	73992 KB	Output is correct
9	Correct	378 ms	69444 KB	Output is correct
10	Correct	875 ms	74556 KB	Output is correct
11	Correct	489 ms	75076 KB	Output is correct
12	Correct	468 ms	75076 KB	Output is correct
13	Correct	89 ms	65860 KB	Output is correct
14	Correct	402 ms	73896 KB	Output is correct
15	Correct	149 ms	66724 KB	Output is correct
16	Correct	1102 ms	74680 KB	Output is correct
17	Correct	499 ms	74576 KB	Output is correct
18	Correct	466 ms	74580 KB	Output is correct
19	Correct	982 ms	91812 KB	Output is correct
20	Correct	1030 ms	99820 KB	Output is correct
21	Correct	1111 ms	102272 KB	Output is correct
22	Correct	1004 ms	99852 KB	Output is correct
23	Correct	1004 ms	99896 KB	Output is correct
24	Correct	1053 ms	99928 KB	Output is correct
25	Correct	999 ms	99736 KB	Output is correct
26	Correct	998 ms	102356 KB	Output is correct
27	Correct	993 ms	102260 KB	Output is correct
28	Correct	995 ms	99708 KB	Output is correct
29	Correct	987 ms	99852 KB	Output is correct
30	Correct	999 ms	99808 KB	Output is correct