oj.uz

답안 #39689

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
39689 2018-01-17T10:14:00 Z aome 전차 (CEOI13_tram) C++14
60 / 100
 137 ms 4716 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
 
const int N = 150005;
 
typedef pair<int, int> ii;
typedef pair<int, ii> II;
typedef set<int> :: iterator it;
 
int n, m;
int mask[N];
ii res[N];
set<int> s;
multiset<II> s2; 
 
II cal(int x, int y) {
	int mx = mask[x], my = mask[y];
	if (!x && !y) return II(0, ii(0, 0));
	if (!x) {
		if (my == 3) return II(-(y - 1) * (y - 1), ii(1, 1));
		else return II(-(y - 1) * (y - 1) - 1, ii(1, 3 ^ my)); 
	}
	if (!y) {
		if (mx == 3) return II(-(n - x) * (n - x), ii(n, 1));
		else return II(-(n - x) * (n - x) - 1, ii(n, 3 ^ mx));
	}
	int mid = (x + y) / 2;
	if (mx == 3 && my == 3) {
		return II(-(mid - x) * (mid - x), ii(mid, 1));
	}
	else if (mx == 3) {
		mid = (x + y + 1) / 2;
		if (x % 2 != y % 2) return II(-(y - mid) * (y - mid) - 1, ii(mid, 3 ^ my));
		else return II(-(mid - x) * (mid - x), ii(mid, 1));
	}
	else if (my == 3) {
		if (x % 2 != y % 2) return II(-(mid - x) * (mid - x) - 1, ii(mid, 3 ^ mx));
		else return II(-(y - mid) * (y - mid), ii(mid, 1));
	}
	else {
		if (mx == my) {
			return II(-(mid - x) * (mid - x) - 1, ii(mid, 3 ^ mx));
		}
		else {
			if (x % 2 == y % 2) {
				if (x + 2 == y) return II(-1, ii(mid - 1, 3 ^ mx));
				return II(-(mid - x) * (mid - x), ii(mid, 1));
			}
			else {
				return II(-(mid - x) * (mid - x) - 1, ii(mid, 3 ^ mx));
			}
		}
	}
}
 
int nxt(it i) {
	if (i == --s.end()) return 0; return *(++i);
}
 
int prv(it i) {
	if (i == s.begin()) return 0; return *(--i);
}
 
void add(int x) {
	it i = s.lower_bound(x);
	int l, r;
	l = prv(i);
	if (i == s.end()) r = 0; else r = *i;
 
	II tmp = cal(l, r);	
	if (tmp.fi) s2.erase(s2.find(tmp));
	tmp = cal(l, x), s2.insert(tmp);
	tmp = cal(x, r), s2.insert(tmp);
	s.insert(x);
}
 
void rem(int x) {
	it i = s.lower_bound(x);
	int l, r;
	l = prv(i), r = nxt(i);
	II tmp;
	tmp = cal(l, x), s2.erase(s2.find(tmp));
	tmp = cal(x, r), s2.erase(s2.find(tmp));
	tmp = cal(l, r);
	if (tmp.fi) s2.insert(tmp);
	s.erase(x);
}
 
int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m;
	for (int i = 1; i <= m; ++i) {
		char type; cin >> type;
		if (type == 'E') {
			if (!s2.size()) {
				res[i] = ii(1, 1), mask[1] |= 1, add(1);
			}
			else {
				II tmp = *s2.begin();
				res[i] = tmp.se; 
				if (mask[res[i].fi]) {
					rem(res[i].fi), mask[res[i].fi] |= 1 << (res[i].se - 1), add(res[i].fi);
				}
				else {
					mask[res[i].fi] |= 1 << (res[i].se - 1), add(res[i].fi);
				}
			}
			cout << res[i].fi << ' ' << res[i].se << '\n';
		}
		else {
			int pos; cin >> pos;
			rem(res[pos].fi), mask[res[pos].fi] ^= (1 << (res[pos].se - 1));
			if (mask[res[pos].fi]) add(res[pos].fi);
		}
	}
}

Compilation message

tram.cpp: In function 'int nxt(it)':
tram.cpp:59:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   59 |  if (i == --s.end()) return 0; return *(++i);
      |  ^~
tram.cpp:59:32: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   59 |  if (i == --s.end()) return 0; return *(++i);
      |                                ^~~~~~
tram.cpp: In function 'int prv(it)':
tram.cpp:63:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   63 |  if (i == s.begin()) return 0; return *(--i);
      |  ^~
tram.cpp:63:32: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   63 |  if (i == s.begin()) return 0; return *(--i);
      |                                ^~~~~~

Subtask #1
10.0 / 10.0

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

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

# 결과 실행 시간 메모리 Grader output
1 Correct 5 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 #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 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
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 1132 KB Output is correct
2 Correct 5 ms 364 KB Output is correct
3 Incorrect 4 ms 1004 KB Output isn't correct

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 1132 KB Output is correct
2 Correct 4 ms 364 KB Output is correct
3 Incorrect 5 ms 1004 KB Output isn't correct

Subtask #7
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 137 ms 2540 KB Output is correct
2 Correct 99 ms 748 KB Output is correct
3 Correct 105 ms 1816 KB Output is correct

Subtask #8
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 112 ms 4716 KB Output is correct
2 Correct 67 ms 876 KB Output is correct
3 Runtime error 8 ms 1644 KB Execution killed with signal 6 (could be triggered by violating memory limits)