oj.uz

Submission #1019741

# Submission time Handle Problem Language Result Execution time Memory
1019741 2024-07-11T08:30:35 Z ZeroCool Poklon (COCI17_poklon) C++14
140 / 140
 837 ms 29776 KB 
#include <bits/stdc++.h>
using namespace std;
  
#define int long long
  
#define ll long long
#define ar array
#define ld long double
  
const int N = 5e5 + 20;
const int MOD = 1e9 + 7;
const int K = 700;
const int INF = 1e17;
const int LOG = 34;

int ans = 0;
int cnt[N];
int A[N];
void add(int x){
	x = A[x];
	ans -= cnt[x] == 2;
	cnt[x]++;
	ans += cnt[x] == 2;
}

void rem(int x){
	x = A[x];
	ans -= cnt[x] == 2;
	cnt[x]--;
	ans += cnt[x] == 2;
}

bool cmp(ar<int, 3> a, ar<int,3 > b){
	return ar<int,2>{a[0] / K, a[1]} < ar<int, 2>{b[0] / K, b[1]};
}

signed main(){ios::sync_with_stdio(false);cin.tie(0);   
	int n, q;
	cin>>n>>q;
	map<int,int> mp;
	int id = 0;
	for(int i = 0;i < n;i++){
		cin>>A[i];
		if(!mp.count(A[i]))mp[A[i]] = id++;
		A[i] = mp[A[i]];
		//cout<<A[i]<<" ";
	}
	
	//cout<<endl;
	ar<int, 3> que[q];
	for(int i = 0;i < q;i++){
		cin>>que[i][0]>>que[i][1];
		--que[i][0], --que[i][1];
		que[i][2] = i;
	}
	
	int ml = 0;
	int mr = -1;
	sort(que, que + q, cmp);
	int res[q];
	for(int i = 0;i < q;i++){
		int l = que[i][0];
		int r = que[i][1];
		int ind = que[i][2];
		//cout<<i<<endl;
		while(ml > l)add(--ml);
		while(mr < r)add(++mr);
		while(ml < l)rem(ml++);
		while(mr > r)rem(mr--);
		
		res[ind] = ans;
	}
	for(int i = 0;i < q;i++)cout<<res[i]<<" ";
}

// Te molam da raboti!

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 5 ms 604 KB Output is correct
5 Correct 94 ms 5972 KB Output is correct
6 Correct 91 ms 5804 KB Output is correct
7 Correct 220 ms 11792 KB Output is correct
8 Correct 427 ms 17688 KB Output is correct
9 Correct 575 ms 23512 KB Output is correct
10 Correct 837 ms 29776 KB Output is correct