oj.uz

Submission #65650

# Submission time Handle Problem Language Result Execution time Memory
65650 2018-08-08T10:52:25 Z IvanC Tram (CEOI13_tram) C++17
100 / 100
 100 ms 30700 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 euclid(ll x,ll y){
	return x*x + y*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;
		empty = 0;

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

	}

	node operator*(const node& other)const{

		node novo;
		if(empty && other.empty){
			return novo;
		}
		if(other.empty){
			return (*this);
		}
		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);
		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) );
		novo.ans = get_best(novo.ans, calcula(m + 1,1,suf_pos,suf,other.pref_pos,other.pref) );
		novo.ans = get_best(novo.ans, calcula(m + 1,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:118:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  118 |  scanf("%d %d",&N,&Q);
      |  ~~~~~^~~~~~~~~~~~~~~
tram.cpp:123:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  123 |   scanf(" %c",&op);
      |   ~~~~~^~~~~~~~~~~
tram.cpp:134:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  134 |    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 20 ms 28524 KB Output is correct

Subtask #2
15.0 / 15.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 30316 KB Output is correct
2 Correct 22 ms 28524 KB Output is correct
3 Correct 25 ms 30212 KB Output is correct

Subtask #7
15.0 / 15.0

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

Subtask #8
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 30700 KB Output is correct
2 Correct 59 ms 28908 KB Output is correct
3 Correct 75 ms 30700 KB Output is correct