oj.uz

Submission #65521

# Submission time Handle Problem Language Result Execution time Memory
65521 2018-08-07T20:07:40 Z IvanC Tram (CEOI13_tram) C++17
100 / 100
 84 ms 30828 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef tuple<ll,int,int> trinca;

const int MAXN = 150010;
const ll INF = 1e18;

trinca get_best(trinca t1,trinca t2){
	if(get<0>(t1) > get<0>(t2)){
		return t1;
	}
	else if(get<0>(t1) < get<0>(t2)){
		return t2;
	}
	if(get<1>(t1) < get<1>(t2)){
		return t1;
	}
	else if(get<1>(t1) > get<1>(t2)){
		return t2;
	}
	if(get<2>(t1) < get<2>(t2)){
		return t1;
	}
	else{
		return t2;
	}
}

ll sq(ll x){
	return x*x;
}

ll euclid(ll x,ll y){
	return sq(x) + sq(y);
}

trinca calcula(int px,int py,int suf_x,const int suf[],int pref_x,const int pref[]){
	ll min_dist = INF;
	if(suf[0] == 1) min_dist = min(min_dist, euclid(px - suf_x,py - 1) );
	if(suf[1] == 1) min_dist = min(min_dist, euclid(px - suf_x,py - 2) );
	if(pref[0] == 1) min_dist = min(min_dist, euclid(px - pref_x,py - 1) );
	if(pref[1] == 1) min_dist = min(min_dist, euclid(px - pref_x,py - 2) );
	return make_tuple(min_dist,px,py);
}

struct node{

	int pref_pos,pref[2],suf_pos,suf[2],empty;
	trinca ans;

	node(int _pos = 0,int v1 = 0,int v2 = 0){

		pref_pos = suf_pos = _pos;
		pref[0] = suf[0] = v1; 
		pref[1] = suf[1] = v2;

		if(v1 == 0 && v2 == 0){
			empty = 1;
			ans = make_tuple(-1,MAXN,MAXN);
		}
		else if(v1 == 1 && v2 == 0){
			empty = 0;
			ans = make_tuple(1,_pos,2);
		}
		else if(v1 == 0 && v2 == 1){
			empty = 0;
			ans = make_tuple(1,_pos,1);
		}
		else{
			empty = 0;
			ans = make_tuple(0,_pos,1);
		}

	}

	node operator*(const node& other)const{

		node novo;
		if(empty && other.empty){
			return novo;
		}
		if(other.empty){
			novo.pref_pos = pref_pos;
			novo.pref[0] = pref[0];
			novo.pref[1] = pref[1];
			novo.suf_pos = suf_pos;
			novo.suf[0] = suf[0];
			novo.suf[1] = suf[1];
			novo.empty = 0;
			novo.ans = ans;
			return novo;
		}
		else if(empty){
			return other;
		}

		novo.pref_pos = pref_pos;
		novo.pref[0] = pref[0];
		novo.pref[1] = pref[1];
		novo.suf_pos = other.suf_pos;
		novo.suf[0] = other.suf[0];
		novo.suf[1] = other.suf[1];
		novo.empty = 0;

		novo.ans = get_best(ans,other.ans);
		if((suf_pos + other.pref_pos) % 2 == 1){
			int m1 = (suf_pos + other.pref_pos)/2;
			int m2 = m1 + 1;
			novo.ans = get_best(novo.ans, calcula(m1,1,suf_pos,suf,other.pref_pos,other.pref) );
			novo.ans = get_best(novo.ans, calcula(m1,2,suf_pos,suf,other.pref_pos,other.pref) );
			novo.ans = get_best(novo.ans, calcula(m2,1,suf_pos,suf,other.pref_pos,other.pref) );
			novo.ans = get_best(novo.ans, calcula(m2,2,suf_pos,suf,other.pref_pos,other.pref) );
		}
		else{
			int m = (suf_pos + other.pref_pos)/2;
			novo.ans = get_best(novo.ans, calcula(m,1,suf_pos,suf,other.pref_pos,other.pref) );
			novo.ans = get_best(novo.ans, calcula(m,2,suf_pos,suf,other.pref_pos,other.pref) );
		}

		return novo;

	}

};

int tab[MAXN][3],X[MAXN],Y[MAXN],N,Q;
node seg[4*MAXN];

void update(int pos,int left,int right,int x){
	
	if(left == right){
		seg[pos] = node(x,tab[x][1],tab[x][2]);
		return;
	}

	int mid = (left + right)/2;
	if(x <= mid) update(2*pos,left,mid,x);
	else update(2*pos+1,mid+1,right,x);

	seg[pos] = seg[2*pos]*seg[2*pos+1];

}

trinca doQuery(){
	if(seg[1].empty) return make_tuple(1,1,1);
	trinca ans = seg[1].ans;
	ans = get_best(ans, calcula(1,1, seg[1].pref_pos, seg[1].pref,seg[1].pref_pos, seg[1].pref ) );
	ans = get_best(ans, calcula(1,2, seg[1].pref_pos, seg[1].pref,seg[1].pref_pos, seg[1].pref ) );
	ans = get_best(ans, calcula(N,1, seg[1].suf_pos, seg[1].suf,seg[1].suf_pos, seg[1].suf ) );
	ans = get_best(ans, calcula(N,2, seg[1].suf_pos, seg[1].suf,seg[1].suf_pos, seg[1].suf ) );
	return ans;
}

int main(){

	scanf("%d %d",&N,&Q);

	for(int i = 1;i<=Q;i++){

		char op;
		scanf(" %c",&op);
		if(op == 'E'){
			trinca davez = doQuery();
			X[i] = get<1>(davez);
			Y[i] = get<2>(davez);
			tab[X[i]][Y[i]] = 1;
			update(1,1,N,X[i]);
			printf("%d %d\n",X[i],Y[i]);
		}
		else{
			int k;
			scanf("%d",&k);
			tab[X[k]][Y[k]] = 0;
			update(1,1,N,X[k]);
		}

	}

	return 0;

}

Compilation message

tram.cpp: In function 'int main()':
tram.cpp:158:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  158 |  scanf("%d %d",&N,&Q);
      |  ~~~~~^~~~~~~~~~~~~~~
tram.cpp:163:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  163 |   scanf(" %c",&op);
      |   ~~~~~^~~~~~~~~~~
tram.cpp:174:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  174 |    scanf("%d",&k);
      |    ~~~~~^~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 28524 KB Output is correct
2 Correct 19 ms 28524 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 28524 KB Output is correct
2 Correct 21 ms 28524 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 28524 KB Output is correct
2 Correct 21 ms 28524 KB Output is correct
3 Correct 22 ms 28524 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 28524 KB Output is correct
2 Correct 22 ms 28524 KB Output is correct
3 Correct 22 ms 28524 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 30316 KB Output is correct
2 Correct 22 ms 28652 KB Output is correct
3 Correct 27 ms 30336 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 30316 KB Output is correct
2 Correct 25 ms 28524 KB Output is correct
3 Correct 25 ms 30188 KB Output is correct

Subtask #7
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 29164 KB Output is correct
2 Correct 62 ms 29036 KB Output is correct
3 Correct 66 ms 29164 KB Output is correct

Subtask #8
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 30828 KB Output is correct
2 Correct 58 ms 29164 KB Output is correct
3 Correct 72 ms 30808 KB Output is correct