Submission #739453

#	Time	Username	Problem	Language	Result	Execution time	Memory
739453		MODDI	Weighting stones (IZhO11_stones)	C++14	0 / 100	2 ms	3412 KiB

stones

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<long long, long long> pll;
typedef pair<int,int> pii;
typedef vector<long long> vl;
typedef vector<int> vi;
int tree_levo[4 * 100100], tree_desno[4 * 100100];
void update_levo(int node, int l, int r, int pos){
	if(l == r){
		tree_levo[node]=1;
	}
	else{
		int mid = (l + r) / 2;
		if(pos <= mid)	update_levo(node*2, l, mid, pos);
		else update_levo(node*2+1, mid+1, r, pos);
		
		tree_levo[node] = tree_levo[node*2] + tree_levo[node*2+1];
	}
}
void update_desno(int node, int l, int r, int pos){
	if(l == r){
		tree_desno[node]=1;
	}
	else{
		int mid = (l + r) / 2;
		if(pos <= mid)	update_desno(node*2, l, mid, pos);
		else update_desno(node*2+1, mid+1, r, pos);
		
		tree_desno[node] = tree_desno[node*2] + tree_desno[node*2+1];
	}
}
int query_levo(int node, int l, int r, int L, int R){
	if(r < L || l > R)	return 0;
	if(L <= l && r <= R)	return tree_levo[node];
	
	int mid = (l + r) / 2;
	return query_levo(node*2, l, mid, L, R) + query_levo(node*2+1, mid+1, r, L, R);
}
int query_desno(int node, int l, int r, int L, int R){
	if(r < L || l > R)	return 0;
	if(L <= l && r <= R)	return tree_desno[node];
	
	int mid = (l + r) / 2;
	return query_desno(node*2, l, mid, L, R) + query_desno(node*2+1, mid+1, r, L, R);
}
void answer(int levo, int desno){
	if(levo < desno)
		cout<<"<"<<'\n';
	else if(levo > desno)
		cout<<">"<<'\n';
	else
		cout<<"?"<<'\n';
}
int main(){
	int n;
	cin>>n;
	int levo = 0, desno = 0, cnt_levo = 0, cnt_desno = 0;
	memset(tree_levo, 0, sizeof tree_levo);
	memset(tree_desno, 0, sizeof tree_desno);
	for(int i = 0; i < n; i++){
		int id, side;
		cin>>id>>side;
		if(side == 1){
			levo += query_desno(1, 1, n, 1, id-1);
			update_levo(1, 1, n, id);
			cnt_levo++;
			if(cnt_desno == 0)
				cout<<">"<<'\n';
			else
			answer(levo, desno);
		}
		else{
			desno += query_levo(1, 1, n, 1, id-1);
			update_desno(1, 1, n, id);
			cnt_desno++;
			if(cnt_levo == 0)
				cout<<"<"<<'\n';
			else
			answer(levo,desno);
		}
	}

	return 0;
}

• Subtask 1: 0 / 100