Submission #1278923

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278923		SmuggingSpun	Weighting stones (IZhO11_stones)	C++20	100 / 100	43 ms	4552 KiB

stones

#include<bits/stdc++.h>
#define taskname "D"
using namespace std;
const int lim = 1e5 + 5;
int n, r[lim], s[lim], st[lim << 2], lazy[lim << 2];
void push_down(int id){
	st[id << 1] += lazy[id];
	st[id << 1 | 1] += lazy[id];
	lazy[id << 1] += lazy[id];
	lazy[id << 1 | 1] += lazy[id];
	lazy[id] = 0;
}
void update(int id, int l, int r, int u, int v, int x){
	if(l > v || r < u){
		return;
	}
	if(u <= l && v >= r){
		st[id] += x;
		lazy[id] += x;
		return;
	}
	int m = (l + r) >> 1;
	push_down(id);
	update(id << 1, l, m, u, v, x);
	update(id << 1 | 1, m + 1, r, u, v, x);
	st[id] = min(st[id << 1], st[id << 1 | 1]);
}
vector<bool>solve(int target){
	memset(st, 0, sizeof(st));
	memset(lazy, 0, sizeof(lazy));
	vector<bool>ans(n, false);
	for(int i = 0; i < n; i++){
		if(s[i] == target){
			update(1, 1, n, 1, r[i], 1);
		}
		else{
			update(1, 1, n, 1, r[i], -1);
		}
		ans[i] = (st[1] < 0);
	}
	return ans;
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	if(fopen(taskname".inp", "r")){
		freopen(taskname".inp", "r", stdin);
	}
	cin >> n;
	for(int i = 0; i < n; i++){
		cin >> r[i] >> s[i];
	}
	vector<bool>ans_1 = solve(1), ans_2 = solve(2);
	for(int i = 0; i < n; i++){
		cout << (ans_1[i] == ans_2[i] ? '?' : (ans_1[i] ? '<' : '>')) << "\n";
	}
}

Compilation message (stderr)

stones.cpp: In function 'int main()':
stones.cpp:46:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |                 freopen(taskname".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100