oj.uz

답안 #881862

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
881862 2023-12-02T05:24:01 Z marvinthang 청소 (JOI20_sweeping) C++17
64 / 100
 5770 ms 528132 KB 
/*************************************
*    author: marvinthang             *
*    created: 02.12.2023 08:47:56    *
*************************************/

#include <bits/stdc++.h>
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;


#define                  fi  first
#define                  se  second
#define                left  ___left
#define               right  ___right
#define                TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define             MASK(i)  (1LL << (i))
#define           BIT(x, i)  ((x) >> (i) & 1)
#define  __builtin_popcount  __builtin_popcountll
#define              ALL(v)  (v).begin(), (v).end()
#define           REP(i, n)  for (int i = 0, _n = (n); i < _n; ++i)
#define          REPD(i, n)  for (int i = (n); i-- > 0; )
#define        FOR(i, a, b)  for (int i = (a), _b = (b); i < _b; ++i) 
#define       FORD(i, b, a)  for (int i = (b), _a = (a); --i >= _a; ) 
#define       FORE(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i) 
#define      FORDE(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i) 
#define        scan_op(...)  istream & operator >> (istream &in, __VA_ARGS__ &u)
#define       print_op(...)  ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#ifdef LOCAL
    #include "debug.h"
#else
    #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
    #define DB(...) 23
    #define db(...) 23
    #define debug(...) 23
#endif

template <class U, class V> scan_op(pair <U, V>)  { return in >> u.first >> u.second; }
template <class T> scan_op(vector <T>)  { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class U, class V> print_op(pair <U, V>)  { return out << '(' << u.first << ", " << u.second << ')'; }
template <size_t i, class T> ostream & print_tuple_utils(ostream &out, const T &tup) { if constexpr(i == tuple_size<T>::value) return out << ")";  else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); }
template <class ...U> print_op(tuple<U...>) { return print_tuple_utils<0, tuple<U...>>(out, u); }
template <class Con, class = decltype(begin(declval<Con>()))> typename enable_if <!is_same<Con, string>::value, ostream&>::type operator << (ostream &out, const Con &con) { out << '{'; for (__typeof(con.begin()) it = con.begin(); it != con.end(); ++it) out << (it == con.begin() ? "" : ", ") << *it; return out << '}'; }

// end of template

void process(void) {
	int n, m, q; cin >> n >> m >> q;
	vector <pair <int, int>> dusts(m); cin >> dusts;
	vector <ordered_set <pair <int, int>>> x_order(q + 1), y_order(q + 1);
	vector <pair <int, int>> pos(1);
	REP(i, dusts.size()) {
		x_order[0].insert(pair{dusts[i].fi, i});
		y_order[0].insert(pair{dusts[i].se, i});
	}
	vector <int> in_set(m);
	map <int, int> px;
	px[0] = 0;
	auto add = [&] (int i, int p) {
		x_order[in_set[i]].erase(pair{dusts[i].fi, i});
		y_order[in_set[i]].erase(pair{dusts[i].se, i});
		in_set[i] = p;
		x_order[p].insert(pair{dusts[i].fi, i});
		y_order[p].insert(pair{dusts[i].se, i});
	};
	while (q--) {
		int t, a; cin >> t >> a;
		if (t == 1) {
			--a;
			cout << max(dusts[a].fi, pos[in_set[a]].fi) << ' ' << max(dusts[a].se, pos[in_set[a]].se) << '\n';
		} else if (t == 2) {
			auto it = prev(px.upper_bound(n - a));
			if (it->fi == n - a) continue;
			int p = it->se;
			int q = pos.size();
			pos.emplace_back(n - a, pos[p].se);
			pos[p].se = a + 1;
			px[n - a] = q;
			if (y_order[p].order_of_key(pair{a + 1, 0}) * 2 <= y_order[p].size()) {
				while (!y_order[p].empty() && y_order[p].begin()->fi <= a) {
					add(y_order[p].begin()->se, q);
				}
			} else {
				while (!y_order[p].empty() && y_order[p].rbegin()->fi > a) {
					add(y_order[p].rbegin()->se, q);
				}
				swap(pos[p], pos[q]);
				swap(px[pos[p].fi], px[pos[q].fi]);
			}
		} else if (t == 3) {
			auto it = prev(px.upper_bound(a + 1));
			if (it->fi == a + 1) continue;
			int p = it->se;
			int q = pos.size();
			pos.emplace_back(a + 1, pos[p].se);
			pos[p].se = n - a;
			px[a + 1] = q;
			if (x_order[p].order_of_key(pair{a + 1, 0}) * 2 <= x_order[p].size()) {
				while (!x_order[p].empty() && x_order[p].begin()->fi <= a) {
					add(x_order[p].begin()->se, q);
				}
				swap(pos[p], pos[q]);
				swap(px[pos[p].fi], px[pos[q].fi]);
			} else {
				while (!x_order[p].empty() && x_order[p].rbegin()->fi > a) {
					add(x_order[p].rbegin()->se, q);
				}
			}
		}
	}
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(nullptr); // cout.tie(nullptr);
	file("JOI20_sweeping");
	// int t; cin >> t; while (t--)
	process();
	// cerr << "Time elapsed: " << TIME << " s.\n";
	return (0^0);
}

Compilation message

sweeping.cpp: In function 'int main()':
sweeping.cpp:36:61: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |     #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sweeping.cpp:119:2: note: in expansion of macro 'file'
  119 |  file("JOI20_sweeping");
      |  ^~~~
sweeping.cpp:36:94: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |     #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                                                       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
sweeping.cpp:119:2: note: in expansion of macro 'file'
  119 |  file("JOI20_sweeping");
      |  ^~~~

Subtask #1
0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 5 ms 3164 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 5770 ms 528132 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5413 ms 313708 KB Output is correct
2 Correct 3316 ms 313920 KB Output is correct
3 Correct 1903 ms 312696 KB Output is correct
4 Correct 1749 ms 313880 KB Output is correct
5 Correct 3160 ms 313940 KB Output is correct
6 Correct 3099 ms 313808 KB Output is correct

Subtask #4
53.0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5413 ms 313708 KB Output is correct
2 Correct 3316 ms 313920 KB Output is correct
3 Correct 1903 ms 312696 KB Output is correct
4 Correct 1749 ms 313880 KB Output is correct
5 Correct 3160 ms 313940 KB Output is correct
6 Correct 3099 ms 313808 KB Output is correct
7 Correct 4621 ms 313964 KB Output is correct
8 Correct 4828 ms 313152 KB Output is correct
9 Correct 4425 ms 313628 KB Output is correct
10 Correct 2571 ms 312640 KB Output is correct
11 Correct 2213 ms 313472 KB Output is correct
12 Correct 3900 ms 314200 KB Output is correct
13 Correct 3263 ms 314064 KB Output is correct
14 Correct 187 ms 192228 KB Output is correct
15 Correct 1350 ms 282452 KB Output is correct
16 Correct 4529 ms 313856 KB Output is correct
17 Correct 4149 ms 313844 KB Output is correct

Subtask #5
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 5 ms 3164 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -