Submission #1272258

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272258		SmuggingSpun	Poklon (COCI17_poklon)	C++20	140 / 140	526 ms	31736 KiB

poklon

#include<bits/stdc++.h>
#define taskname "E"
using namespace std;
const int lim = 5e5 + 5;
int n, q, a[lim], bit[lim];
void update(int p, int x){
	for(; p <= n; p += p & -p){
		bit[p] += x;
	}
}
int get(int p){
	int ans = 0;
	for(; p > 0; p -= p & -p){
		ans += bit[p];
	}
	return ans;
}
map<int, vector<int>>pos;
vector<pair<int, int>>query[lim];
int ans[lim];
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 >> q;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
	}
	for(int i = 1; i <= q; i++){
		int l, r;
		cin >> l >> r;
		query[r].push_back(make_pair(l, i));
	}
	memset(bit, 0, sizeof(bit));
	for(int r = 1; r <= n; r++){
		if(pos[a[r]].size() == 1){
			update(pos[a[r]][0], 1);
		}
		else if(!pos[a[r]].empty()){
			update(pos[a[r]][int(pos[a[r]].size()) - 2], -2);
			if(pos[a[r]].size() > 2){
				update(pos[a[r]][int(pos[a[r]].size()) - 3], 1);
			}
			update(pos[a[r]].back(), 1);
		}
		pos[a[r]].emplace_back(r);
		for(int i = 0; i < query[r].size(); i++){
			ans[query[r][i].second] = get(r) - get(query[r][i].first - 1); 
		}
	}
	for(int i = 1; i <= q; i++){
		cout << ans[i] << "\n";
	}
}

Compilation message (stderr)

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

• Subtask 1: 140 / 140