oj.uz

Submission #53306

# Submission time Handle Problem Language Result Execution time Memory
53306 2018-06-29T08:39:55 Z 김세빈(#1401) Tram (CEOI13_tram) C++11
100 / 100
 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);
      |    ~~~~~^~~~~~~~~~~

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
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 2 ms 496 KB Output is correct

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 2 ms 492 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory 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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory 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

Subtask #7
15.0 / 15.0

# Verdict Execution time Memory 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

Subtask #8
20.0 / 20.0

# Verdict Execution time Memory 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