oj.uz

Submission #778959

# Submission time Handle Problem Language Result Execution time Memory
778959 2023-07-11T05:32:41 Z 박상훈(#10000) Tram (CEOI13_tram) C++17
100 / 100
 37 ms 4908 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
constexpr int INF = 1e9 + 100;

int n;
pair<int, int> _log[300300];

int dist(const pair<int, int> &p, const pair<int, int> &q){
	if (p.second==q.second) return abs(p.first-q.first) * 2;
	if (p.first==q.first) return 2;
	return abs(p.first-q.first) * 2 + 1;
}

int dist(pair<int, int> p, const vector<pair<int, int>> &V){
	if (V.empty()) return -INF;
	int mn = INF;
	for (const auto &q:V) mn = min(mn, dist(p, q));
	// printf(" fuck fuck %d %d -> %d\n", p.first, p.second, mn);

	return mn;
}

struct Block{
	int l, r, bl, br;
	int x, y, v;

	Block(){}
	Block(int _l, int _r, int _bl, int _br){
		l = _l, r = _r, bl = _bl, br = _br;

		assert(l<r);
		vector<pair<int, int>> C, P;

		if (bl&1) P.emplace_back(l, 1);
		else if (l>0) C.emplace_back(l, 1);

		if (bl&2) P.emplace_back(l, 2);
		else if (l>0) C.emplace_back(l, 2);

		if (br&1) P.emplace_back(r, 1);
		else if (r<=n) C.emplace_back(r, 1);

		if (br&2) P.emplace_back(r, 2);
		else if (r<=n) C.emplace_back(r, 2);

		if (l+1 < r){
			int len = (r-l-2) / 2;
			C.emplace_back(l+1+len, 1);
			C.emplace_back(l+1+len, 2);
			C.emplace_back(r-1-len, 1);
			C.emplace_back(r-1-len, 2);

			C.emplace_back(l+1, 1);
			C.emplace_back(l+1, 2);
			C.emplace_back(r-1, 1);
			C.emplace_back(r-1, 2);
		}

		// for (auto &[x, y]:P) printf(" fuck %d %d\n", x, y);

		v = -INF, x = INF, y = INF;
		for (auto &p:C){
			int d = dist(p, P);
			
			if (v==d){
				if (pair<int, int>(x, y) > p){
					x = p.first, y = p.second;
				}
			}

			else if (v < d){
				v = d;
				x = p.first, y = p.second;
			}
		}
	}

	bool operator < (const Block &B) const{
		if (v==B.v) return array<int, 3>{x, y, l} < array<int, 3>{B.x, B.y, B.l};
		return v > B.v;
	}

	void print() const{
		printf("ran = [%d, %d] / typ = (%d, %d) / P = (%d, %d) / v = %d\n", l, r, bl, br, x, y, v);
	}
};

multiset<Block> st;
set<int> st2;
int on[300300];

int getprv(int x){
	auto iter = st2.find(x);
	assert(iter!=st2.end());
	return *prev(iter);
}

int getnxt(int x){
	auto iter = st2.find(x);
	assert(iter!=st2.end());
	return *next(iter);
}

void insert(int idx, int x, int y){
	_log[idx] = {x, y};
	st.erase(st.begin());
	if (!st.empty() && st.begin()->x == x && st.begin()->y == y) st.erase(st.begin());

	on[x] |= 1<<(y-1);
	st2.insert(x);

	int px = getprv(x), nx = getnxt(x);
	// printf("px = %d / nx = %d\n", px, nx);
	st.emplace(px, x, on[px], on[x]);
	st.emplace(x, nx, on[x], on[nx]);
}

void erase(int idx){
	auto [x, y] = _log[idx];
	int px = getprv(x), nx = getnxt(x);
	
	// Block(px, x, on[px], on[x]).print();
	st.erase(st.find(Block(px, x, on[px], on[x])));

	// Block(px, x, on[px], on[x]).print();
	st.erase(st.find(Block(x, nx, on[x], on[nx])));

	on[x] ^= 1<<(y-1);
	if (!on[x]){
		st2.erase(st2.find(x));
		st.emplace(px, nx, on[px], on[nx]);
	}
	else{
		st.emplace(px, x, on[px], on[x]);
		st.emplace(x, nx, on[x], on[nx]);
	}
}

int main(){
	int q;
	scanf("%d %d", &n, &q);

	st2.insert(0);
	st2.insert(n+1);
	st.emplace(0, n+1, 0, 0);

	for (int i=1;i<=q;i++){
		char op;
		int x;
		scanf(" %c", &op);

		if (op=='E'){
			x = i;
			auto iter = st.begin();

			// printf("ok: ");
			printf("%d %d\n", iter->x, iter->y);
			insert(x, iter->x, iter->y);
		}

		else{
			scanf("%d", &x);
			erase(x);
		}

		// printf("debug:\n");
		// for (auto &B:st) B.print();
		// printf("\n");
	}
}

Compilation message

tram.cpp: In function 'int main()':
tram.cpp:143:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  143 |  scanf("%d %d", &n, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~
tram.cpp:152:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  152 |   scanf(" %c", &op);
      |   ~~~~~^~~~~~~~~~~~
tram.cpp:164:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  164 |    scanf("%d", &x);
      |    ~~~~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 212 KB Output is correct
3 Correct 2 ms 340 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 468 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1104 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 852 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 980 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 852 KB Output is correct

Subtask #7
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 2568 KB Output is correct
2 Correct 31 ms 716 KB Output is correct
3 Correct 34 ms 1740 KB Output is correct

Subtask #8
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 4908 KB Output is correct
2 Correct 30 ms 748 KB Output is correct
3 Correct 36 ms 2252 KB Output is correct