Submission #392397

#	Time	Username	Problem	Language	Result	Execution time	Memory
392397		arwaeystoamneg	Wall (IOI14_wall)	C++17	61 / 100	1040 ms	34972 KiB

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 = 17;
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 (stderr)

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 / 8
• Subtask 2: 24 / 24
• Subtask 3: 29 / 29
• Subtask 4: 0 / 39