| # |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
| 53306 |
2018-06-29T08:39:55 Z |
김세빈(#1401) |
전차 (CEOI13_tram) |
C++11 |
|
38 ms |
9964 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll inf = 1e18;
ll dist(ll x1, ll y1, ll x2, ll y2) { return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2); }
set <pll> S;
ll C[151515], L[151515], R[151515], T[151515];
pll K[151515], P[151515];
ll n,m;
void update_cost(ll l)
{
ll r = R[l];
if(l == 0 && r == n+1){
C[l] = inf;
K[l] = pll(1, 1);
}
else if(l == 0){
if(T[r] == 1){
C[l] = dist(1, 2, r, 1);
K[l] = pll(1, 2);
}
else if(T[r] == 2){
C[l] = dist(1, 1, r, 2);
K[l] = pll(1, 1);
}
else if(T[r] == 3){
C[l] = dist(1, 1, r, 1);
K[l] = pll(1, 1);
}
}
else if(r == n+1){
if(T[l] == 1){
C[l] = dist(l, 1, n, 2);
K[l] = pll(n, 2);
}
else if(T[l] == 2){
C[l] = dist(l, 2, n, 1);
K[l] = pll(n, 1);
}
else if(T[l] == 3){
C[l] = dist(l, 1, n, 1);
K[l] = pll(n, 1);
}
}
else{
if(T[l] == 1 && T[r] == 1){
C[l] = dist(l, 1, l+r>>1, 2);
K[l] = pll(l+r>>1, 2);
}
else if(T[l] == 1 && (T[r] == 2 || T[r] == 3)){
if(r-l == 2){
C[l] = dist(l, 1, l, 2);
K[l] = pll(l, 2);
}
else if(r-l & 1){
C[l] = dist(l, 1, l+r>>1, 2);
K[l] = pll(l+r>>1, 2);
}
else{
C[l] = dist(l, 1, l+r>>1, 1);
K[l] = pll(l+r>>1, 1);
}
}
else if(T[l] == 2 && (T[r] == 1 || T[r] == 3)){
if(r-l == 2){
C[l] = dist(l, 2, l, 1);
K[l] = pll(l, 1);
}
else if(r-l & 1){
C[l] = dist(l, 2, l+r>>1, 1);
K[l] = pll(l+r>>1, 1);
}
else{
C[l] = dist(r, 1, l+r>>1, 1);
K[l] = pll(l+r>>1, 1);
}
}
else if(T[l] == 2 && T[r] == 2){
C[l] = dist(l, 2, l+r>>1, 1);
K[l] = pll(l+r>>1, 1);
}
else if(T[l] == 3 && T[r] == 1){
if(r-l & 1){
C[l] = dist(r, 1, l+r+1>>1, 2);
K[l] = pll(l+r+1>>1, 2);
}
else{
C[l] = dist(l, 1, l+r>>1, 1);
K[l] = pll(l+r>>1, 1);
}
}
else if(T[l] == 3 && T[r] == 2){
if(r-l & 1){
C[l] = dist(r, 2, l+r+1>>1, 1);
K[l] = pll(l+r+1>>1, 1);
}
else{
C[l] = dist(l, 1, l+r>>1, 1);
K[l] = pll(l+r>>1, 1);
}
}
else if(T[l] == 3 && T[r] == 3){
C[l] = dist(l, 1, l+r>>1, 1);
K[l] = pll(l+r>>1, 1);
}
}
}
int main()
{
scanf("%lld%lld",&n,&m);
char str[5];
ll i,k,l,r,a;
pll p;
L[0] = -1; R[0] = n+1;
L[n+1] = 0; R[n+1] = -1;
update_cost(0);
S.insert(pll(-C[0], 0));
for(i=1;i<=m;i++){
scanf("%s",str);
if(*str == 'E'){
k = S.begin()->second;
p = K[k];
P[i] = p;
if(T[p.first] != 0){
l = L[p.first]; r = p.first;
S.erase(pll(-C[l], l)); S.erase(pll(-C[r], r));
T[r] |= 1 << p.second-1;
update_cost(l); update_cost(r);
S.insert(pll(-C[l], l)); S.insert(pll(-C[r], r));
}
else{
l = k; r = p.first;
S.erase(pll(-C[l], l));
R[r] = R[l];
L[R[l]] = r;
R[l] = r;
L[r] = l;
T[r] |= 1 << p.second-1;
update_cost(l); update_cost(r);
S.insert(pll(-C[l], l)); S.insert(pll(-C[r], r));
}
printf("%lld %lld\n",p.first,p.second);
}
else if(*str == 'L'){
scanf("%lld",&a);
p = P[a];
T[p.first] -= 1 << p.second-1;
if(T[p.first] != 0){
l = L[p.first]; r = p.first;
S.erase(pll(-C[l], l)); S.erase(pll(-C[r], r));
update_cost(l); update_cost(r);
S.insert(pll(-C[l], l)); S.insert(pll(-C[r], r));
}
else{
l = L[p.first]; r = p.first;
S.erase(pll(-C[l], l)); S.erase(pll(-C[r], r));
R[l] = R[r];
L[R[r]] = l;
update_cost(l);
S.insert(pll(-C[l], l));
}
}
}
return 0;
}
Compilation message
tram.cpp: In function 'void update_cost(ll)':
tram.cpp:55:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
55 | C[l] = dist(l, 1, l+r>>1, 2);
| ~^~
tram.cpp:56:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
56 | K[l] = pll(l+r>>1, 2);
| ~^~
tram.cpp:63:13: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
63 | else if(r-l & 1){
| ~^~
tram.cpp:64:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
64 | C[l] = dist(l, 1, l+r>>1, 2);
| ~^~
tram.cpp:65:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
65 | K[l] = pll(l+r>>1, 2);
| ~^~
tram.cpp:68:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
68 | C[l] = dist(l, 1, l+r>>1, 1);
| ~^~
tram.cpp:69:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
69 | K[l] = pll(l+r>>1, 1);
| ~^~
tram.cpp:77:13: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
77 | else if(r-l & 1){
| ~^~
tram.cpp:78:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
78 | C[l] = dist(l, 2, l+r>>1, 1);
| ~^~
tram.cpp:79:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
79 | K[l] = pll(l+r>>1, 1);
| ~^~
tram.cpp:82:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
82 | C[l] = dist(r, 1, l+r>>1, 1);
| ~^~
tram.cpp:83:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
83 | K[l] = pll(l+r>>1, 1);
| ~^~
tram.cpp:87:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
87 | C[l] = dist(l, 2, l+r>>1, 1);
| ~^~
tram.cpp:88:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
88 | K[l] = pll(l+r>>1, 1);
| ~^~
tram.cpp:91:8: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
91 | if(r-l & 1){
| ~^~
tram.cpp:92:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
92 | C[l] = dist(r, 1, l+r+1>>1, 2);
| ~~~^~
tram.cpp:93:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
93 | K[l] = pll(l+r+1>>1, 2);
| ~~~^~
tram.cpp:96:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
96 | C[l] = dist(l, 1, l+r>>1, 1);
| ~^~
tram.cpp:97:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
97 | K[l] = pll(l+r>>1, 1);
| ~^~
tram.cpp:101:8: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
101 | if(r-l & 1){
| ~^~
tram.cpp:102:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
102 | C[l] = dist(r, 2, l+r+1>>1, 1);
| ~~~^~
tram.cpp:103:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
103 | K[l] = pll(l+r+1>>1, 1);
| ~~~^~
tram.cpp:106:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
106 | C[l] = dist(l, 1, l+r>>1, 1);
| ~^~
tram.cpp:107:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
107 | K[l] = pll(l+r>>1, 1);
| ~^~
tram.cpp:111:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
111 | C[l] = dist(l, 1, l+r>>1, 1);
| ~^~
tram.cpp:112:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
112 | K[l] = pll(l+r>>1, 1);
| ~^~
tram.cpp: In function 'int main()':
tram.cpp:142:26: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
142 | T[r] |= 1 << p.second-1;
| ~~~~~~~~^~
tram.cpp:155:26: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
155 | T[r] |= 1 << p.second-1;
| ~~~~~~~~^~
tram.cpp:166:31: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
166 | T[p.first] -= 1 << p.second-1;
| ~~~~~~~~^~
tram.cpp:119:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
119 | scanf("%lld%lld",&n,&m);
| ~~~~~^~~~~~~~~~~~~~~~~~
tram.cpp:132:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
132 | scanf("%s",str);
| ~~~~~^~~~~~~~~~
tram.cpp:163:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
163 | scanf("%lld",&a);
| ~~~~~^~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
492 KB |
Output is correct |
| 2 |
Correct |
2 ms |
364 KB |
Output is correct |
| 3 |
Correct |
2 ms |
496 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
492 KB |
Output is correct |
| 2 |
Correct |
2 ms |
364 KB |
Output is correct |
| 3 |
Correct |
2 ms |
492 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
8 ms |
7532 KB |
Output is correct |
| 2 |
Correct |
2 ms |
364 KB |
Output is correct |
| 3 |
Correct |
6 ms |
7148 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
8 ms |
7532 KB |
Output is correct |
| 2 |
Correct |
2 ms |
364 KB |
Output is correct |
| 3 |
Correct |
5 ms |
6892 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
22 ms |
2668 KB |
Output is correct |
| 2 |
Correct |
22 ms |
1132 KB |
Output is correct |
| 3 |
Correct |
21 ms |
2284 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
38 ms |
9964 KB |
Output is correct |
| 2 |
Correct |
22 ms |
1132 KB |
Output is correct |
| 3 |
Correct |
33 ms |
8684 KB |
Output is correct |
