oj.uz

Submission #53320

# Submission time Handle Problem Language Result Execution time Memory
53320 2018-06-29T09:28:10 Z Petr(#1976) Tram (CEOI13_tram) C++11
45 / 100
 65 ms 8044 KB 
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using pp=pair<int,int>;
#define x first
#define y second

multiset<int> filled_row;
int n;

bool m[150010][2];

pp history[30010];
set<pair<ll, pp>> candidate;

int get_bef(int x){
	auto it = filled_row.lower_bound(x);
	if(it == filled_row.begin()) return 0;
	else return *--it;
}

int get_nxt(int x){
	auto it = filled_row.upper_bound(x);
	if(it == filled_row.end()) return n+1;
	else return *it;
}

ll hypo(ll dx, ll dy){ return dx*dx + abs(dy); }

void add_range(int d, int u){
	if(d+1 >= u) return;
	pair<ll, pp> ans[4]; int an = 0;

	auto eval = [&](int r, int c){
		ll Md = 1ll << 60;
		for(int br = d; br <= u; br += u-d){
			for(int bc = 0; bc < 2; ++bc){
				if(m[br][bc]) Md = min(Md, hypo(r - br, c - bc));
			}
		}
		if(an == 0 || -ans[0].x == Md) ans[an++] = make_pair(-Md, pp(r, c));
		else if(-ans[0].x < Md){
			ans[0] = make_pair(-Md, pp(r, c));
			an = 1;
		}
	};

	if(d == 0){
		if(u == n+1){
			candidate.insert(make_pair(0, pp(1, 0)));
			return;
		} else {
			eval(1, 0); eval(1, 1);
		}
	} else if(u == n+1){
		eval(n, 0); eval(n, 1);
	} else for(int r = (d+u)/2; r <= (d+u+1)/2; ++r){
		eval(r, 0); eval(r, 1);
	}
	for(int i=0; i<an; ++i) candidate.insert(ans[i]);
}

void remove_range(int d, int u){
	if(d+1 >= u) return;
	pair<ll, pp> ans[4]; int an = 0;

	auto eval = [&](int r, int c){
		ll Md = 1ll << 60;
		for(int br = d; br <= u; br += u-d){
			for(int bc = 0; bc < 2; ++bc){
				if(m[br][bc]) Md = min(Md, hypo(r - br, c - bc));
			}
		}
		if(an == 0 || -ans[0].x == Md) ans[an++] = make_pair(-Md, pp(r, c));
		else if(-ans[0].x < Md){
			ans[0] = make_pair(-Md, pp(r, c));
			an = 1;
		}
	};

	if(d == 0){
		if(u == n+1){
			candidate.erase(make_pair(0, pp(1, 0)));
			return;
		} else {
			eval(1, 0); eval(1, 1);
		}
	} else if(u == n+1){
		eval(n, 0); eval(n, 1);
	} else for(int r = (d+u)/2; r <= (d+u+1)/2; ++r){
		eval(r, 0); eval(r, 1);
	}
	for(int i=0; i<an; ++i) candidate.erase(ans[i]);
}

int main()
{
	int q;
	scanf("%d%d", &n, &q);
	add_range(0, n+1);

	for(int i=1; i<=q; ++i){
		char com[10];
		scanf("%s", com);
		if(com[0] == 'E'){
			assert(candidate.size());
			auto tmp = *candidate.begin();
			int px, py; tie(px, py) = candidate.begin() -> second;
			printf("%d %d\n", px, py+1);
			history[i] = {px, py};

			int bef = get_bef(px), nxt = get_nxt(px);
			filled_row.insert(px);
			
			if(m[px][py^1]){
				candidate.erase(tmp);
				remove_range(bef, px); remove_range(px, nxt);
				m[px][py] = 1;
				add_range(bef, px); add_range(px, nxt);
			} else {
				remove_range(bef, nxt);
				m[px][py] = 1;

				add_range(bef, px); add_range(px, nxt);
				candidate.emplace(-1, pp(px, py^1));
			}
		} else {
			int idx, x, y;
			scanf("%d", &idx);
			tie(x, y) = history[idx];

			filled_row.erase(filled_row.find(x));
			int bef = get_bef(x), nxt = get_nxt(x);
			remove_range(bef, x);
			remove_range(x, nxt);
			m[x][y] = 0;
			if(m[x][y^1]){
				add_range(bef, x);
				add_range(x, nxt);
				candidate.emplace(-1, pp(x, y));
			} else {
				add_range(bef, nxt);
				candidate.erase(make_pair(-1, pp(x, y^1)));
			}
		}
	}
	return 0;
}

Compilation message

tram.cpp: In function 'int main()':
tram.cpp:99:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   99 |  scanf("%d%d", &n, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~
tram.cpp:104:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  104 |   scanf("%s", com);
      |   ~~~~~^~~~~~~~~~~
tram.cpp:129:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  129 |    scanf("%d", &idx);
      |    ~~~~~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 492 KB Output is correct
2 Incorrect 2 ms 364 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1004 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 3 ms 748 KB Output is correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1004 KB Output is correct
2 Incorrect 3 ms 364 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 2540 KB Output is correct
2 Incorrect 30 ms 876 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 8044 KB Output is correct
2 Incorrect 34 ms 876 KB Output isn't correct
3 Halted 0 ms 0 KB -