oj.uz

Submission #861041

# Submission time Handle Problem Language Result Execution time Memory
861041 2023-10-15T07:47:02 Z Dzadzo Poklon (COCI17_poklon) C++17
140 / 140
 535 ms 46264 KB 
#include <bits/stdc++.h>
#define ll long long
#define int ll
#define pb push_back
#define S second
#define F first
#define pii pair<int,int>
#define vi vector <int>
#define vvi vector <vi>
#define vvvi vector <vvi>
#define vp vector <pii>
#define vvp vector <vp>
#define vb vector <bool>
#define vvb vector <vb>;
#define INF LLONG_MAX
#define MOD 1000000009
#define MAXN 500000
#pragma GCC optimize("O3,unroll-loops")
using namespace std;
int t[4*MAXN+1];
void up(int v,int tl,int tr,int pos,int val){
	if (tl==tr)t[v]=val;else{
		int tm=(tl+tr)/2;
		if (pos<=tm)up(v*2,tl,tm,pos,val);else up(v*2+1,tm+1,tr,pos,val);
		t[v]=t[v*2]+t[v*2+1];
	}
}
int query(int v,int tl,int tr,int l,int r){
	if (l>r)return 0;
	if (tl==l && tr==r)return t[v];
	int tm=(tl+tr)/2;
	return query(v*2,tl,tm,l,min(r,tm))+query(v*2+1,tm+1,tr,max(l,tm+1),r);
}
int32_t main() {
	ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
	int n,q;
	cin>>n>>q;
	int a[n+1];
	for (int i=1;i<=n;i++)cin>>a[i];
	vvp Q(n+1);
	int ans[q+1];
	for (int i=1;i<=q;i++){
		int l,r;
		cin>>l>>r;
		Q[r].pb({l,i});
	}
	map <int,int> f;
	int prev[n+1];
	for (int i=1;i<=n;i++){
		prev[i]=f[a[i]];
		f[a[i]]=i;
	}
	
	for (int i=1;i<=n;i++){
		if (prev[i]){
			up(1,1,n,prev[i],1);
			if (prev[prev[i]]){
				up(1,1,n,prev[prev[i]],-1);
				if (prev[prev[prev[i]]]){
					up(1,1,n,prev[prev[prev[i]]],0);
				}
			}
		}
		for (auto &[x,id]:Q[i]){
			ans[id]=query(1,1,n,x,i);
		}
	}
	for (int i=1;i<=q;i++)cout<<ans[i]<<"\n";

}

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 4 ms 860 KB Output is correct
5 Correct 80 ms 10092 KB Output is correct
6 Correct 84 ms 10068 KB Output is correct
7 Correct 199 ms 19524 KB Output is correct
8 Correct 343 ms 31148 KB Output is correct
9 Correct 506 ms 38996 KB Output is correct
10 Correct 535 ms 46264 KB Output is correct