oj.uz

답안 #392399

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
392399 2021-04-21T04:09:52 Z arwaeystoamneg 벽 (IOI14_wall) C++17
100 / 100
 1112 ms 102356 KB 
// 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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