oj.uz

Submission #4554

# Submission time Handle Problem Language Result Execution time Memory
4554 2013-10-27T17:37:32 Z ainta Tram (CEOI13_tram) C++
100 / 100
 102 ms 3820 KB 
#include<stdio.h>
#include<algorithm>
#include<set>
#define Set_itr set<int>::iterator
#define SetA_itr set<A>::iterator
using namespace std;
set<int>Set;
Set_itr be, ed;
int n, m, dat[31000];
struct A{
	int d, r, a, b;
	bool operator <(const A &p)const{
		return d != p.d ? d < p.d : r > p.r;
	}
}tp;
set<A>Set2;
int dist(int a, int b){
	int x = a / 2, y = b / 2, r;
	if (x < y)r = y - x;
	else r = x - y;
	r *= 2;
	if (a % 2 != b % 2) r++;
	if (r == 1)r = 2;
	return r;
}
void Print(int a){
	printf("%d %d\n", a / 2 + 1, a % 2 + 1);
}
A Sol(Set_itr it){
	A res;
	Set_itr it2 = it,it3=it,it4;
	int y, my, i, t, R = -1, dis, rr;
	it2++; it4 = it2;
	if (it3 != be)it3--;
	if (it4 != ed)it4++;
	res.a = *it, res.b = *it2;
	y = (res.a / 2 + res.b / 2)/2;
	my = y;
	if ((res.a / 2 + res.b / 2) & 1)my++;
	if (res.b / 2 - res.a / 2 == 2){
		y--, my++;
	}
	while (y <= my){
		for (i = 0; i < 2; i++){
			t = y * 2 + i;
			if (t<res.a || t>res.b)continue;
			dis = min(min(dist(t, *it), dist(t, *it2)), min(dist(t, *it3), dist(t, *it4)));
			if (R < dis)R = dis, rr = t;
		}
		y++;
	}
	res.d = R, res.r = rr;
	return res;
}
void Ins(Set_itr it){
	if (it != ed){
		tp = Sol(it);
		Set2.insert(tp);
		it++;
		if (it != ed){
			tp = Sol(it);
			Set2.insert(tp);
		}
		it--;
	}
	if (it != be){
		it--;
		Set2.insert(Sol(it));
		if (it != be){
			it--;
			tp = Sol(it);
			Set2.insert(tp);
			it++;
		}
	}
}
void Pro(Set_itr it){
	if (it != Set.begin() && it != Set.end()){
		it--;
		Set2.erase(Set2.find(Sol(it)));
	}
}
void Put(int cnt, int t){
	dat[cnt] = t;
	Print(t);
	Set_itr it=Set.lower_bound(t),it2;
	Pro(it);
	if (it != Set.begin()){
		it2 = it; it2--;
		Pro(it2);
	}
	if (it != Set.end()){
		it2 = it; it2++;
		Pro(it2);
	}
	Set.insert(t);
	be = Set.begin();
	ed = Set.end();
	ed--;
	Ins(Set.find(t));
}
void insert(int cnt){
	int sz = Set.size(), t, d, r;
	Set_itr it = be, it2;
	t = 1 - (*it % 2);
	if (sz > 1){
		it2 = it; it2++;
		if (*it2 / 2 == *it / 2)t = 0;
	}
	d = dist(t, *it), r = t;
	it = ed;
	t = n * 2 - 1 - (*it % 2);
	if (sz > 1){
		it2 = it; it2--;
		if (*it2 / 2 == *it / 2)t = n * 2 - 2, it = it2;
	}
	if (d < dist(t, *it))d = dist(t, *it), r = t;
	if (Set2.empty()){
		Put(cnt, r);
		return;
	}
	SetA_itr iit;
	if (!Set2.empty()){
		iit = Set2.end(); iit--;
		if (iit->d > d || (d == iit->d &&iit->r < r))d = iit->d, r = iit->r;
	}
	Put(cnt, r);
	return;
}
void del(Set_itr it){
	Set_itr it2 = it, it3;
	bool ck=false;
	if (it != be)it--;
	if (it != be)it--;
	int c = 0;
	while (c < 4 && it != ed){
		Set2.erase(Set2.find(Sol(it)));
		c++, it++;
	}
	it3 = it;
	it = it2;
	if (it3 == it)ck = true;
	int t = *it;
	Set.erase(it);
	if (Set.empty())return;
	be = Set.begin(),ed = Set.end();
	ed--;
	if (ck)it3 = ed;
	it2 = Set.lower_bound(t);
	if (it2 != be)it2--;
	if (it2 != be)it2--;
	c = 0;
	while (c < 3 && it2 != it3){
		Set2.insert(Sol(it2));
		c++, it2++;
	}
}
int main(){
	scanf("%d%d", &n, &m);
	char pp[2];
	int cnt = 0, a;
	while (m--){
		scanf("%s", pp);
		cnt++;
		if (!Set.empty()){
			be = Set.begin();
			ed = Set.end();
			ed--;
		}
		else{
			Put(cnt, 0);
			continue;
		}
		if (pp[0] == 'E'){	
			insert(cnt);
		}
		else{
			scanf("%d", &a);
			del(Set.find(dat[a]));
		}
	}
}

Compilation message

tram.cpp: In function 'int main()':
tram.cpp:159:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  159 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
tram.cpp:163:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  163 |   scanf("%s", pp);
      |   ~~~~~^~~~~~~~~~
tram.cpp:178:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  178 |    scanf("%d", &a);
      |    ~~~~~^~~~~~~~~~
tram.cpp: In function 'A Sol(std::set<int>::iterator)':
tram.cpp:53:9: warning: 'rr' may be used uninitialized in this function [-Wmaybe-uninitialized]
   53 |  return res;
      |         ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 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
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 3812 KB Output is correct
2 Correct 102 ms 748 KB Output is correct
3 Correct 65 ms 1516 KB Output is correct

Subtask #8
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 3820 KB Output is correct
2 Correct 68 ms 748 KB Output is correct
3 Correct 73 ms 1448 KB Output is correct